pith. sign in

arxiv: 2606.11778 · v2 · pith:ER2I42O7new · submitted 2026-06-10 · 💻 cs.DC

Consensus Time in 3-Majority and 2-Choices Is Determined by the Maximum Initial Opinion Density

Niccol\`o D Archivio (COATI , I3S , UniCA) This is my paper

Pith reviewed 2026-06-27 08:40 UTC · model grok-4.3

classification 💻 cs.DC
keywords consensus time3-majority dynamics2-choices dynamicsopinion frequency vectormaximum densitycomplete graphsynchronous modelhigh-probability bounds
0
0 comments X

The pith

Maximum initial opinion density sets the consensus time for 3-Majority and 2-Choices dynamics.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes tight bounds showing that consensus time in both dynamics depends on the single largest initial opinion frequency rather than the total number of opinions or the overall distribution shape. On the complete graph, 3-Majority reaches agreement in roughly the minimum of the inverse of that maximum frequency and the square root of the population size, while 2-Choices takes time proportional to the inverse of the maximum frequency. These bounds hold with high probability for every possible starting frequency vector. The result replaces earlier reliance on global parameters with a local density measure that directly limits how fast any opinion can be eliminated.

Core claim

We show that 3-Majority reaches consensus in ilde{\Theta}(\min\{\|\alpha^{(0)}\|_\infty^{-1},\sqrt n\}) rounds w.h.p., while 2-Choices reaches consensus in ilde{\Theta}(\|\alpha^{(0)}\|_\infty^{-1}) rounds w.h.p. The convergence time of both dynamics is governed not by global parameters such as the number of opinions k or the squared \ell_2 norm of the initial opinion distribution, but rather by the local parameter \|\alpha^{(0)}\|_\infty, the maximum initial opinion density.

What carries the argument

The maximum entry \|\alpha^{(0)}\|_\infty of the initial opinion-frequency vector, which directly determines the tight convergence-time bounds for both dynamics.

If this is right

  • Consensus time is independent of the total number of opinions k.
  • The bounds are tight for every initial configuration rather than only for some configurations.
  • 3-Majority time is additionally capped at order sqrt n while 2-Choices has no such cap.
  • Previous global measures such as squared L2 norm no longer control the speed.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same local-density dependence may appear in other majority-based processes once the graph is no longer complete.
  • Eliminating one opinion at a time may be the rate-limiting step when the densest opinion is sparse.
  • Real-world networks with heterogeneous degrees could be tested to check whether max initial density still dominates observed agreement times.

Load-bearing premise

The dynamics run on the complete graph under the synchronous model, and the stated high-probability bounds apply without further restrictions to every possible initial frequency vector.

What would settle it

An initial frequency vector where the observed number of rounds to consensus for 3-Majority falls outside the min of inverse max density and square root of n, or for 2-Choices falls outside inverse max density, with high probability.

Figures

Figures reproduced from arXiv: 2606.11778 by I3S, Niccol\`o D Archivio (COATI, UniCA).

Figure 1
Figure 1. Figure 1: A heatmap of the ratio γ0/m0 for all possible initial configurations with three opinions. The corners of the triangle correspond to monochromatic configurations, where m0 = γ0 = 1. The centre of the triangle corresponds to the perfectly balanced configuration, where m0 = γ0 = 1/3. The lower γ0/m0 the more unbalanced the configuration is. 1.1 Our Contribution We show that the correct parameter governing the… view at source ↗
Figure 2
Figure 2. Figure 2: Comparison of consensus time between 3-Majority, 2-Choices, and Undecided-State [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
read the original abstract

We establish the correct parameter governing the convergence time of the 3-Majority and 2-Choices dynamics on the complete graph in the synchronous model. Recent work [Shimizu and Shiraga, PODC'25] provides matching upper and lower bounds on the number of rounds to consensus, but only in a weak sense: the bounds are shown to coincide for some initial opinion configuration. In contrast, we obtain tight bounds in a strong sense, with upper and lower bounds matching up to logarithmic factors for every initial configuration. Let $\alpha^{(0)}$ be the initial opinion-frequency vector, and denote by $\|\alpha^{(0)}\|\_\infty$ its maximum entry. We show that 3-Majority reaches consensus in $\tilde{\Theta}(\min\{\|\alpha^{(0)}\|\_\infty^{-1},\sqrt n\})$ rounds w.h.p., while 2-Choices reaches consensus in $\tilde{\Theta}(\|\alpha^{(0)}\|\_\infty^{-1})$ rounds w.h.p. Our results demonstrate that the convergence time of both dynamics is governed not by global parameters such as the number of opinions $k$ or the squared $\ell\_2$ norm of the initial opinion distribution, but rather by the ``local'' parameter $\|\alpha^{(0)}\|\_\infty$, the maximum initial opinion density.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript establishes strong-sense tight bounds (up to logarithmic factors, for every initial configuration) on the consensus time of the 3-Majority and 2-Choices dynamics on the complete graph in the synchronous model. It proves that 3-Majority reaches consensus in ilde{\Theta}(\min\{\|\alpha^{(0)}\|_\infty^{-1}, \sqrt{n}\}) rounds w.h.p. and 2-Choices in ilde{\Theta}(\|\alpha^{(0)}\|_\infty^{-1}) rounds w.h.p., showing that the governing parameter is the local maximum initial opinion density rather than global quantities such as k or \|\alpha\|_2^2. This strengthens prior weak-sense matching bounds that held only for some configurations.

Significance. If the proofs are correct, the result is significant: it supplies the first strong-sense characterization of convergence time for these dynamics, identifies the correct local parameter, and cleanly separates the 3-Majority case (capped by \sqrt{n}) from the 2-Choices case. The work also supplies machine-checkable or reproducible elements only if the full proofs contain explicit concentration bounds; otherwise the contribution remains the parameter identification itself.

minor comments (3)
  1. [Abstract] Abstract, line 3: the citation '[Shimizu and Shiraga, PODC'25]' should be expanded to a full bibliographic entry; the year 2025 appears forward-looking and should be verified against the actual publication date.
  2. [Abstract] The notation \|\alpha^{(0)}\|_\infty is introduced without an explicit definition of the opinion-frequency vector \alpha^{(0)} in the abstract; a one-sentence reminder of its normalization (sum to 1, non-negative entries) would aid readers.
  3. [Theorem statements] The phrase 'w.h.p.' is used without specifying the probability bound (e.g., 1-1/n^c); while conventional, an explicit statement in the theorem statements would remove ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary and recommendation of minor revision. The report identifies the contribution accurately and raises no specific major comments requiring point-by-point rebuttal. We are prepared to address any minor editorial or clarification requests in the revised version.

Circularity Check

0 steps flagged

No significant circularity; derivation is independent analysis

full rationale

The paper derives tight high-probability bounds on consensus time for 3-Majority and 2-Choices via direct analysis of the synchronous complete-graph model. The claimed governing parameter ||α⁰||_∞ emerges from the proof structure rather than being presupposed or fitted; upper/lower bounds are shown to match for arbitrary initial α⁰ without reducing any quantity to a self-referential definition or to a fitted subset. The cited prior work (Shimizu-Shiraga) is external and used only for contrast, not as a load-bearing uniqueness theorem. No self-citation chains, ansatzes smuggled via citation, or renaming of known empirical patterns appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on the standard modeling assumptions of the complete graph and synchronous updates; no free parameters, invented entities, or non-standard axioms are mentioned.

axioms (2)
  • domain assumption The underlying graph is the complete graph on n nodes.
    The dynamics and bounds are stated for the complete graph.
  • domain assumption Updates occur in the synchronous model.
    The model is explicitly identified as synchronous.

pith-pipeline@v0.9.1-grok · 5782 in / 1529 out tokens · 20850 ms · 2026-06-27T08:40:02.786363+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 17 canonical work pages · 1 internal anchor

  1. [1]

    Fast convergence of k-opinion undecided state dynamics in the population protocol model

    Talley Amir, James Aspnes, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser, and John Lazarsfeld. Fast convergence of k-opinion undecided state dynamics in the population protocol model. In Rotem Oshman, Alexandre Nolin, Magnús M. Halldórsson, and Alkida Balliu, editors,Proceedings of the 2023 ACM Symposium on Principles of Distributed ...

    work page doi:10.1145/3583668.3594589 2023

  2. [2]

    A simple population protocol for fast robust approximate majority.Distributed Comput., 21(2):87–102, 2008

    Dana Angluin, James Aspnes, and David Eisenstat. A simple population protocol for fast robust approximate majority.Distributed Comput., 21(2):87–102, 2008. URL:https: //doi.org/10.1007/s00446-008-0059-z, doi:10.1007/S00446-008-0059-Z

    work page doi:10.1007/s00446-008-0059-z 2008

  3. [3]

    Fast consensus via the unconstrained unde- cided state dynamics

    Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hossein- pour, Dominik Kaaser, and Peter Kling. Fast consensus via the unconstrained unde- cided state dynamics. In Joseph (Seffi) Naor and Niv Buchbinder, editors,Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Con- ference / Alexandria, VA, ...

    work page doi:10.1137/1.9781611977073.135 2022

  4. [4]

    Consensus dynamics: An overview

    Luca Becchetti, Andrea Clementi, and Emanuele Natale. Consensus dynamics: An overview. SIGACT News, 51(1):58–104, March 2020.doi:10.1145/3388392.3388403. 17

    work page doi:10.1145/3388392.3388403 2020

  5. [5]

    Plurality consensus in the gossip model

    Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Riccardo Silvestri. Plurality consensus in the gossip model. In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 371–390, 2016.doi:10. 1137/1.9781611974331.ch28

    2016

  6. [6]

    Simple dynamics for plurality consensus

    Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. Distributed Computing, 30(4):293–306, August 2017.doi:10.1007/s00446-016-0289-4

    work page doi:10.1007/s00446-016-0289-4 2017

  7. [7]

    Stabilizing consensus with many opinions

    Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Stabilizing consensus with many opinions. In Robert Krauthgamer, editor,Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 620–635. SIAM, 2016. URL:https: //doi.org/10.1137/1.97...

    work page doi:10.1137/1.9781611974331.ch46 2016

  8. [8]

    The minority dynamics and the power of synchronicity

    Luca Becchetti, Andrea Clementi, Francesco Pasquale, Luca Trevisan, Robin Vacus, and Isabella Ziccardi. The minority dynamics and the power of synchronicity. In David P. Woodruff, editor,Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024, pages 4155–4176. SIAM, 2024. doi:10.1137/1.97816119...

    work page doi:10.1137/1.9781611977912.144 2024

  9. [9]

    2503.15477

    Petra Berenbrink, Felix Biermeier, and Christopher Hahn. Undecided state dynamics with stubborn agents. CoRR, abs/2406.07335, 2024. URL:https://doi.org/10.48550/arXiv. 2406.07335, arXiv:2406.07335, doi:10.48550/ARXIV.2406.07335

    work page internal anchor Pith review doi:10.48550/arxiv 2024

  10. [10]

    Ignore or comply?: On breaking symmetry in consensus

    Petra Berenbrink, Andrea Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann- Trenn, and Emanuele Natale. Ignore or comply?: On breaking symmetry in consensus. In Elad Michael Schiller and Alexander A. Schwarzmann, editors,Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, Washington, DC, USA, July 25-27, 2017, pages...

    work page doi:10.1145/3087801.3087817 2017

  11. [11]

    On the hierarchy of distributed majority protocols

    Petra Berenbrink, Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, Dominik Kaaser, and Malin Rau. On the hierarchy of distributed majority protocols. In Eshcar Hillel, Roberto Palmieri, and Etienne Rivière, editors, 26th International Conference on Principles of Distributed Systems, OPODIS 2022, December 13-15, 2022, Brussels, Belgium, volume 253 ofLI...

    work page doi:10.4230/lipics.opodis.2022.23 2022

  12. [12]

    A tight analysis of the parallel undecided-state dynamics with two colors

    Andrea Clementi, Mohsen Ghaffari, Luciano Gualà, Emanuele Natale, Francesco Pasquale, and Giacomo Scornavacca. A tight analysis of the parallel undecided-state dynamics with two colors. In Igor Potapov, Paul G. Spirakis, and James Worrell, editors,43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, ...

    work page doi:10.4230/lipics.mfcs.2018.28 2018

  13. [13]

    Asynchronous 3-majority dynamics with many opinions

    Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. Asynchronous 3-majority dynamics with many opinions. In Yossi Azar and Debmalya Panigrahi, editors,Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2025, New Orleans, LA, USA, January 12-15, 2025, pages 4095–4131. SIAM, 2025.doi:10.1...

    work page doi:10.1137/1.9781611978322.140 2025

  14. [14]

    Undecided state dynamics with many opinions, 2026

    Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. Undecided state dynamics with many opinions, 2026. URL:https://arxiv.org/ abs/2603.02636, arXiv:2603.02636. 18

    arXiv 2026

  15. [15]

    Phase transition of a non-linear opinion dynamics with noisy interactions - (extended abstract)

    Francesco D’Amore, Andrea Clementi, and Emanuele Natale. Phase transition of a non-linear opinion dynamics with noisy interactions - (extended abstract). In Andréa Werneck Richa and Christian Scheideler, editors,Structural Information and Communication Complexity - 27th International Colloquium, SIROCCO 2020, Paderborn, Germany, June 29 - July 1, 2020, Pr...

    work page doi:10.1007/978-3-030-54921-3 2020

  16. [16]

    Phase transition of a nonlinear opinion dynamics with noisy interactions

    Francesco D’Amore, Andrea Clementi, and Emanuele Natale. Phase transition of a nonlinear opinion dynamics with noisy interactions. Swarm Intell., 16(4):261–304, 2022. URL: https://doi.org/10.1007/s11721-022-00217-w, doi:10.1007/S11721-022-00217-W

    work page doi:10.1007/s11721-022-00217-w 2022

  17. [17]

    , TITLE =

    David A. Freedman. On tail probabilities for martingales. The Annals of Probability, 3(1):100–118, 1975.doi:10.1214/aop/1176996452

    work page doi:10.1214/aop/1176996452 1975

  18. [18]

    In PODC ’18: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing pp

    Mohsen Ghaffari and Johannes Lengler. Nearly-tight analysis for 2-choice and 3-majority consensusdynamics. InProceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 305–313, 2018.doi:10.1145/3212734.3212738

    work page doi:10.1145/3212734.3212738 2018

  19. [19]

    3-majority and 2-choices with many opinions

    Nobutaka Shimizu and Takeharu Shiraga. 3-majority and 2-choices with many opinions. CoRR, abs/2503.02426, 2025. arXiv:2503.02426, doi:10.48550/arXiv.2503.02426

    work page doi:10.48550/arxiv.2503.02426 2025

  20. [20]

    Étude critique de la notion de collectif

    Jean Ville. Étude critique de la notion de collectif. Gauthier-Villars, 1939. URL: http: //eudml.org/doc/192893. 19

    1939