Abstract
We consider distributed plurality consensus in a complete graph of size $n$ with $k$ initial opinions. We design an efficient and simple protocol in the asynchronous communication model that ensures that all nodes eventually agree on the initially most frequent opinion. In this model, each node is equipped with a random Poisson clock with parameter $\lambda=1$. Whenever a node's clock ticks, it samples some neighbors, uniformly at random and with replacement, and adjusts its opinion according to the sample. A prominent example is the so-called two-choices algorithm in the synchronous model, where in each round, every node chooses two neighbors uniformly at random, and if the two sampled opinions coincide, then that opinion is adopted. This protocol is very efficient and well-studied when $k=2$. If $k=O(n^\varepsilon)$ for some small $\varepsilon$, we show that it converges to the initial plurality opinion within $O(k \cdot \log{n})$ rounds, w.h.p., as long as the initial difference between the largest and second largest opinion is $\Omega(\sqrt{n \log n})$. On the other side, we show that there are cases in which $\Omega(k)$ rounds are needed, w.h.p. One can beat this lower bound in the synchronous model by combining the two-choices protocol with randomized broadcasting. Our main contribution is a non-trivial adaptation of this approach to the asynchronous model. If the support of the most frequent opinion is at least $(1+\varepsilon)$ times that of the second-most frequent one and $k=O(\exp(\log{n}/\log \log{n}))$, then our protocol achieves the best possible run time of $O(\log n)$, w.h.p. We relax full synchronicity by allowing $o(n)$ nodes to be poorly synchronized, and the well synchronized nodes are only required to be within a certain time difference from one another. We enforce this synchronicity by introducing a novel gadget into the protocol.
Introduction
In distributed computing, plurality consensus is the fundamental task of reaching a network-wide agreement on the opinion initially held by the largest group. While this problem is well-understood in synchronous models—where nodes operate in lockstep rounds—real-world networks are inherently asynchronous. In such environments, nodes operate based on independent internal clocks, leading to challenges like clock drift and coordination bottlenecks. This paper addresses the "$k$-opinion bottleneck," where the time to reach consensus typically scales linearly with the number of initial opinions ($k$). We present a novel protocol that achieves optimal $O(\log n)$ convergence in an asynchronous setting, even with a large number of initial opinions.
The Challenge of Asynchrony
In the asynchronous model, each node follows a Poisson clock with parameter $\lambda=1$. This means nodes do not share a global round counter; instead, they "tick" and act at random intervals. This introduces two primary difficulties:
- Drift: Nodes may tick at different rates, making it difficult to coordinate multi-phase algorithms that rely on simultaneous transitions.
- The $k$-Opinion Bottleneck: Standard protocols like "Two-Choices"—where a node adopts an opinion only if two sampled neighbors agree—perform well for two opinions but slow down significantly as $k$ increases, often requiring $\Omega(k)$ time to resolve.
Methodology
Analyzing Two-Choices
The authors first provide a rigorous analysis of the standard Two-Choices protocol. In a synchronous setting, they show it converges in $O(k \log n)$ rounds. However, they also prove a lower bound of $\Omega(k)$ for certain cases, demonstrating that simple sampling is insufficient for high-speed consensus when many opinions are present.
The OneExtraBit Mechanism
To break the $\Omega(k)$ barrier, the authors propose the "OneExtraBit" mechanism. In this approach, nodes use a single bit of memory to signal whether they have recently updated their opinion. This effectively combines the stability of the Two-Choices protocol with the speed of rumor-spreading (broadcasting). When a plurality opinion begins to dominate, this extra bit allows it to "flood" the network more rapidly than standard sampling would allow.
The Sync Gadget
The core contribution is the adaptation of this logic to the asynchronous model through a "Sync Gadget." To manage clock drift, the authors introduce a relaxation called Weak Synchronicity. In this state, the vast majority of nodes ($1-o(1)$) remain roughly aligned in time, while a small fraction of "bad" nodes can be significantly out of sync.
The Sync Gadget works by having nodes periodically sample the internal "tick counts" of their neighbors. A node then updates its own internal "working time" to the median value of the samples. Because the median is robust to outliers, a small number of extremely fast or slow nodes cannot disrupt the progress of the majority. This keeps the network moving through the protocol phases in a coordinated fashion without requiring a global clock.
Key Results
The proposed protocol achieves several theoretical milestones:
- Optimal Runtime: It reaches plurality consensus in $\Theta(\log n)$ time with high probability, which is asymptotically optimal for gossip-based protocols.
- Opinion Scaling: The protocol remains efficient even as the number of initial opinions grows, specifically up to $k = O(\exp(\log n / \log \log n))$.
- Robustness: The system maintains stability and reaches the correct consensus even if $o(n)$ nodes are poorly synchronized, provided the initial plurality has a lead of at least $(1 + \epsilon)$ over the runner-up.
- Quadratic Growth: The analysis shows that the gap between the plurality opinion and its rivals grows quadratically in each phase, driving the logarithmic convergence.
Conclusion
This work bridges the gap between synchronous and asynchronous plurality consensus. By introducing the Sync Gadget and a robust median-based timing mechanism, the authors demonstrate that optimal $O(\log n)$ convergence is possible even in the presence of clock drift and numerous initial opinions.
Future research may look to extend these results beyond complete graphs to more complex network topologies, such as expander graphs. Additionally, narrowing the gap between the current opinion limit and the $k = O(n^\varepsilon)$ handled by synchronous models remains an open theoretical challenge.
Summary updated