Overlay Network Construction: Improved Overall and Node-Wise Message Complexity

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: $\mathsf{\text{GOSSIP-reply}}${} and $\mathsf{\text{HYBRID}}${}. In the $\mathsf{\text{GOSSIP-reply}}${} model, each node can send a message and receive a corresponding reply message in one round. In the $\mathsf{\text{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 $\mathsf{\text{GOSSIP-reply}}${} model, our protocol takes $O(\log n)$ rounds while in the $\mathsf{\text{HYBRID}}$ model, our protocol takes $O({\log }^{2}n)$ rounds. Both protocols use $O\left(n{\log }^{2}n\right)$ bits of communication.