An optimal bit complexity randomized distributed MIS algorithm
An optimal bit complexity randomized distributed MIS algorithm
复制标题
DOI：
10.1007/s00446-010-0121-5
复制
发表时间：
2011-04-01
影响因子：
1.3
通讯作者：
Zemmari, A.
中科院分区：
文献类型：
--
作者：
Metivier, Y.;Robson, J. M.;Zemmari, A.
我们提出了一个随机分布式最大独立集（MIS）算法的大小为n的任意图，该算法在时间O中停止了概率1 -O（n（-1）），并且仅需要包含1位的消息。因此，其位复杂性PAR通道为O（log n）。我们假设该图是匿名的：独特的身份无法区分过程。我们仅假设每个顶点通过局部已知的频道名称区分其邻居。此外，我们不认为该图的大小（或大小上的上限）是已知的。该算法对于位复杂性是最佳的（模拟乘法常数），并改善了先前的随机分布式MIS算法（根据Luby引起的随机前列物算法推论（Siam J.Comput。15：1036-1053，1986））））））））））））））））））））））每个通道的o（log（2）n）的图形（时间O（log n）停止，每个消息的大小为log n）。该结果基于一种强大而通用的技术，用于转换包含在网络的每个顶点上随机绘制的真实数字的消息交换的不切实际交换，以交换位。然后，我们考虑一个自然的问题：将顶点包含在MIS中对遥远顶点有什么影响？我们证明，随着有限度的顶点的距离的增长，这种影响迅速消失，并且我们提供了一个反示例，表明该结果一般不存在。我们还证明，这些结果对于Lynch（分布式算法，Morgan Kaufman 1996）和Wattenhofer（http://dcg.ethz.ch/lectures/FS08/FS08/DistComp/Lectemp/lecture/chapter4.pdf，2007年）提出的Luby的算法仍然有效。 。对于Peleg给出的变体（分布式计算 - 对局部敏感的方法2000），这个问题仍然开放。
We present a randomized distributed maximal independent set (MIS) algorithm for arbitrary graphs of size n that halts in time O(log n) with probability 1 - o(n (-1)), and only needs messages containing 1 bit. Thus, its bit complexity par channel is O(log n). We assume that the graph is anonymous: unique identities are not available to distinguish between the processes; we only assume that each vertex distinguishes between its neighbours by locally known channel names. Furthermore we do not assume that the size (or an upper bound on the size) of the graph is known. This algorithm is optimal (modulo a multiplicative constant) for the bit complexity and improves the best previous randomized distributed MIS algorithms (deduced from the randomized PRAM algorithm due to Luby (SIAM J. Comput. 15:1036-1053, 1986)) for general graphs which is O(log(2) n) per channel (it halts in time O(log n) and the size of each message is log n). This result is based on a powerful and general technique for converting unrealistic exchanges of messages containing real numbers drawn at random on each vertex of a network into exchanges of bits. Then we consider a natural question: what is the impact of a vertex inclusion in the MIS on distant vertices? We prove that this impact vanishes rapidly as the distance grows for bounded-degree vertices and we provide a counter-example that shows this result does not hold in general. We prove also that these results remain valid for Luby's algorithm presented by Lynch (Distributed algorithms. Morgan Kaufman 1996) and by Wattenhofer (http://dcg.ethz.ch/lectures/fs08/distcomp/lecture/chapter4.pdf, 2007). This question remains open for the variant given by Peleg (Distributed computing-a locality-sensitive approach 2000).