DEX: self-healing expanders

<p class="Para" style="box-sizing: border-box; margin-top: 1em; margin-bottom: 1.2em; word-break: break-word;">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 class="EmphasisTypeItalic" style="box-sizing: border-box;">deterministically</em>—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 class="EmphasisTypeItalic" style="box-sizing: border-box;">probabilistic</em> guarantees on the network expansion which<em class="EmphasisTypeItalic" style="box-sizing: border-box;">rapidly degrade</em> in a dynamic setting; in particular, the expansion properties can degrade even more rapidly under <em class="EmphasisTypeItalic" style="box-sizing: border-box;">adversarial</em> insertions and deletions. Our algorithm provides efficient maintenance and incurs a low overhead per insertion/deletion by an adaptive adversary: only O(logn)O(log⁡n) rounds and O(logn)O(log⁡n) messages are needed with high probability (<em class="EmphasisTypeItalic" style="box-sizing: border-box;">n</em> 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 on top of dex  with only a constant additional overhead. Our results are a step towards implementing efficient self-healing networks that have <em class="EmphasisTypeItalic" style="box-sizing: border-box;">guaranteed</em> properties (constant bounded degree and expansion) despite dynamic changes.</p><p class="SimplePara" style="box-sizing: border-box;">Gopal Pandurangan has been supported in part by Nanyang Technological University Grant M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 Grant MOE2010-T2-2-082, MOE AcRF Tier 1 Grant MOE2012-T1-001-094, and the United States-Israel Binational Science Foundation (BSF) Grant 2008348. Peter Robinson has been supported by Grant MOE2011-T2-2-042 “Fault-tolerant Communication Complexity in Wireless Networks” from the Singapore MoE AcRF-2. Work done in part while the author was at the Nanyang Technological University and at the National University of Singapore. Amitabh Trehan has been supported by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11). Work done in part while the author was at Hebrew University of Jerusalem and at the Technion and supported by a Technion fellowship.</p>