DEX: Self-Healing Expanders

Gopal Pandurangan, Peter Robinson, Amitabh Trehan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Citations (Scopus)
97 Downloads (Pure)

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 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 probabilistic guarantees on the network expansion which rapidly degrade in a dynamic setting, in particular, the expansion properties can degrade even more rapidly under adversarial insertions and deletions. Our algorithm provides efficient maintenance and incurs a low overhead per insertion/deletion by an adaptive adversary: only O(log n) rounds and O(log n) messages are needed with high probability (n 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 guaranteed properties (constant bounded degree and expansion) despite dynamic changes.
Original languageEnglish
Title of host publicationParallel and Distributed Processing Symposium, 2014 IEEE 28th International
Pages702-711
DOIs
Publication statusPublished - May 2014
EventIEEE 28th International Parallel and Distributed Processing Symposium (IPDPS), 2014 - Arizona Grand Resort, Phoenix, United States
Duration: 19 May 201423 May 2014

Conference

ConferenceIEEE 28th International Parallel and Distributed Processing Symposium (IPDPS), 2014
CountryUnited States
CityPhoenix
Period19/05/201423/05/2014

Keywords

  • Distributed algorithm
  • Deterministic Expander
  • CONGEST Model
  • Self-healing

ASJC Scopus subject areas

  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'DEX: Self-Healing Expanders'. Together they form a unique fingerprint.

  • Cite this

    Pandurangan, G., Robinson, P., & Trehan, A. (2014). DEX: Self-Healing Expanders. In Parallel and Distributed Processing Symposium, 2014 IEEE 28th International (pp. 702-711) https://doi.org/10.1109/IPDPS.2014.78