DEX: Self-Healing Expanders

Gopal Pandurangan, Peter Robinson, Amitabh Trehan

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

13 Citations (Scopus)
166 Downloads (Pure)


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
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


ConferenceIEEE 28th International Parallel and Distributed Processing Symposium (IPDPS), 2014
Country/TerritoryUnited States


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

ASJC Scopus subject areas

  • Computer Networks and Communications


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

Cite this