Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election

作     者：Gasieniec, Leszek Stachowiak, Grzegorz 

作者机构：Univ Liverpool Dept Comp Sci Liverpool Merseyside England Augusta Univ Sch Comp & Cyber Sci Augusta GA 30912 USA Uniwersytet Wroclawski Inst Informatyki Wroclaw Poland 

出 版 物：《JOURNAL OF THE ACM》 (J ACM)

年 卷 期：2021年第68卷第1期

页      面：1–21页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：University of Liverpool initiative Networks Sciences and Technologies (NeST) Polish National Science Centre [DEC-2012/06/M/ST6/00459] 

主　　题：Population protocols leader election randomised algorithm distributed algorithm 

摘      要：The model of population protocols refers to the growing in popularity theoretical framework suitable for studying pairwise interactions within a large collection of simple indistinguishable entities, frequently called agents. In this article, the emphasis is on the space complexity of fast leader election in population protocols governed by the random scheduler, which uniformly at random selects pairwise interactions between n agents. One of the main results of this article is the first fast space optimal leader election protocol, which works with high probability. The new protocol operates in parallel time O(log(2) n) equivalent to O(n log(2) n) sequential pairwise interactions with each agent s memory space limited to O(log logn) states. This double logarithmic space utilisation matches asymptotically the lower bound 12 log logn on the number of states utilised by agents in any leader election algorithm with the running time o(n/polylog n);see Reference [7]. Our new solution expands also on the classical concept of phase clocks used to synchronise and to coordinate computations in distributed algorithms. In particular, we formalise the concept and provide a rigorous analysis of phase clocks operating in nested modes. Our arguments are also valid for phase clocks propelled by multiple leaders. The combination of the two results in the first time-space efficient leader election algorithm. We also provide a complete formal argumentation, indicating that our solution is always correct, fast, and it works with high probability.