Name
Abstract | ||
|---|---|---|
ABSTRACTWe 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. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1145/3465084.3467898 | PODC |
Keywords | DocType | Citations |
leader election, self-stabilization, population protocols | Conference | 1 |
PageRank | References | Authors |
0.35 | 0 | 7 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Janna Burman | 1 | 123 | 13.55 |
| Ho-Lin Chen | 2 | 354 | 24.97 |
| Hsueh-Ping Chen | 3 | 1 | 1.02 |
| David Doty | 4 | 308 | 23.80 |
| Thomas Nowak | 5 | 1 | 0.35 |
| Eric E. Severson | 6 | 1 | 0.69 |
| Chuan Xu | 7 | 3 | 4.80 |