Overlay networks, where nodes communicate with neighbors over logical links consisting of zero or more physical links, have become an important part of modern networking. From data centers to IoT devices, overlay networks are used to organize a diverse set of processes for efficient operations like searching and routing. Many of these overlay networks operate in fragile environments where faults that perturb the logical network topology are commonplace. Self-stabilizing overlay networks offer one approach for managing these faults, promising to build or restore a particular topology from any weakly-connected initial configuration. Designing efficient self-stabilizing algorithms for many topologies, however, is not an easy task. For non-trivial topologies that have desirable properties like low diameter and robust routing in the face of node or link failures, self-stabilizing algorithms to date have had at least linear running time or space requirements. In this work, we address this issue by presenting an algorithm for building a Chord network that has polylogarithmic time and space complexity. Furthermore, we discuss how the technique we use for building this Chord network can be generalized into a ``design pattern'' for other desirable overlay network topologies.
翻译:由零或更多物理链接构成的逻辑链接的重叠网络与邻居进行连接的节点通信已成为现代网络的一个重要部分。 从数据中心到 IoT 设备,重叠网络被用来组织一套多样化的高效操作流程,例如搜索和路线。许多这些重叠网络在脆弱的环境中运作,因为那里存在干扰逻辑网络地形的错误。自我稳定重叠网络为管理这些错误提供了一种方法,承诺从任何薄弱连接的初始配置中建立或恢复特定的地形。然而,为许多地形设计高效的自我稳定算法并非一件容易的任务。对于在节点或连接失败面前具有低直径和强固路径等可取性的非三角结构学,自稳定算法迄今为止至少具有线性运行时间或空间要求。在这项工作中,我们通过提出一个算法来建立具有多logarith时间和空间复杂性的Chord网络来解决这个问题。此外,我们讨论如何在建设这个Chord网络顶端模式时使用的技术可以普遍化为另一个模式。