2021/09/28 by Andrew Berns, Berns, Andrew
Computer Science · #Distributed and Parallel Computing Systems #Peer-to-Peer Network Technologies #Distributed systems and fault tolerance
paper · pdf · doi:10.48550/arxiv.2109.14126
Overlay networks, where nodes communicate with neighbors over logical links\nconsisting of zero or more physical links, have become an important part of\nmodern networking. From data centers to IoT devices, overlay networks are used\nto organize a diverse set of processes for efficient operations like searching\nand routing. Many of these overlay networks operate in fragile environments\nwhere faults that perturb the logical network topology are commonplace.\nSelf-stabilizing overlay networks offer one approach for managing these faults,\npromising to build or restore a particular topology from any weakly-connected\ninitial configuration.\n Designing efficient self-stabilizing algorithms for many topologies, however,\nis not an easy task. For non-trivial topologies that have desirable properties\nlike low diameter and robust routing in the face of node or link failures,\nself-stabilizing algorithms to date have had at least linear running time or\nspace requirements. In this work, we address this issue by presenting an\nalgorithm for building a Chord network that has polylogarithmic time and space\ncomplexity. Furthermore, we discuss how the technique we use for building this\nChord network can be generalized into a ``design pattern'' for other desirable\noverlay network topologies.\n