Stabilizing leader election in population protocols
Stabilizing leader election in population protocols
复制标题
稳定人口协议中的领导人选举
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
M. Potop
中科院分区：
文献类型：
--
作者：
D. Canepa;M. Potop
在这篇文章中，我们讨论了带有先知的种群协议模型中的稳定领导人选举问题。种群协议是一种最新的计算模型，它捕获了生物系统之间的相互作用。在该模型中，当匿名有限状态代理(节点)执行局部对等交互时，观察到出现的全局行为。在这样的系统中，如果没有额外的假设，统一的自我稳定的领导人选举是不可能的。因此，经典模型增加了最终的领导者探测器Omega？，它最终检测领导者的存在或不存在。在增广模型中，已经提出了环和完备网络中领导人选举的几种解决方案。在这项工作中，我们将研究扩展到树和任意拓扑。我们提出了确定性和概率解。所有提出的算法都是内存优化的-它们每个代理只需要一个内存位。此外，我们证明了即使在随机化帮助的环境中，最终的引导者检测器也是必要的。
In this paper we address the stabilizing leader election problem in the population protocols model augmented with oracles. Population protocols is a recent model of computation that captures the interactions of biological systems. In this model emergent global behavior is observed while anonymous finite-state agents(nodes) perform local peer interactions. Uniform self-stabilizing leader election is impossible in such systems without additional assumptions. Therefore, the classical model has been augmented with the eventual leader detector, Omega?, that eventually detects the presence or absence of a leader. In the augmented model several solutions for leader election in rings and complete networks have been proposed. In this work we extend the study to trees and arbitrary topologies. We propose deterministic and probabilistic solutions. All the proposed algorithms are memory optimal --- they need only one memory bit per agent. Additionally, we prove the necessity of the eventual leader detector even in environments helped by randomization.