Consensus Speed Ruled by Maximum Initial Opinion Density in 3-Majority & 2-Choices

Researchers have pinpointed the fundamental parameter controlling how fast two classic distributed consensus algorithms—3-Majority and 2-Choices—agree on a complete graph. In a new preprint on arXiv, Niccolò D'Archivio (COATI, I3S, Université Côte d'Azur) proves that the convergence time is dictated not by the total number of initial opinions or their squared ℓ2 norm, but by the single largest initial opinion density (the maximum entry of the initial frequency vector, ||α(0)||_∞).

The results are tight: for 3-Majority, consensus occurs in Θ(min{||α(0)||_∞^{-1}, √n}) rounds with high probability, while 2-Choices converges in exactly Θ(||α(0)||_∞^{-1}) rounds. Prior work (Shimizu & Shiraga, PODC'25) gave matching bounds only for specific initial configurations; this new analysis shows the bounds hold up to logarithmic factors for any starting distribution. The paper thus establishes a clean, local parameter that unifies understanding of both dynamics on complete graphs.

For distributed systems engineers, this means the speed of reaching agreement can be predicted simply by knowing the strength of the most popular initial opinion—a far simpler metric than previously assumed. The work also highlights the nuanced difference between 3-Majority and 2-Choices: while 2-Choices depends linearly on the inverse of maximum density, 3-Majority's speed is capped by √n when the dominant opinion is very strong, revealing a trade-off between robustness and speed.