On Underlay-Aware Self-Stabilizing Overlay Networks

2018/09/07 by Thorsten Götte, Götte, Thorsten, Christian Scheideler +3
Computer Science · #Distributed #Distributed and Parallel Computing Systems #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Peer-to-Peer Network Technologies #and Cluster Computing (cs.DC)

paper · pdf · doi:10.48550/arxiv.1809.02436

openalex publication_date 2018/09/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We present a self-stabilizing protocol for an overlay network that constructs the Minimum Spanning Tree (MST) for an underlay that is modeled by a weighted tree. The weight of an overlay edge between two nodes is the weighted length of their shortest path in the tree. We rigorously prove that our protocol works correctly under asynchronous and non-FIFO message delivery. Further, the protocol stabilizes after O(N²) asynchronous rounds where N is the number of nodes in the overlay.

Related

• A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property
• Avatar: A Time- and Space-Efficient Self-Stabilizing Overlay Network
• Applications and Implications of a General Framework for Self-Stabilizing Overlay Networks
• A Uniform Self-Stabilizing Minimum Diameter Spanning Tree Algorithm
• Network Scaffolding for Efficient Stabilization of the Chord Overlay\n Network