Limit Laws for Consensus Protocols on the Complete Graph
Julian Becker, Konstantinos Panagiotou · 2026
Read Limit Laws for Consensus Protocols on the Complete Graph by Julian Becker, Konstantinos Panagiotou (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19131.txt.
Introduction
Julian Becker and Konstantinos Panagiotou study consensus on a network where each vertex holds one of two opinions. Vertices sample neighbours at random and update by a rule such as k-majority, even with an adversary flipping a few opinions per round. They give limit laws for agreement time and the winning opinion, for many rules and any starting mix. Agreement time centers on a log scale formula, and its centered form never settles, turning periodic on both scales. For k-majority, they give the key constant in closed form.
Catalog record
| CREATOR | Julian Becker, Konstantinos Panagiotou |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 90941 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.19131
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Limit Laws for Consensus Protocols on the Complete Graph Julian Becker, Konstantinos Panagiotou Abstract We study a distributed consensus problem on a complete communication network of n 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 f depending on the sampled opinions. A prominent example is the k k -maj protocol, where every vertex adopts the majority opinion of k k randomly sampled neighbors. We consider the runtime R n R_{n} that is the number of rounds until all vertices agree on the same opinion, which we call the dominating opinion D n D_{n} . In our main result we describe the limiting distributions of these two key quantities for a large class of update functions f f , for arbitrary initial configurations and under the presence of an adversary who may alter the opinions of up to o ( n ) o(\sqrt{n}) vertices in each round. We show that there are f f -specific constants γ , m > 0 \gamma,m>0 such that R n R_{n} centers around μ n = 1 2 log γ n + log m ln n \mu_{n}=\frac{1}{2}\log_{\gamma}n+\log_{m}\ln n , and we describe the asymptotic distribution of R n − μ n R_{n}-\mu_{n} . In particular, we show that it does not converge, and that it becomes asymptotically periodic both in the log n \log n as well as the log log n \log\log n scale. Applied to k k -maj , our results show, among other things, that γ k -maj = ( k − 1 ⌊ k / 2 ⌋ ) 2 1 − k k ∼ ( 2 k / π ) 1 / 2 \gamma_{\texttt{$k$-maj}}=\binom{k-1}{\lfloor k/2\rfloor}2^{1-k}k\sim({2k}/{\pi})^{1/2} . Keywords: Consensus, Majority, Gossip Model, Limiting distribution 1 Introduction In this paper we provide a tight analysis for the runtime of a large class of consensus protocols on fully connected networks that includes the well-studied k -maj ( k -majority) protocol. In particular, we describe the limiting distribution of the runtime and of the eventually dominating opinion in a general setting, where there is (not necessarily) a dominating opinion in the beginning, and where there might be adversarial changes to the opinion distribution. The study of consensus protocols and related probabilistic dynamics – where vertices in a network exchange information, synchronously or asynchronously, possibly in the presence of noise, in order to reach consensus – has attracted extensive attention not only within distributed computing, but also among other disciplines, where opinion forming and synchronization are relevant primitives. The literature is vast, and we refer to the extensive overview by Becchetti et. al. [ 4 ] for a broad discussion and many further references, and to the subsequent sections. Example: k -maj . Before we proceed to our general model we give a brief demonstration of our results in the case of the k -maj protocol, which is defined on a complete communication network of n vertices, each holding one of two opinions that we call X and Y . The vertices communicate in rounds, where everyone samples independently k neighbors uniformly at random and adopts the majority opinion among them, breaking ties uniformly. Let R_{n}^{\texttt{$k$-maj}}(X_{0}) be the runtime , i.e., the number of rounds until all vertices hold the same opinion, where X_{0} is the initial number of vertices holding X . Moreover, let D_{n}^{\texttt{$k$-maj}}(X_{0}) be the dominating opinion at the end of the process. Majority protocols have been studied extensively, a small sample is [ 2 , 5 , 3 ] . Berenbrink et al. show in [ 6 ] that R_{n}^{\texttt{$k$-maj}}(X_{0}) stochastically dominates R_{n}^{\texttt{$\ell$-maj}}(X_{0}) for \ell>k , so that the runtime should decline with increasing k . Moreover, Ghaffari and Lengler [ 21 ] establish that, with probability 1-n^{-O(1)} , 3 -maj finishes in O(\ln n) rounds, which then implies that k -maj reaches consensus in logarithmic time for any k\geq 3 . Yet, the magnitude of the speedup and the precise effect of k are not clear. In the following, and throughout the paper, we use the abbreviation whp (with high probability) to denote events that occur with probability 1-o(1) . Different notions of whp appear in the literature, e.g. with probability 1-n^{-O(1)} as before, but we will not distinguish between them here. Let k\geq 3 and X_{0}=n/2+d\sqrt{n} , where 0\leq d\leq(1/2-\varepsilon)\sqrt{n} for some 0<\varepsilon\leq 1/2 . This assumption is not restrictive. Indeed, if X is initially the minority opinion, we can just swap X and Y to guarantee that d\geq 0 . Moreover, if d=(1+o(1))\sqrt{n} , then already at the beginning a vanishing fraction of the vertices has opinion Y , which is not so interesting. Let m=\lceil k/2\rceil,\quad\beta=\binom{k}{\lfloor k/2\rfloor}\quad\text{and}\quad\gamma=\binom{k-1}{\lfloor k/2\rfloor}2^{1-k}k. We say that a sequence of random variables (W_{n})_{n\in\mathbb{N}_{0}} is stochastically bounded by (a_{n})_{n\in\mathbb{N}_{0}} , and we write W_{n}=O_{\mathbb{P}}(a_{n}) , if for every \varepsilon>0 there exists C_{\varepsilon},n_{\varepsilon} such that \mathbb{P}(|W_{n}|\geq C_{\varepsilon}a_{n})\leq\varepsilon for every n\geq n_{\varepsilon} . Set \mu_{n}^{\text{$k$-maj}}(d):=\begin{cases}\frac{1}{2}\log_{\gamma}n+\log_{m}\ln n,&\text{if }d=O(1),\\[2.84526pt] \frac{1}{2}\log_{\gamma}(n/d^{2})+\log_{m}\ln n,&\text{if }d=\omega(1).\end{cases} Our main result, Theorem 1.3 , implies that R_{n}^{\texttt{$k$-maj}}(X_{0})=\mu_{n}^{\texttt{$k$-maj}}(d)+O_{\mathbb{P}}(1), that is, the runtime has stochastically bounded fluctuations around \mu_{n}^{\texttt{$k$-maj}}(d) . Actually, our results imply more. If d=\omega(1) , in which case there is already a substantial initial bias towards X , then we can show that the runtime concentrates on at most three values. Moreover, whp D_{n}^{\texttt{$k$-maj}}(X_{0})=X in that case. On the other hand, if d=O(1) , the picture (and the analysis) is more intricate, as the process has initially no/very small drift. Here we describe and provide qualitative information about the limiting distribution of R_{n}^{\texttt{$k$-maj}}(X_{0})-\lfloor\mu_{n}^{\texttt{$k$-maj}}(d)\rfloor , which has support on all \mathbb{Z} , see Section 1.1 . Moreover, in this case the two opinions perform a race, and both have a chance to prevail; to wit, we obtain completely explicit that \mathbb{P}\big(D_{n}^{\texttt{$k$-maj}}(X_{0})=X\big)=\sqrt{\frac{2(\gamma^{2}-1)}{\pi}}\int_{0}^{\infty}e^{-2(\gamma^{2}-1)(t-d)^{2}}dt+o(1)\in(0,1). Thus, our results enable us to perform a fine-grained runtime analysis and a qualitative comparison of majority protocols for all values of k . Let us also mention that our analysis is robust enough and leaves enough margin that it allows for small changes in the model, namely adversarial interventions of order o(\sqrt{n}) in each round. We make this more precise in the following section. 1.1 Model & Results Let f:[0,1]\rightarrow[0,1] be, for the moment, an arbitrary function. We associate to f a consensus protocol that is a stochastic process (X_{t})_{t\in\mathbb{N}_{0}} with initial configuration X_{0}=\frac{n}{2}+d\sqrt{n}+o(\sqrt{n}). Thus, at t=0 , there are X_{0} vertices holding opinion X , and there is an initial bias of d\sqrt{n} (vertices). As we will see, the most interesting and complex case is when d is bounded and independent of n , since then the process moves just a little or even not at all in expectation; if, on the other hand, the initial bias is larger, then our analysis applies as well but starts already in a ’simpler’ situation. Now f comes into play. Given X_{t} , the probability that a specific vertex has opinion X at time t+1 is given