Search Results

Documents authored by Moses Jr., William K.

Document
DOI: 10.4230/LIPIcs.ESA.2024.71
Towards Communication-Efficient Peer-To-Peer Networks

Authors: Khalid Hourani, William K. Moses Jr., and Gopal Pandurangan

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
We focus on designing Peer-to-Peer (P2P) networks that enable efficient communication. Over the last two decades, there has been substantial algorithmic research on distributed protocols for building P2P networks with various desirable properties such as high expansion, low diameter, and robustness to a large number of deletions. A key underlying theme in all of these works is to distributively build a random graph topology that guarantees the above properties. Moreover, the random connectivity topology is widely deployed in many P2P systems today, including those that implement blockchains and cryptocurrencies. However, a major drawback of using a random graph topology for a P2P network is that the random topology does not respect the underlying (Internet) communication topology. This creates a large propagation delay, which is a major communication bottleneck in modern P2P networks. In this paper, we work towards designing P2P networks that are communication-efficient (having small propagation delay) with provable guarantees. Our main contribution is an efficient, decentralized protocol, Close-Weaver, that transforms a random graph topology embedded in an underlying Euclidean space into a topology that also respects the underlying metric. We then present efficient point-to-point routing and broadcast protocols that achieve essentially optimal performance with respect to the underlying space.
Cite as

Khalid Hourani, William K. Moses Jr., and Gopal Pandurangan. Towards Communication-Efficient Peer-To-Peer Networks. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 71:1-71:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hourani_et_al:LIPIcs.ESA.2024.71,
  author =	{Hourani, Khalid and Moses Jr., William K. and Pandurangan, Gopal},
  title =	{{Towards Communication-Efficient Peer-To-Peer Networks}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{71:1--71:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.71},
  URN =		{urn:nbn:de:0030-drops-211428},
  doi =		{10.4230/LIPIcs.ESA.2024.71},
  annote =	{Keywords: Peer-to-Peer Networks, Overlay Construction Protocol, Expanders, Broadcast, Geometric Routing}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.55
Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous

Authors: Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K. Moses Jr.

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
Temporal graphs are dynamic graphs where the edge set can change in each time step, while the vertex set stays the same. Exploration of temporal graphs whose snapshot in each time step is a connected graph, called connected temporal graphs, has been widely studied. In this paper, we extend the concept of graph automorphisms from static graphs to temporal graphs and show for the first time that symmetries enable faster exploration: We prove that a connected temporal graph with n vertices and orbit number r (i.e., r is the number of automorphism orbits) can be explored in O(r n^{1+ε}) time steps, for any fixed ε > 0. For r = O(n^c) for constant c < 1, this is a significant improvement over the known tight worst-case bound of Θ(n²) time steps for arbitrary connected temporal graphs. We also give two lower bounds for temporal exploration, showing that Ω(n log n) time steps are required for some inputs with r = O(1) and that Ω(rn) time steps are required for some inputs for any r with 1 ≤ r ≤ n. Moreover, we show that the techniques we develop for fast exploration can be used to derive the following result for rendezvous: Two agents with different programs and without communication ability are placed by an adversary at arbitrary vertices and given full information about the connected temporal graph, except that they do not have consistent vertex labels. Then the two agents can meet at a common vertex after O(n^{1+ε}) time steps, for any constant ε > 0. For some connected temporal graphs with the orbit number being a constant, we also present a complementary lower bound of Ω(nlog n) time steps.
Cite as

Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K. Moses Jr.. Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dogeas_et_al:LIPIcs.ICALP.2024.55,
  author =	{Dogeas, Konstantinos and Erlebach, Thomas and Kammer, Frank and Meintrup, Johannes and Moses Jr., William K.},
  title =	{{Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.55},
  URN =		{urn:nbn:de:0030-drops-201989},
  doi =		{10.4230/LIPIcs.ICALP.2024.55},
  annote =	{Keywords: dynamic graphs, parameterized algorithms, algorithmic graph theory, graph automorphism, orbit number}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2024.42
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}
}
Document
DOI: 10.4230/LIPIcs.DISC.2022.19
An Almost Singularly Optimal Asynchronous Distributed MST Algorithm

