https://scholars.lib.ntu.edu.tw/handle/123456789/606972
標題: | Time-Optimal Self-Stabilizing Leader Election in Population Protocols | 作者: | Burman J Chen H.-L Chen H.-P Doty D Nowak T Severson E Xu C. CHEN HO-LIN |
關鍵字: | leader election;population protocols;self-stabilization;Asymptotically optimal;Communication graphs;Initial configuration;Leader Election Problem;Quasi-poly-nomial;Random scheduling;Ranking problems;Standard population;Computation theory | 公開日期: | 2021 | 起(迄)頁: | 33-44 | 來源出版物: | Proceedings of the Annual ACM Symposium on Principles of Distributed Computing | 摘要: | 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. ? 2021 Owner/Author. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85109485150&doi=10.1145%2f3465084.3467898&partnerID=40&md5=8bcc0f6a8bc0ad3b75f414762cb5ec43 https://scholars.lib.ntu.edu.tw/handle/123456789/606972 |
DOI: | 10.1145/3465084.3467898 |
顯示於: | 電機工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。