Optimal Dynamic Distributed MIS
Authors:
Open Access
- 25 July 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 217-226
Abstract
Finding a maximal independent set (MIS) in a graph is a cornerstone task in distributed computing. The local nature of an MIS allows for fast solutions in a static distributed setting, which are logarithmic in the number of nodes or in their degrees. The result trivially applies for the dynamic distributed model, in which edges or nodes may be inserted or deleted. In this paper, we take a different approach which exploits locality to the extreme, and show how to update an MIS in a dynamic distributed setting, either synchronous or asynchronous, with only a single adjustment and in a single round, in expectation. These strong guarantees hold for the complete fully dynamic setting: Insertions and deletions, of edges as well as nodes, gracefully and abruptly. This strongly separates the static and dynamic distributed models, as super-constant lower bounds exist for computing an MIS in the former. Our results are obtained by a novel analysis of the surprisingly simple solution of carefully simulating the greedy sequential MIS algorithm with a random ordering of the nodes. As such, our algorithm has a direct application as a 3-approximation algorithm for correlation clustering. This adds to the important toolbox of distributed graph decompositions, which are widely used as crucial building blocks in distributed computing. Finally, our algorithm enjoys a useful history-independence property, meaning the output is independent of the history of topology changes that constructed that graph. This means the output cannot be chosen, or even biased, by the adversary in case its goal is to prevent us from optimizing some objective function.Keywords
All Related Versions
Funding Information
- Israel Science Foundation (1696/14)
This publication has 58 references indexed in Scilit:
- The Forgiving Graph: a distributed data structure for low stretch under adversarial attackDistributed Computing, 2012
- An optimal bit complexity randomized distributed MIS algorithmDistributed Computing, 2010
- Distributed error confinementACM Transactions on Algorithms, 2010
- Empire of colonies: Self-stabilizing and self-organizing distributed algorithmTheoretical Computer Science, 2009
- Aggregating inconsistent informationJournal of the ACM, 2008
- Distributed algorithms for updating shortest paths2005
- Fault-Local Distributed MendingJournal of Algorithms, 1999
- Self-stabilizationACM Computing Surveys, 1993
- A fast and simple randomized parallel algorithm for the maximal independent set problemJournal of Algorithms, 1986
- Self-stabilizing systems in spite of distributed controlCommunications of the ACM, 1974