2015/06/04 by Andrew Berns, Berns, Andrew
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.1506.01688
openalex publication_date 2015/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Overlay networks present an interesting challenge for fault-tolerant computing. Many overlay networks operate in dynamic environments (e.g. the Internet), where faults are frequent and widespread, and the number of processes in a system may be quite large. Recently, self-stabilizing overlay networks have been presented as a method for managing this complexity. Self-stabilizing overlay networks promise that, starting from any weakly-connected configuration, a correct overlay network will eventually be built. To date, this guarantee has come at a cost: nodes may either have high degree during the algorithm's execution, or the algorithm may take a long time to reach a legal configuration. In this paper, we present the first self-stabilizing overlay network algorithm that does not incur this penalty. Specifically, we (i) present a new locally-checkable overlay network based upon a binary search tree, and (ii) provide a randomized algorithm for self-stabilization that terminates in an expected polylogarithmic number of rounds and increases a node's degree by only a polylogarithmic factor in expectation.