Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
Feedback from nature: simple randomised distributed algorithms for maximal independent set selection and greedy colouring
复制标题
来自大自然的反馈：用于最大独立集选择和贪婪着色的简单随机分布式算法
DOI：
10.1007/s00446-016-0269-8
复制
发表时间：
2016
影响因子：
1.3
通讯作者：
Lei Xu
中科院分区：
文献类型：
--
作者：
P. Jeavons;A. Scott;Lei Xu
我们提出了两个行之有效的问题，在极其恶劣的条件下有效地运作的分布式算法。我们的算法以一种简单而新颖的方式实现了最先进的性能。我们的最大独立集选择算法在相同的匿名处理器网络上运行。每个节点处的处理器没有关于网络的先验信息。在每个时间步，每个节点只能向所有邻居广播一个比特，或者保持沉默。每个节点都可以检测是否有一个或多个邻居进行了广播，但无法判断有多少个邻居进行了广播，或者是哪些邻居。我们建立在Afek等人（Science 331（6014）：183-185，2011）的最近工作的基础上，其受到研究果蝇中细胞网络发育的启发。然而，我们第一次纳入了生物系统的另一个重要特征：根据相邻节点的局部反馈，改变每个节点使用的概率值。给定任意n个节点的网络，我们的算法以很高的概率实现了O（\log n）O（logn）轮的最优时间复杂度和O（1）每个节点广播的单比特消息的最优期望消息复杂度。我们还表明，以前的方法，没有反馈，不能实现更好的$$\varOmega（\log ^2 n）$$Ω（log 2n）的时间复杂度与高概率，无论全球计划是用来选择的概率。我们的分布式贪婪着色算法在类似的苛刻条件下工作：每个相同的节点没有关于网络的先验信息，只能在每个时间步向所有邻居广播一条消息，代表所需的颜色，并且只能检测是否至少有一个邻居广播了每个颜色值。我们证明了我们的算法具有高概率的时间复杂度为O（\Delta +\log n）O（Δ+logn），其中$$\Delta $$Δ是网络的最大度，并且每个节点的预期消息复杂度为O（1）。
We propose distributed algorithms for two well-established problems that operate efficiently under extremely harsh conditions. Our algorithms achieve state-of-the-art performance in a simple and novel way. Our algorithm for maximal independent set selection operates on a network of identical anonymous processors. The processor at each node has no prior information about the network. At each time step, each node can only broadcast a single bit to all its neighbours, or remain silent. Each node can detect whether one or more neighbours have broadcast, but cannot tell how many of its neighbours have broadcast, or which ones. We build on recent work of Afek et al. (Science 331(6014):183–185, 2011) which was inspired by studying the development of a network of cells in the fruit fly. However we incorporate for the first time another important feature of the biological system: varying the probability value used at each node based on local feedback from neighbouring nodes. Given any n-node network, our algorithm achieves with high probability the optimal time complexity of $$O(\log n)$$O(logn) rounds and the optimal expected message complexity of O(1) single-bit messages broadcast by each node. We also show that the previous approach, without feedback, cannot achieve better than $$\varOmega (\log ^2 n)$$Ω(log2n) time complexity with high probability, whatever global scheme is used to choose the probabilities. Our algorithm for distributed greedy colouring works under similar harsh conditions: each identical node has no prior information about the network, can only broadcast a single message to all neighbours at each time step representing a desired colour, and can only detect whether at least one neighbour has broadcast each colour value. We show that with high probability our algorithm has a time complexity of $$O(\Delta +\log n)$$O(Δ+logn), where $$\Delta $$Δ is the maximum degree of the network, and also has an expected message complexity of O(1) messages broadcast by each node.