The Locality of Distributed Symmetry Breaking
The Locality of Distributed Symmetry Breaking
复制标题
DOI：
10.1145/2903137
复制
发表时间：
2016-09-01
影响因子：
2.5
通讯作者：
Schneider, Johannes
中科院分区：
文献类型：
--
作者：
Barenboim, Leonid;Elkin, Michael;Schneider, Johannes
对称破坏问题是分布式计算领域中研究最充分的问题之一，但关于其复杂性的最基本问题仍然悬而未决。在本文中，我们工作在局部模型中(其中输入图和底层分布网络是相同的)，并研究了图上四个基本对称破坏问题的随机化复杂性：计算遗漏(极大独立集)、最大匹配、顶点着色和规则集。我们的一个小样本结果包括：-一个运行在O(log(2)Delta+2(O(Root Logn)时间内的管理信息系统算法，其中Delta是最大次数。这是对1986年的Luby和Alon、Babai和Itai算法进行改进的第一个MIS算法，当log n
Symmetry-breaking problems are among the most well studied in the field of distributed computing and yet the most fundamental questions about their complexity remain open. In this article we work in the LOCAL model (where the input graph and underlying distributed network are identical) and study the randomized complexity of four fundamental symmetry-breaking problems on graphs: computing MISs (maximal independent sets), maximal matchings, vertex colorings, and ruling sets. A small sample of our results includes the following:-An MIS algorithm running in O(log(2) Delta + 2(O(root loglogn))) time, where Delta is the maximum degree. This is the first MIS algorithm to improve on the 1986 algorithms of Luby and Alon, Babai, and Itai, when log n