Maintaining Distributed Data Structures in Dynamic Peer-to-Peer Networks

• DOI: 10.48550/arxiv.2409.10235
• Publication Date: 2024-09-16
• Authors: John Augustine; Antonio Cruciani; Iqra Altaf Gillani
• Keywords: FOS: Computer and information sciences; Computer Science - Distributed, Parallel, and Cluster Computing; Distributed, Parallel, and Cluster Computing (cs.DC)

We study robust and efficient distributed algorithms for building maintaining data structures in dynamic Peer-to-Peer (P2P) networks. P2P networks are characterized by a high level of dynamicity with abrupt heavy node \emph{churn} (nodes that join leave the network continuously over time). present novel algorithm builds maintains probability skip list $poly(n)$ rounds despite $\mathcal{O}(n/\log n)$ churn \emph{per round} ($n$ is stable size). assume controlled an oblivious adversary (that has complete knowledge control what nodes at time unlimited computational power, but to random choices made algorithm). Moreover, maintenance overhead proportional rate. Furthermore, scalable messages small (i.e., most $polylog(n)$ bits) every sends receives per round. Our crucially relies on parallel merge two $n$-elements lists delete large subset items, both $\mathcal{O}(\log probability. These procedures may be independent interest due their elegance potential applicability other contexts structures. To best our knowledge, work provides first-known fully-distributed structure provably works under highly settings rate). they localized do not require any global topological knowledge). Finally, we believe framework can generalized including graphs, potentially leading computation churn.