Efficient k-Party Voting with Two Choices

Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Frederik Mallmann-Trenn, Horst Trinker

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

Plurality consensus is a fundamental problem in distributed computing where a network of $n$ nodes must reach agreement on the most frequent opinion among $k$ initial candidates. While the case of $k=2$ (binary consensus) is well-understood and highly efficient, the problem becomes significantly more complex as the number of opinions increases. Standard protocols, such as the "two-choices" algorithm, often suffer from a performance bottleneck where the time to reach consensus scales linearly with $k$.

Furthermore, most existing high-performance algorithms assume a synchronous model where all nodes act in discrete, simultaneous rounds. In real-world distributed systems, nodes operate asynchronously, driven by independent local clocks. This paper addresses these challenges by introducing a novel asynchronous protocol that breaks the $\Omega(k)$ time barrier, achieving optimal $O(\log n)$ convergence.

The Limitations of Standard Voting

In the traditional synchronous two-choices protocol, each node samples two neighbors and adopts their opinion only if they match. While robust, this process is slow when $k$ is large. We demonstrate that for $k = O(n^\varepsilon)$, the standard two-choices algorithm requires $O(k \log n)$ rounds to converge, and in certain adversarial configurations, it cannot beat $\Omega(k)$.

To overcome this, we look toward the "OneExtraBit" approach. By allowing nodes to transmit a single additional bit of information—indicating whether they have recently changed their opinion—the network can trigger a rumor-spreading mechanism. This allows the plurality opinion to propagate exponentially rather than linearly. However, adapting this to an asynchronous environment where nodes lack a global heartbeat is non-trivial.

Methodology: Asynchronous Adaptation and the Sync Gadget

Our protocol transitions the benefits of synchronous broadcasting into an asynchronous setting using two primary mechanisms:

1. Weak Perpetual Synchronization

We relax the requirement for perfect synchronicity. Our model allows for a small fraction of nodes ($o(n)$) to be poorly synchronized, while the majority remain within a bounded time difference of each other. This "weak" synchronicity is sufficient to maintain the phased structure required for the broadcasting mechanism to function.

2. The Sync Gadget

To maintain this alignment without a global clock, we introduce a "Sync Gadget." Each node tracks its own "working time" based on its local Poisson clock. Periodically, a node samples the clocks of its neighbors. By adopting the median value of these samples, the node can adjust its internal progress. The use of the median is critical; it provides robustness against "outlier" nodes that may be ticking too fast or too slow, preventing them from dragging the rest of the network out of alignment.

3. Tactical Waiting

The protocol incorporates "do-nothing" blocks. These intervals allow lagging nodes to catch up to the rest of the population, ensuring that when the next phase of the voting/broadcasting algorithm begins, a sufficient quorum of nodes is ready to participate.

Key Insights

  • Quadratic Growth: By interleaving voting sub-phases with propagation sub-phases, the gap between the plurality opinion and its competitors grows quadratically in each phase, leading to rapid convergence.
  • The Power of One Bit: The addition of a single bit to signal an opinion change transforms the consensus process from a slow voting exercise into a fast rumor-spreading event.
  • Robustness to Initial Bias: The protocol is effective as long as the initial plurality has a lead of at least $(1+\varepsilon)$ over the second-most frequent opinion, even with a large number of initial opinions $k$.

Results and Conclusion

Our analysis proves that this asynchronous protocol achieves a runtime of $\Theta(\log n)$, which is the theoretical lower bound for gossip-based consensus. This represents a significant improvement over the $\Omega(k)$ runtime of standard asynchronous voting. The protocol is shown to be scalable up to $k = O(\exp(\log n / \log \log n))$ and remains robust against small-scale dynamic perturbations.

While this work focuses on complete graphs, it provides a framework for understanding how "weak synchronicity" can be maintained in distributed systems. Future research may extend these proofs to more complex topologies, such as expander graphs, and explore parameter-free versions of the protocol that do not require prior knowledge of $n$ or $k$.

Summary updated

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.
BibTeX
@misc{elsasser2016efficient,
  author = {Robert Elsässer and Tom Friedetzky and Dominik Kaaser and Frederik Mallmann-Trenn and Horst Trinker},
  title = {{Efficient k-Party Voting with Two Choices}},
  year = {2016},
  eprint = {1602.04667},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1602.04667},
}
Figure