2026-08-16T21:28:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25102 2026-02-09T08:06:13Z ddc:004 open_access

Overlay Network Construction: Improved Overall and Node-Wise Message Complexity Chang, Yi-Jun Chen, Yanyu Mishra, Gopinath Distributed algorithms Overlay networks Expander graphs 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: GOSSIP-reply and HYBRID. In the GOSSIP-reply model, each node can send a message and receive a corresponding reply message in one round. In the HYBRID 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 GOSSIP-reply model, our protocol takes O(log n) rounds while in the HYBRID model, our protocol takes O(log² n) rounds. Both protocols use O (n log² n) bits of communication. We obtain improved bounds over prior work: GOSSIP-reply: A recent result by Dufoulon et al. (ITCS 2024) achieved O(log⁵ n) round complexity and O (n log⁵ n) message complexity using messages of at least Ω(log² n) bits in GOSSIP-reply. With messages of size O(log n), our protocol achieves an optimal round complexity of O(log n) and an improved message complexity of O(n log n). HYBRID: Götte et al. (Distributed Computing 2023) showed an optimal O(log n)-round algorithm with O(log² n) global messages per round which incurs a message complexity of Ω(m), where m is the number of edges in the initial topology. At the cost of increasing the round complexity to O(log² n) while using only O(log n) messages globally, our protocol achieves a message complexity that is independent of m. Our approach ensures that the total number of messages for node v, with degree deg(v) in the initial topology, is bounded by O(deg(v) + log n), while the algorithm of Götte et al. requires O(deg(v) + (log⁴ n)/(log log n)) messages per node. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yi-Jun Chang and Yanyu Chen and Gopinath Mishra 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.21 urn:nbn:de:0030-drops-251025 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.21 eng https://creativecommons.org/licenses/by/4.0/legalcode