DEX: self-healing expanders
From MaRDI portal
Abstract: We present a fully-distributed self-healing algorithm DEX, that maintains a constant degree expander network in a dynamic setting. To the best of our knowledge, our algorithm provides the first efficient distributed construction of expanders --- whose expansion properties hold {em deterministically} --- that works even under an all-powerful adaptive adversary that controls the dynamic changes to the network (the adversary has unlimited computational power and knowledge of the entire network state, can decide which nodes join and leave and at what time, and knows the past random choices made by the algorithm). Previous distributed expander constructions typically provide only {em probabilistic} guarantees on the network expansion which {em rapidly degrade} in a dynamic setting; in particular, the expansion properties can degrade even more rapidly under {em adversarial} insertions and deletions. Our algorithm provides efficient maintenance and incurs a low overhead per insertion/deletion by an adaptive adversary: only rounds and messages are needed with high probability ( is the number of nodes currently in the network). The algorithm requires only a constant number of topology changes. Moreover, our algorithm allows for an efficient implementation and maintenance of a distributed hash table (DHT) on top of DEX, with only a constant additional overhead. Our results are a step towards implementing efficient self-healing networks that have emph{guaranteed} properties (constant bounded degree and expansion) despite dynamic changes.
Recommendations
Cites work
- \(\mathrm{SKIP}^{+}\), a self-stabilizing skip graph
- A Chernoff Bound for Random Walks on Expander Graphs
- Araneola: a scalable reliable multicast system for dynamic environments
- Correctness of gossip-based membership under message loss
- Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski
- Distributed Computing: A Locality-Sensitive Approach
- Expander graphs and their applications
- Fast distributed random walks
- scientific article; zbMATH DE number 53883 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- Novel architectures for P2P applications: the continuous-discrete approach
- Probability and Computing
- Spanders: distributed spanning expanders
- The expansion and mixing time of skip graphs with applications
- The flip Markov chain and a randomising P2P protocol
- The forgiving graph: a distributed data structure for low stretch under adversarial attack
- The forgiving tree, a self-healing distributed data structure
- Towards robust and efficient computation in dynamic peer-to-peer networks
- Universal continuous routing strategies
- Xheal, localized self-healing using expanders
Cited in
(10)- The forgiving graph: a distributed data structure for low stretch under adversarial attack
- Xheal: a localized self-healing algorithm using expanders
- Distributed agreement in dynamic peer-to-peer networks
- The forgiving tree, a self-healing distributed data structure
- Xheal, localized self-healing using expanders
- Physical expander in virtual tree overlay
- Spanders: distributed spanning expanders
- The forgiving graph, a distributed data structure for low stretch under adversarial attack
- Network Scaffolding for Efficient Stabilization of the Chord Overlay Network
- Towards communication-efficient Peer-to-Peer networks
This page was built for publication: DEX: self-healing expanders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2629213)
