Time-Optimal Self-Stabilizing Leader Election in Population Protocols
Time-Optimal Self-Stabilizing Leader Election in Population Protocols
复制标题
群体协议中的时间最优自稳定领导者选举
DOI：
10.1145/3465084.3467898
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Xu, Chuan
中科院分区：
文献类型：
--
作者：
Burman, Janna;Chen, Ho-Lin;Chen, Hsueh-Ping;Doty, David;Nowak, Thomas;Severson, Eric;Xu, Chuan
我们考虑标准群体协议模型，其中（先验的）不可区分的和匿名的智能体根据一致随机调度成对地相互作用。自稳定领导者选举问题要求协议从任何可能的初始配置收敛到单个领导者代理。我们开始研究种群协议的时间复杂度，在其原始设置下，即在完全通信图中，以概率为1解决该问题。Cai， Izumi和Wada先前已知的唯一协议[理论]。第一版。系统[50]以预期的并行时间Θ（n2）运行，并且在n个智能体的总体中具有最优的n个状态数。现有的协议有一个额外的属性，它会变得沉默，也就是说，代理的状态最终会停止变化。观察到任何解决自稳定领导者选举的沉默协议都需要Ω(n)预期并行时间，我们引入了一个使用最优O(n)并行时间和状态的沉默协议。在没有任何沉默约束的情况下，我们证明了在O（log n）的渐近最优期望并行时间内解决自稳定领导者选举是可能的，但至少使用指数状态（位数的拟多项式）。我们所有的协议（以及Cai等人的协议）都是通过解决更困难的排名问题来工作的：为代理分配排名1，z,n。
We consider the standard population protocol model, where (a priori) indistinguishable and anonymous agents interact in pairs according to uniformly random scheduling. The self-stabilizing leader election problem requires the protocol to converge on a single leader agent from any possible initial configuration. We initiate the study of time complexity of population protocols solving this problem in its original setting: with probability 1, in a complete communication graph. The only previously known protocol by Cai, Izumi, and Wada [Theor. Comput. Syst. 50] runs in expected parallel time Θ(n2) and has the optimal number of n states in a population of n agents. The existing protocol has the additional property that it becomes silent, i.e., the agents' states eventually stop changing.Observing that any silent protocol solving self-stabilizing leader election requires Ω(n) expected parallel time, we introduce a silent protocol that uses optimal O(n) parallel time and states. Without any silence constraints, we show that it is possible to solve self-stabilizing leader election in asymptotically optimal expected parallel time of O(log n), but using at least exponential states (a quasi-polynomial number of bits). All of our protocols (and also that of Cai et al.) work by solving the more difficult ranking problem: assigning agents the ranks 1,ł,n.
登录
查看更多内容
离散化学反应网络中的可组合计算
影响因子：
1.3
作者：
Severson, Eric E.;Haley, David;Doty, David
通讯作者：
Doty, David
任意通信图群体协议中的自稳定领导者选举
DOI：
--
发表时间：
2013
期刊：
International Conference on Principles of Distributed Systems
影响因子：
--
作者：
J. Beauquier;Peva Blanchard;Janna Burman
通讯作者：
Janna Burman
影响因子：
1.3
作者：
Angluin, Dana;Aspnes, James;Eisenstat, David
通讯作者：
Eisenstat, David
群体协议中的快速空间最优领导者选举
DOI：
10.1137/1.9781611975031.169
发表时间：
2017
期刊：
J. Comput. Syst. Sci.
影响因子：
--
作者：
L. Gąsieniec;Grzegorz Stachowiak
通讯作者：
Grzegorz Stachowiak
全局计算与局部计算：使用标识符进行快速计算
DOI：
--
发表时间：
2016
期刊：
Colloquium on Structural Information & Communication Complexity
影响因子：
--
作者：
M. Rabie
通讯作者：
M. Rabie