Feedback from nature: an optimal distributed algorithm for maximal independent set selection
Feedback from nature: an optimal distributed algorithm for maximal independent set selection
复制标题
来自自然的反馈：最大独立集选择的最优分布式算法
DOI：
10.1145/2484239.2484247
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Lei Xu
中科院分区：
文献类型：
--
作者：
A. Scott;P. Jeavons;Lei Xu
最大独立集选择是分布式计算中的一个基本问题。Afek等人最近提出了一种新的概率算法来解决这个问题，其灵感来自于对苍蝇细胞分化的研究。他们提出的算法简单而健壮，但不如以前的方法高效：预期的时间复杂度为O（log2n）。在这里，我们首先表明，无论如何选择全局概率值，Afek等人的方法都无法在所有网络中获得比这更好的效率。
Maximal Independent Set selection is a fundamental problem in distributed computing. A novel probabilistic algorithm for this problem has recently been proposed by Afek et al, inspired by the study of the way that developing cells in the fly become specialised. The algorithm they propose is simple and robust, but not as efficient as previous approaches: the expected time complexity is O(log2 n). Here we first show that the approach of Afek et al cannot achieve better efficiency than this across all networks, no matter how the global probability values are chosen.
However, we then propose a new algorithm that incorporates another important feature of the biological system: the probability value at each node is adapted using local feedback from neighbouring nodes. Our new algorithm retains all the advantages of simplicity and robustness, but also achieves the optimal efficiency of O(log n) expected time. The new algorithm also has only a constant message complexity per node.
影响因子：
4.6
作者：
T. Jacobsen;K. Brennan;A. Arias;M. Muskavitch
通讯作者：
T. Jacobsen;K. Brennan;A. Arias;M. Muskavitch