Optimal Dynamic Distributed MIS
Optimal Dynamic Distributed MIS
复制标题
最优动态分布式MIS
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Zohar S. Karnin
中科院分区：
文献类型：
--
作者：
K. Censor;Elad Haramaty;Zohar S. Karnin
在图中寻找最大独立集（MIS）是分布式计算中的一项重要任务. MIS的局部性质允许在静态分布式设置中快速解决方案，其在节点数量或其程度上是对数的。这一结果对于动态分布模型是很适用的，在动态分布模型中，边或节点可以被插入或删除。在本文中，我们采取了一种不同的方法，将局部性发挥到了极致，并展示了如何在动态分布式设置中更新MIS，无论是同步还是异步，只需一次调整和一轮，符合预期。这些强有力的保证适用于完整的全动态设置：边和节点的插入和删除，优雅而突然。这强烈地分离了静态和动态分布式模型，因为在前者中存在用于计算MIS的超常数下限。我们的研究结果是通过一种新的分析，仔细模拟贪婪的顺序MIS算法与随机排序的节点的令人惊讶的简单的解决方案。因此，我们的算法有一个直接的应用程序作为一个3-近似算法的相关聚类。这增加了分布式图分解的重要工具箱，它被广泛用作分布式计算中的关键构建块。最后，我们的算法具有有用的历史独立性，这意味着输出独立于构建该图的拓扑变化的历史。这意味着输出不能被对手选择，甚至不能被对手偏见，以防对手的目标是阻止我们优化某些目标函数。
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.
影响因子：
1.1
作者：
Levi, Reut;Rubinfeld, Ronitt;Yodpinyanee, Anak
通讯作者：
Yodpinyanee, Anak