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

We consider the 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. Exact plurality consensus refers to the requirement that the plurality opinion must be identified even if the bias (difference between the most and second most frequent opinion) is only 1. 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, Uznanski, and Stachowiak; 2021]. Meanwhile, results for general plurality consensus are rare and far from optimal. We know that any always correct protocol requires Omega(k(2)) 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(6)) [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 center dot 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 center dot log n + log(2) 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 center dot log log n + log n). This improves the time to O(n/x(max) center dot log n + log(2) n), where x(max) is the initial size of the plurality. Note that n/x(max) is at most k and can be much smaller (e.g., in case of a large bias or if there are many small opinions).