2024/12/06 by Chang, Yi-Jun, Chen, Yanyu, Mishra, Gopinath
#Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2412.04771
We consider the problem of constructing distributed overlay networks, where nodes in a reconfigurable system can create or sever connections with nodes whose identifiers they know. Initially, each node knows only its own and its neighbors' identifiers, forming a local channel, while the evolving structure is termed the global channel. The goal is to reconfigure any connected graph into a desired topology, such as a bounded-degree expander graph or a well-formed tree (WFT) with a constant maximum degree and logarithmic diameter, minimizing the total number of rounds and message complexity. This problem mirrors real-world peer-to-peer network construction, where creating robust and efficient systems is desired. We study the overlay reconstruction problem in a network of n nodes in two models: \textsfGOSSIP-reply and \textsfHYBRID. In the \textsfGOSSIP-reply model, each node can send a message and receive a corresponding reply message in one round. In the \textsfHYBRID model, a node can send O(1) messages to each neighbor in the local channel and a total of O(log n) messages in the global channel. In both models, we propose protocols for WFT construction with O(n log n) message complexities using messages of O(log n) bits. In the \textsfGOSSIP-reply model, our protocol takes O(log n) rounds while in the \textsfHYBRID model, our protocol takes O(log2 n) rounds. Both protocols use O(n log2 n) bits of communication.