Khalid Hourani
Towards Communication-Efficient Peer-to-Peer Networks
Hourani, Khalid; Moses Jr., William K.; Pandurangan, Gopal
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.
Citation
Hourani, K., Moses Jr., W. K., & Pandurangan, G. (in press). Towards Communication-Efficient Peer-to-Peer Networks. . https://doi.org/10.4230/LIPIcs.ESA.2024.9
Conference Name | European Symposium on Algorithms |
---|---|
Conference Location | Egham, United Kingdom |
Start Date | Sep 2, 2024 |
End Date | Sep 4, 2024 |
Acceptance Date | Jun 23, 2024 |
Deposit Date | Jun 27, 2024 |
DOI | https://doi.org/10.4230/LIPIcs.ESA.2024.9 |
Keywords | 2012 ACM Subject Classification Theory of computation → Distributed algorithms; Mathematics of computing → Probabilistic algorithms; Mathematics of computing → Discrete mathematics Keywords and phrases Peer-to-Peer Networks, Overlay Construction Pro |
Public URL | https://durham-repository.worktribe.com/output/2504358 |
Related Public URLs | https://arxiv.org/abs/2406.16661 |
This file is under embargo due to copyright reasons.
You might also like
Awake Complexity of Distributed Minimum Spanning Tree
(2024)
Conference Proceeding
Dispersion, Capacitated Nodes, and the Power of a Trusted Shepherd
(2024)
Conference Proceeding
Time- and Communication-Efficient Overlay Network Construction via Gossip
(2023)
Conference Proceeding
Efficient live exploration of a dynamic ring with mobile robots
(2023)
Journal Article
Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous
(2024)
Conference Proceeding
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search