Authors: Fabien Dufoulon, Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
A singularly (near) optimal distributed algorithm is one that is (near) optimal in two criteria, namely, its time and message complexities. For synchronous CONGEST networks, such algorithms are known for fundamental distributed computing problems such as leader election [Kutten et al., JACM 2015] and Minimum Spanning Tree (MST) construction [Pandurangan et al., STOC 2017, Elkin, PODC 2017]. However, it is open whether a singularly (near) optimal bound can be obtained for the MST construction problem in general asynchronous CONGEST networks. In this paper, we present a randomized distributed MST algorithm that, with high probability, computes an MST in asynchronous CONGEST networks and takes Õ(D^{1+ε} + √n) time and Õ(m) messages, where n is the number of nodes, m the number of edges, D is the diameter of the network, and ε > 0 is an arbitrarily small constant (both time and message bounds hold with high probability). Since Ω̃(D+√n) and Ω(m) are respective time and message lower bounds for distributed MST construction in the standard KT₀ model, our algorithm is message optimal (up to a polylog(n) factor) and almost time optimal (except for a D^ε factor). Our result answers an open question raised in Mashregi and King [DISC 2019] by giving the first known asynchronous MST algorithm that has sublinear time (for all D = O(n^{1-ε})) and uses Õ(m) messages. Using a result of Mashregi and King [DISC 2019], this also yields the first asynchronous MST algorithm that is sublinear in both time and messages in the KT₁ CONGEST model. A key tool in our algorithm is the construction of a low diameter rooted spanning tree in asynchronous CONGEST that has depth Õ(D^{1+ε}) (for an arbitrarily small constant ε > 0) in Õ(D^{1+ε}) time and Õ(m) messages. To the best of our knowledge, this is the first such construction that is almost singularly optimal in the asynchronous setting. This tree construction may be of independent interest as it can also be used for efficiently performing basic tasks such as verified broadcast and convergecast in asynchronous networks.
Cite as

Fabien Dufoulon, Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. An Almost Singularly Optimal Asynchronous Distributed MST Algorithm. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dufoulon_et_al:LIPIcs.DISC.2022.19,
  author =	{Dufoulon, Fabien and Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David},
  title =	{{An Almost Singularly Optimal Asynchronous Distributed MST Algorithm}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.19},
  URN =		{urn:nbn:de:0030-drops-172107},
  doi =		{10.4230/LIPIcs.DISC.2022.19},
  annote =	{Keywords: Asynchronous networks, Minimum Spanning Tree, Distributed Algorithm, Singularly Optimal}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.27
Singularly Near Optimal Leader Election in Asynchronous Networks

