Almost Logarithmic-Time Space Optimal Leader Election in Population Protocols
Leszek Antoni Gąsieniec, Grzegorz Stachowiak, Przemysław Uznański · 2019
The model of population protocols refers to a large collection of simple indistinguishable entities, frequently called \em agents. The agents communicate and perform computation through pairwise interactions. We study fast and space efficient leader election in population of cardinality n governed by a random scheduler, where during each time step the scheduler uniformly at random selects for interaction exactly one pair of agents. We present the first $o(łog^2)$-time leader election protocol. It operates in expected parallel time $\bigo(łog nłogłog n)$ which is equivalent to $\bigo(n łog nłogłog n)$ pairwise interactions. This is the fastest currently known leader election algorithm in which each agent utilises asymptotically optimal number of $\bigo(łogłog n)$ states. The new protocol incorporates and amalgamates successfully the power of assorted \em synthetic coins with variable rate \em phase clocks.