Brief Announcement: Maintaining a Bounded Degree Expander in Dynamic Peer-To-Peer Networks
Loading...
Access rights
openAccess
CC BY
CC BY
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
7
Series
39th International Symposium on Distributed Computing (DISC 2025), pp. 1-7, Leibniz International Proceedings in Informatics (LIPIcs) ; Volume 356
Abstract
We study the problem of maintaining robust and sparse overlay networks in fully distributed settings where nodes continuously join and leave the system. This scenario closely models real-world unstructured peer-to-peer networks, where maintaining a well-connected yet low-degree communication graph is crucial. We generalize a recent protocol by Becchetti et al. [SODA 2020] that relies on a simple randomized connection strategy to build an expander topology with high probability to a dynamic networks with churn setting. In this work, the network dynamism is governed by an oblivious adversary that controls which nodes join and leave the system in each round. The adversary has full knowledge of the system and unbounded computational power, but cannot see the random choices made by the protocol. Our analysis builds on the framework of Augustine et al. [FOCS 2015], and shows that our distributed algorithm maintains a constant-degree expander graph with high probability, despite a continuous adversarial churn with a rate of up to O(n/polylog(n)) per round, where n is the stable network size. The protocol and proof techniques are not new, but together they resolve a specific open problem raised in prior work. The result is a simple, fully distributed, and churn-resilient protocol with provable guarantees that align with observed empirical behavior.Description
Keywords
Other note
Citation
Cruciani, A 2025, Brief Announcement: Maintaining a Bounded Degree Expander in Dynamic Peer-To-Peer Networks. in 39th International Symposium on Distributed Computing (DISC 2025) . Leibniz International Proceedings in Informatics (LIPIcs), vol. 356, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-7, International Symposium on Distributed Computing, Berlin, Germany, 27/10/2025. https://doi.org/10.4230/LIPIcs.DISC.2025.53