Population Protocols for Exact Plurality Consensus -- How a small chance of failure helps to eliminate insignificant opinions

We consider the exact plurality consensus problem for population protocols. Here, n anonymous agents start each with one of k opinions. Their goal is to agree on the initially most frequent opinion (the plurality opinion) via random, pairwise interactions. The case of $k = 2$ opinions is known as the majority problem. Recent breakthroughs led to an always correct, exact majority population protocol that is both time- and space-optimal, needing O(log n) states per agent and, with high probability, O(log n) time~[Doty, Eftekhari, Gasieniec, Severson, Stachowiak, and Uznanski; 2021]. We know that any always correct protocol requires Ω(k²) states, while the currently best protocol needs O(k¹¹) states~[Natale and Ramezani; 2019]. For ordered opinions, this can be improved to O(k⁶)~[Gasieniec, Hamilton, Martin, Spirakis, and Stachowiak; 2016]. We design protocols for plurality consensus that beat the quadratic lower bound by allowing a negligible failure probability. While our protocols might fail, they identify the plurality opinion with high probability even if the bias is $1$. Our first protocol achieves this via $k-1$ tournaments in time O(k · log n) using O(k + log n) states. While it assumes an ordering on the opinions, we remove this restriction in our second protocol, at the cost of a slightly increased time O(k · log n + log² n). By efficiently pruning insignificant opinions, our final protocol reduces the number of tournaments at the cost of a slightly increased state complexity O(k · loglog n + log n). This improves the time to O(n / xₘₐₓ · log n + log² n), where xₘₐₓ is the initial size of the plurality. Note that n/xₘₐₓ is at most k and can be much smaller (e.g., in case of a large bias or if there are many small opinions).