Distributed Maximal Independent Set using Small Messages
Distributed Maximal Independent Set using Small Messages
复制标题
使用小消息的分布式最大独立集
DOI：
10.1137/1.9781611975482.50
复制
发表时间：
2019
影响因子：
7.2
通讯作者：
M. Ghaffari
中科院分区：
文献类型：
--
作者：
M. Ghaffari
最大独立集问题是分布式图算法的核心问题之一。著名的作品吕比[STOC'85]和阿龙，巴拜，和Itai [JALG'86]提供O（log n）轮随机分布式MIS算法，其工作于O（log n）位消息。Barenboim，Elkin，Pettie和Schneider [FOCS'11; JACM'16]的突破将此轮复杂度改进为[MATH HERE]，然后由Ghaffari [SODA'16]改进为[MATH HERE]，其中Δ表示最大程度。然而，这些改进有一个缺点：它们需要更大的消息，高达poly（Δ log n）位。事实上，使用小消息来提高O（log n）轮复杂度的问题已经开放了三十年，基本上所有的Δ值，除了Δ = o（log n），其中有O（Δ + log* n）轮确定性算法。
我们提出了一个随机分布式MIS算法，O（log n）位的消息，实现了一轮的复杂度[MATH HERE]。这是第一个使用小消息的算法，它改进了吕比和Alon等人的O（log n）轮复杂度，并且其复杂度几乎与使用无界消息大小的最佳已知算法相匹配。作为MIS算法的应用或沿着它的道路，我们得到了改进的小消息分布式算法，用于解决网络分解、（Δ + 1）-顶点着色和规则集等问题。
Maximal Independent Set (MIS) is one of the central problems in distributed graph algorithms. The celebrated works of Luby [STOC'85] and Alon, Babai, and Itai [JALG'86] provide O(log n)-round randomized distributed MIS algorithms, which work with O(log n)-bit messages. This round complexity was improved to [MATH HERE] in a breakthrough of Barenboim, Elkin, Pettie, and Schneider [FOCS'11; JACM'16] and then to [MATH HERE] by Ghaffari [SODA'16], where Δ denotes the maximum degree. However, these improvements have one drawback: they require much larger messages, up to poly(Δ log n) bits. Indeed, the question of improving the O(log n) round complexity using small messages has remained open for three decades, for essentially all values of Δ, except for Δ = o(log n) where there are O(Δ + log* n)-round deterministic algorithms.
We present a randomized distributed MIS algorithm, with O(log n)-bit messages, that achieves a round complexity of [MATH HERE]. This is the first algorithm with small messages that improves on the O(log n) round complexity of Luby and Alon et al. for a wide range of Δ, and its complexity almost matches that of the best known algorithm using unbounded message sizes. As applications of this MIS algorithm or along the way to it, we obtain improved distributed algorithms with small messages for some other well-studied problems including network decompositions, (Δ + 1)-vertex coloring, and ruling sets.