Authors: Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in asynchronous networks. Kutten et al. (JACM 2015) presented a singularly near optimal randomized leader election algorithm for general synchronous networks that ran in O(D) time and used O(m log n) messages (where D, m, and n are the network’s diameter, number of edges and number of nodes, respectively) with high probability. Both bounds are near optimal (up to a logarithmic factor), since Ω(D) and Ω(m) are the respective lower bounds for time and messages for leader election even for synchronous networks and even for (Monte-Carlo) randomized algorithms. On the other hand, for general asynchronous networks, leader election algorithms are only known that are either time or message optimal, but not both. Kutten et al. (DISC 2020) presented a randomized asynchronous leader election algorithm that is singularly near optimal for complete networks, but left open the problem for general networks. This paper shows that singularly near optimal (up to polylogarithmic factors) bounds can be achieved for general asynchronous networks. We present a randomized singularly near optimal leader election algorithm that runs in O(D + log² n) time and O(m log² n) messages with high probability. Our result is the first known distributed leader election algorithm for asynchronous networks that is near optimal with respect to both time and message complexity and improves over a long line of results including the classical results of Gallager et al. (ACM TOPLAS, 1983), Peleg (JPDC, 1989), and Awerbuch (STOC, 89).
Cite as

Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly Near Optimal Leader Election in Asynchronous Networks. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 27:1-27:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kutten_et_al:LIPIcs.DISC.2021.27,
  author =	{Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David},
  title =	{{Singularly Near Optimal Leader Election in Asynchronous Networks}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{27:1--27:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.27},
  URN =		{urn:nbn:de:0030-drops-148294},
  doi =		{10.4230/LIPIcs.DISC.2021.27},
  annote =	{Keywords: Leader election, Singular optimality, Randomized algorithms, Asynchronous networks, Arbitrary graphs}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.22
Singularly Optimal Randomized Leader Election

Authors: Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
This paper concerns designing distributed algorithms that are singularly optimal, i.e., algorithms that are simultaneously time and message optimal, for the fundamental leader election problem in networks. Our main result is a randomized distributed leader election algorithm for asynchronous complete networks that is essentially (up to a polylogarithmic factor) singularly optimal. Our algorithm uses O(n) messages with high probability and runs in O(log² n) time (with high probability) to elect a unique leader. The O(n) message complexity should be contrasted with the Ω(n log n) lower bounds for the deterministic message complexity of leader election algorithms (regardless of time), proven by Korach, Moran, and Zaks (TCS, 1989) for asynchronous algorithms and by Afek and Gafni (SIAM J. Comput., 1991) for synchronous networks. Hence, our result also separates the message complexities of randomized and deterministic leader election. More importantly, our (randomized) time complexity of O(log² n) for obtaining the optimal O(n) message complexity is significantly smaller than the long-standing Θ̃(n) time complexity obtained by Afek and Gafni and by Singh (SIAM J. Comput., 1997) for message optimal (deterministic) election in asynchronous networks. Afek and Gafni also conjectured that Θ̃(n) time would be optimal for message-optimal asynchronous algorithms. Our result shows that randomized algorithms are significantly faster. Turning to synchronous complete networks, Afek and Gafni showed an essentially singularly optimal deterministic algorithm with O(log n) time and O(n log n) messages. Ramanathan et al. (Distrib. Comput. 2007) used randomization to improve the message complexity, and showed a randomized algorithm with O(n) messages but still with O(log n) time (with failure probability O(1 / log^{Ω(1)}n)). Our second result shows that synchronous complete networks admit a tightly singularly optimal randomized algorithm, with O(1) time and O(n) messages (both bounds are optimal). Moreover, our algorithm’s time bound holds with certainty, and its message bound holds with high probability, i.e., 1-1/n^c for constant c. Our results demonstrate that leader election can be solved in a simultaneously message and time-efficient manner in asynchronous complete networks using randomization. It is open whether this is possible in asynchronous general networks.
Cite as

Shay Kutten, William K. Moses Jr., Gopal Pandurangan, and David Peleg. Singularly Optimal Randomized Leader Election. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kutten_et_al:LIPIcs.DISC.2020.22,
  author =	{Kutten, Shay and Moses Jr., William K. and Pandurangan, Gopal and Peleg, David},
  title =	{{Singularly Optimal Randomized Leader Election}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.22},
  URN =		{urn:nbn:de:0030-drops-131002},
  doi =		{10.4230/LIPIcs.DISC.2020.22},
  annote =	{Keywords: Leader election, Asynchronous systems, Randomized algorithms, Singularly optimal, Complete networks}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.140
Deterministic Leader Election in Programmable Matter

Authors: Yuval Emek, Shay Kutten, Ron Lavi, and William K. Moses Jr.

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
Addressing a fundamental problem in programmable matter, we present the first deterministic algorithm to elect a unique leader in a system of connected amoebots assuming only that amoebots are initially contracted. Previous algorithms either used randomization, made various assumptions (shapes with no holes, or known shared chirality), or elected several co-leaders in some cases. Some of the building blocks we introduce in constructing the algorithm are of interest by themselves, especially the procedure we present for reaching common chirality among the amoebots. Given the leader election and the chirality agreement building block, it is known that various tasks in programmable matter can be performed or improved. The main idea of the new algorithm is the usage of the ability of the amoebots to move, which previous leader election algorithms have not used.
Cite as

Yuval Emek, Shay Kutten, Ron Lavi, and William K. Moses Jr.. Deterministic Leader Election in Programmable Matter. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 140:1-140:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{emek_et_al:LIPIcs.ICALP.2019.140,
  author =	{Emek, Yuval and Kutten, Shay and Lavi, Ron and Moses Jr., William K.},
  title =	{{Deterministic Leader Election in Programmable Matter}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{140:1--140:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.140},
  URN =		{urn:nbn:de:0030-drops-107169},
  doi =		{10.4230/LIPIcs.ICALP.2019.140},
  annote =	{Keywords: programmable matter, geometric amoebot model, leader election}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact