pith. sign in

arxiv: 2605.19131 · v1 · pith:IVNXXICEnew · submitted 2026-05-18 · 🧮 math.CO · math.PR

Limit Laws for Consensus Protocols on the Complete Graph

Julian Becker , Konstantinos Panagiotou This is my paper

Pith reviewed 2026-05-20 08:38 UTC · model grok-4.3

classification 🧮 math.CO math.PR
keywords consensus protocolscomplete graphsruntime analysislimit lawsadversarial noisemajority protocolsdistributed systemsMarkov chains
0
0 comments X

The pith

For consensus protocols on complete graphs, the agreement time centers at half log base gamma of n plus log base m of ln n, with periodic oscillations in the deviation.

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

This paper determines the precise asymptotic behavior of the consensus time in distributed systems on the complete graph with n nodes. For update functions f in a broad regular class, the runtime R_n is shown to be centered at μ_n = (1/2) log_γ n + log_m ln n, where γ and m are constants specific to f. The distribution of R_n minus this center does not converge to a limit but instead exhibits periodic behavior on the logarithmic and double-logarithmic scales. The findings apply to any starting configuration and continue to hold when an adversary alters up to o(sqrt(n)) opinions each round, offering exact characterizations of convergence speed in noisy distributed environments.

Core claim

The number of rounds R_n until all nodes agree on the dominating opinion D_n satisfies R_n = μ_n + o(1) in probability where μ_n = (1/2) log_γ n + log_m ln n for f-dependent γ, m > 0, but more precisely the centered random variable R_n - μ_n has an asymptotic distribution that is periodic in both the log n scale and the log log n scale; this holds for arbitrary initial opinions and against an adversary modifying o(sqrt(n)) opinions per round.

What carries the argument

The Markov chain model for the evolution of the count of nodes holding the minority opinion, whose transition probabilities are governed by the update function f, from which the growth constant γ and the secondary scale m are derived explicitly.

If this is right

  • For the k-maj protocol, the constant γ equals binom(k-1, floor(k/2)) times 2 to the power 1-k times k, which behaves like the square root of 2k over pi for large k.
  • The limiting distribution of the centered runtime is not a single law but varies periodically depending on the fractional part of log n and log log n.
  • These asymptotic laws are robust to adversarial noise that affects a vanishing fraction of the square root of n nodes each round.
  • The results cover arbitrary initial opinion distributions across the nodes.

Where Pith is reading between the lines

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

  • Practical implementations might observe varying runtimes depending on the exact size n due to the periodic component, suggesting averaging over ranges of n for stable estimates.
  • Analyzing how γ changes with the sampling parameter k in majority protocols could identify optimal k for balancing speed and communication cost.
  • Similar techniques might apply to consensus problems on graphs with different structures, potentially altering the logarithmic factors.

Load-bearing premise

The update function f must belong to a class where the induced Markov chain on opinion counts permits derivation of explicit constants γ and m and yields the periodic limiting distribution for the centered runtime, and this analysis carries through under the given level of adversarial interference.

What would settle it

Simulate the protocol for the three-majority rule starting from balanced opinions, for a sequence of n where log n mod 1 cycles, and verify whether the distribution of R_n - predicted mu_n repeats its shape periodically.

Figures

Figures reproduced from arXiv: 2605.19131 by Julian Becker, Konstantinos Panagiotou.

Figure 1
Figure 1. Figure 1: The left plot depicts the function fk for different k, which is the probability that a vertex adopts opinion X in the case of k-maj. The right plot shows the probability density function of Z occurring in Theorems 1.2 and 1.3 for several k and d = 0. bias, Xt is concentrated around its mean, and so the long-term behavior will be described by iterates of f. Therefore, the assumption that f is convex, behave… view at source ↗
Figure 2
Figure 2. Figure 2: The plot shows an approximation of the function g appearing in the limiting distri￾bution of 3-maj. The continuity and 1−periodicity can be observed (g(0) ≈ 0.45). Thus, with probability 1 − o ⋆ (1), we obtain U = 1 − o ⋆ (1) and L = 1 − o ⋆ (1). It remains to show that the logarithmic terms containing U, L are arbitrarily close. To that end, let ε > 0. For any δ > 0 and sufficiently large a, b ∈ N, there … view at source ↗
read the original abstract

We study a distributed consensus problem on a complete communication network of $n$ vertices, each holding one of two opinions. The vertices communicate in rounds, possibly in the presence of adversarial noise, and exchange information until they all agree on a single opinion. We consider a general class of protocols, where the vertices randomly sample neighbors and update their own opinion according to an update function $f$ depending on the sampled opinions. A prominent example is the $k$-maj protocol, where every vertex adopts the majority opinion of $k$ randomly sampled neighbors. We consider the runtime $R_n$ that is the number of rounds until all vertices agree on the same opinion, which we call the dominating opinion $D_n$. In our main result we describe the limiting distributions of these two key quantities for a large class of update functions $f$, for arbitrary initial configurations and under the presence of an adversary who may alter the opinions of up to $o(\sqrt{n})$ vertices in each round. We show that there are $f$-specific constants $\gamma, m > 0$ such that $R_n$ centers around $\mu_n = \frac{1}{2}\log_\gamma n + \log_m\ln n$, and we describe the asymptotic distribution of $R_n - \mu_n$. In particular, we show that it does not converge, and that it becomes asymptotically periodic both in the $\log n$ as well as the $\log\log n$ scale. Applied to $k$-maj, our results show, among other things, that $\gamma_{k\text{-maj}} = \binom{k-1}{\lfloor k/2 \rfloor}2^{1-k}k \sim ({2k}/{\pi})^{1/2}$.

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

2 major / 3 minor

Summary. The manuscript establishes limit laws for the consensus runtime R_n and dominating opinion D_n in a general class of opinion-update protocols on the complete graph. For update functions f belonging to a regular class, it shows the existence of f-specific constants γ, m > 0 such that R_n is centered at μ_n = (1/2) log_γ n + log_m ln n, and that the distribution of R_n - μ_n does not converge but becomes asymptotically periodic in both the log n and log log n scales. The results are stated to hold for arbitrary initial configurations and under an adversary that may alter o(√n) opinions per round. An explicit formula is derived for γ in the k-maj protocol: γ_{k-maj} = binom(k-1, floor(k/2)) 2^{1-k} k ∼ (2k/π)^{1/2}.

Significance. If the central derivations hold, the results are significant for supplying explicit, locally computable constants γ and m together with a doubly-periodic non-convergent limiting law for consensus time under adversarial noise. The robustness claim for o(√n) perturbations and the concrete asymptotic for k-maj constitute clear strengths that advance the quantitative analysis of distributed consensus beyond qualitative convergence statements.

major comments (2)
  1. [§4.2, Theorem 4.3] §4.2, Theorem 4.3 (perturbation control for periodicity): the claim that o(√n) adversarial flips preserve the exact log log n periodicity of the limiting distribution of R_n - μ_n rests on the minority count remaining above the critical O(√n) threshold throughout the evolution. When the minority reaches O(√n), an adaptive adversary can choose state-dependent flips that shift the effective bias entering the final absorption phase; the manuscript must supply a uniform total-variation or coupling bound that rules out such phase shifts for every admissible adversarial strategy.
  2. [§3.1, Equation (3.4)] §3.1, Equation (3.4) (definition of γ and m): while γ is stated to equal the multiplier g'(1/2) for majority-type f, the passage from the local drift to the global centering constants γ, m requires an explicit error term that remains valid uniformly down to the O(√n) minority regime; without this, the claimed periodicity on the log log n scale is not yet justified for the full range of initial configurations.
minor comments (3)
  1. [Abstract] The abstract asserts that the distribution 'becomes asymptotically periodic both in the log n as well as the log log n scale' without indicating the precise topology (e.g., weak convergence along subsequences or in the space of measures on the circle). A single clarifying sentence would remove ambiguity.
  2. [§2] Notation for the update function f and the sampling procedure in §2 would benefit from a short pseudocode block or a worked numerical example for k=3 to improve readability for readers outside the immediate area.
  3. [References] A few additional references to recent results on absorption-time periodicity in Markov chains (e.g., in branching-process or coupon-collector settings) would help situate the doubly-periodic phenomenon.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and constructive comments on our paper. We address each major comment in detail below. We agree that additional details on the uniformity of the bounds are needed to fully justify the claims for the entire range of the process, and we will incorporate these clarifications in the revised manuscript.

read point-by-point responses

  1. Referee: [§4.2, Theorem 4.3] §4.2, Theorem 4.3 (perturbation control for periodicity): the claim that o(√n) adversarial flips preserve the exact log log n periodicity of the limiting distribution of R_n - μ_n rests on the minority count remaining above the critical O(√n) threshold throughout the evolution. When the minority reaches O(√n), an adaptive adversary can choose state-dependent flips that shift the effective bias entering the final absorption phase; the manuscript must supply a uniform total-variation or coupling bound that rules out such phase shifts for every admissible adversarial strategy.

    Authors: We thank the referee for pointing out this subtlety in the perturbation analysis. In the current manuscript, the control of the adversary is handled by showing that the total number of flips is o(√n) over the relevant time scales, which keeps the minority count from dropping below the threshold too early. However, to rigorously rule out adaptive phase shifts in the final absorption phase, we will add a new lemma providing a uniform coupling bound between the perturbed and unperturbed processes. This bound will show that the total variation distance is o(1) uniformly over all adversarial strategies, thereby preserving the asymptotic periodicity on the log log n scale. We plan to include this in a revised §4.2. revision: yes

  2. Referee: [§3.1, Equation (3.4)] §3.1, Equation (3.4) (definition of γ and m): while γ is stated to equal the multiplier g'(1/2) for majority-type f, the passage from the local drift to the global centering constants γ, m requires an explicit error term that remains valid uniformly down to the O(√n) minority regime; without this, the claimed periodicity on the log log n scale is not yet justified for the full range of initial configurations.

    Authors: The referee correctly identifies that the error analysis in the derivation of the centering constants needs to be uniform down to the O(√n) regime to support the periodicity claims for arbitrary initial configurations. While the local drift analysis around 1/2 provides the leading term for γ and m, the higher-order error terms are currently bounded under the assumption that the minority fraction is bounded away from zero initially. We will revise §3.1 to include an explicit uniform error bound that holds throughout the evolution until the minority reaches O(√n), using martingale concentration and stopping time arguments. This will justify the extension to all initial configurations and strengthen the periodicity result. revision: yes

Circularity Check

0 steps flagged

No circularity: constants derived directly from update rule via Markov chain

full rationale

The derivation proceeds from the Markov chain on opinion counts under the general update function f, yielding explicit constants γ and m (e.g., γ_{k-maj} given by the binomial formula in the abstract) that enter the centering sequence μ_n. These constants are computed from the local drift and are not fitted to the target limit laws, nor obtained via self-citation chains or ansatz smuggling. The periodicity claims follow from the chain's analysis for arbitrary initials and o(√n) perturbations; no step equates a prediction to its input by construction. The paper is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The analysis rests on standard probabilistic tools for Markov chains on opinion counts and local update rules; no free parameters are introduced beyond the f-dependent constants γ and m that are computed from the protocol definition.

axioms (1)
  • domain assumption The opinion-count process can be approximated by a deterministic drift plus fluctuations whose limiting behavior is governed by the local update function f.
    Invoked to obtain the explicit centering sequence μ_n and the periodic limiting law.

pith-pipeline@v0.9.0 · 5851 in / 1435 out tokens · 55180 ms · 2026-05-20T08:38:48.490539+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · 1 internal anchor

  1. [1]

    Angluin, M

    D. Angluin, M. J. Fischer, and H. Jiang. Stabilizing consensus in mobile networks. InProceed- ings of the Second IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS), pages 37–50, 2006

    work page 2006

  2. [2]

    Becchetti, A

    L. Becchetti, A. Clementi, and E. Natale. Consensus dynamics: An overview.SIGACT News, 51:58–104, 2020

    work page 2020

  3. [3]

    Becchetti, A

    L. Becchetti, A. Clementi, E. Natale, F. Pasquale, R. Silvestri, and L. Trevisan. Simple dy- namics for plurality consensus. InProceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 247–256, 2014

    work page 2014

  4. [4]

    Becchetti, A

    L. Becchetti, A. Clementi, E. Natale, F. Pasquale, and L. Trevisan. Stabilizing consensus with many opinions. InProceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 620–635, 2016

    work page 2016

  5. [5]

    Berenbrink, A

    P. Berenbrink, A. Clementi, R. Elsässer, P. Kling, F. Mallmann-Trenn, and E. Natale. Ignore or comply? on breaking symmetry in consensus. InProceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 335–344, 2017

    work page 2017

  6. [6]

    Berenbrink, A

    P. Berenbrink, A. Coja-Oghlan, O. Gebhard, M. Hahn-Klimroth, D. Kaaser, and M. Rau. On the hierarchy of distributed majority protocols. In26th International Conference on Principles of Distributed Systems (OPODIS), pages 23:1–23:19, 2023

    work page 2023

  7. [7]

    Berenbrink, G

    P. Berenbrink, G. Giakkoupis, A.-M. Kermarrec, and F. Mallmann-Trenn. Bounds on the voter model in dynamic networks. InProceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), pages 146:1–146:15, 2016

    work page 2016

  8. [8]

    S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms.IEEE/ACM Trans. Netw., 14:2508–2530, 2006

    work page 2006

  9. [9]

    Cooper, R

    C. Cooper, R. Elsässer, H. Ono, and T. Radzik. Coalescing random walks and voting on graphs. InProceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC), pages 47–56, 2012

    work page 2012

  10. [10]

    Cooper, R

    C. Cooper, R. Elsässer, and T. Radzik. The power of two choices in distributed voting. InPro- ceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), pages 435–446, 2014

    work page 2014

  11. [11]

    Cooper, T

    C. Cooper, T. Radzik, N. Rivera, and T. Shiraga. Fast Plurality Consensus in Regular Ex- panders. In31st International Symposium on Distributed Computing (DISC), pages 13:1–13:16, 2017. 29

    work page 2017

  12. [12]

    Cruciani, E

    E. Cruciani, E. Natale, A. Nusser, and G. Scornavacca. Phase transition of the 2-choices dynamics on core–periphery networks.Distrib. Comput., 34:207–225, 2021

    work page 2021

  13. [13]

    Cruciani, E

    E. Cruciani, E. Natale, and G. Scornavacca. Distributed community detection via metastability of the 2-choices dynamics. InProceedings of the AAAI Conference on Artificial Intelligence, pages 6046–6053, 2019

    work page 2019

  14. [14]

    Daknama, K

    R. Daknama, K. Panagiotou, and S. Reisser. Asymptotics for push on the complete graph. Stochastic Processes and their Applications, 137:35–61, 2021

    work page 2021

  15. [15]

    d’Amore, N

    F. d’Amore, N. D’Archivio, G. Giakkoupis, and E. Natale. On the h-majority dynamics with many opinions. InProceedings of the International Symposium on Distributed Computing (DISC), pages 27:1–27:24, 2025

    work page 2025

  16. [16]

    N. G. de Bruijn. An asymptotic problem on iterated functions.Indagationes Mathematicae (Proceedings), 82:105–110, 1979

    work page 1979

  17. [17]

    Doerr, L

    B. Doerr, L. A. Goldberg, L. Minder, T. Sauerwald, and C. Scheideler. Stabilizing consensus with the power of two choices. InProceedings of the Twenty-Third Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 149–158, 2011

    work page 2011

  18. [18]

    Doerr and A

    B. Doerr and A. Kostrygin. Randomized rumor spreading revisited. InProceedings of the International Colloquium on Automata, Languages, and Programming (ICALP), pages 138:1– 138:14, 2017

    work page 2017

  19. [19]

    Rapid Asynchronous Plurality Consensus

    R. Elsässer, T. Friedetzky, D. Kaaser, F. Mallmann-Trenn, and H. Trinker. Efficient k-party voting with two choices.ArXiv, abs/1602.04667:1–24, 2016

    work page internal anchor Pith review Pith/arXiv arXiv 2016

  20. [20]

    Briefannouncement: Rapid asynchronous plurality consensus

    R.Elsässer, T.Friedetzky, D.Kaaser, F.Mallmann-Trenn, andH.Trinker. Briefannouncement: Rapid asynchronous plurality consensus. InProceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 363–365, 2017

    work page 2017

  21. [21]

    Ghaffari and J

    M. Ghaffari and J. Lengler. Nearly-tight analysis for 2-choice and 3-majority consensus dy- namics. InProceedings of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 305–313, 2018

    work page 2018

  22. [22]

    Goles, P

    E. Goles, P. Medina, P. Montealegre, and J. Santivañez. Majority networks and consensus dynamics.Chaos, Solitons & Fractals, 164:112697, 2022

    work page 2022

  23. [23]

    Hassin and D

    Y. Hassin and D. Peleg. Distributed probabilistic polling and applications to proportionate agreement.Information and Computation, 171:248–268, 2001

    work page 2001

  24. [24]

    Kanade, F

    V. Kanade, F. Mallmann-Trenn, and T. Sauerwald. On coalescence time in graphs: When is coalescing as fast as meeting?ACM Trans. Algorithms, 19:1–46, 2023

    work page 2023

  25. [25]

    Kang and N

    N. Kang and N. Rivera. Best-of-three voting on dense graphs. InThe 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 115–121, 2019

    work page 2019

  26. [26]

    Mohan and P

    D. Mohan and P. Pralat. Asynchronous majority dynamics on binomial random graphs.ACM Trans. Econ. Comput., 13:1–26, 2025

    work page 2025

  27. [27]

    Nakata, H

    T. Nakata, H. Imahayashi, and M. Yamashita. A probabilistic local majority polling game on weighted directed graphs with an application to the distributed agreement problem.Networks, 35:266–273, 2000. 30

    work page 2000

  28. [28]

    Panagiotou and S

    K. Panagiotou and S. Reisser. Asymptotics for pull on the complete graph.Stochastic Processes and their Applications, 159:541–563, 2023

    work page 2023

  29. [29]

    F. Sau. Concentration and local smoothness of the averaging process.Electronic Journal of Probabability, 29:1–26, 2024

    work page 2024

  30. [30]

    Schoenebeck and F.-Y

    G. Schoenebeck and F.-Y. Yu. Consensus of interacting particle systems on erdös-rényi graphs. InProceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1945–1964, 2018

    work page 2018

  31. [31]

    D. Shah. Gossip algorithms.Foundations and Trends in Networking, 3:1–125, 2009

    work page 2009

  32. [32]

    Shimizu and T

    N. Shimizu and T. Shiraga. Phase transitions of best-of-two and best-of-three on stochastic block models.Random Structures & Algorithms, 59:96–140, 2021

    work page 2021

  33. [33]

    Shimizu and T

    N. Shimizu and T. Shiraga. Quasi-majority functional voting on expander graphs.Random Structures & Algorithms, 65:613–643, 2024

    work page 2024

  34. [34]

    Shimizu and T

    N. Shimizu and T. Shiraga. 3-majority and 2-choices with many opinions. InProceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pages 207–217, 2025

    work page 2025

  35. [35]

    A. N. Zehmakan. Opinion forming in erdős–rényi random graph and expanders.Discrete Applied Mathematics, 277:280–290, 2020. 31

    work page 2020