Key points are not available for this paper at this time.
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 (n) states per agent and, with high probability, O (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^11) 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 n) using O (k + 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 n + ² 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 n + n). This improves the time to O (n / x_ n + ² 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).
Bankhamer et al. (Fri,) studied this question.