Search Results

Documents authored by Moorman, Michael


Document
Time- and Communication-Efficient Overlay Network Construction via Gossip

Authors: Fabien Dufoulon, Michael Moorman, William K. Moses Jr., and Gopal Pandurangan

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)


Abstract
We focus on the well-studied problem of distributed overlay network construction. We consider a synchronous gossip-based communication model where in each round a node can send a message of small size to another node whose identifier it knows. The network is assumed to be reconfigurable, i.e., a node can add new connections (edges) to other nodes whose identifier it knows or drop existing connections. Each node initially has only knowledge of its own identifier and the identifiers of its neighbors. The overlay construction problem is, given an arbitrary (connected) graph, to reconfigure it to obtain a bounded-degree expander graph as efficiently as possible. The overlay construction problem is relevant to building real-world peer-to-peer network topologies that have desirable properties such as low diameter, high conductance, robustness to adversarial deletions, etc. Our main result is that we show that starting from any arbitrary (connected) graph G on n nodes and m edges, we can construct an overlay network that is a constant-degree expander in polylog rounds using only Õ(n) messages. Our time and message bounds are both essentially optimal (up to polylogarithmic factors). Our distributed overlay construction protocol is very lightweight as it uses gossip (each node communicates with only one neighbor in each round) and also scalable as it uses only Õ(n) messages, which is sublinear in m (even when m is moderately dense). To the best of our knowledge, this is the first result that achieves overlay network construction in polylog rounds and o(m) messages. Our protocol uses graph sketches in a novel way to construct an expander overlay that is both time and communication efficient. A consequence of our overlay construction protocol is that distributed computation can be performed very efficiently in this model. In particular, a wide range of fundamental tasks such as broadcast, leader election, and minimum spanning tree (MST) construction can be accomplished in polylog rounds and Õ(n) message complexity in any graph.

Cite as

Fabien Dufoulon, Michael Moorman, William K. Moses Jr., and Gopal Pandurangan. Time- and Communication-Efficient Overlay Network Construction via Gossip. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 42:1-42:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{dufoulon_et_al:LIPIcs.ITCS.2024.42,
  author =	{Dufoulon, Fabien and Moorman, Michael and Moses Jr., William K. and Pandurangan, Gopal},
  title =	{{Time- and Communication-Efficient Overlay Network Construction via Gossip}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{42:1--42:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.42},
  URN =		{urn:nbn:de:0030-drops-195700},
  doi =		{10.4230/LIPIcs.ITCS.2024.42},
  annote =	{Keywords: Peer-to-Peer Networks, Overlay Construction Protocol, Gossip, Expanders, Sublinear Bounds}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail