Plurality Consensus for $h$-Majority via First-Repetition Rules

Plurality Consensus for h-Majority via First-Repetition Rules Niccolò D’Archivio1 , George Giakkoupis2 , Frédéric Giroire1 , and Emanuele Natale1

arXiv:2611.16037v1 [cs.DC] 11 Nov 2026

1

COATI, Inria, CNRS, I3S, Université Côte d’Azur, France 2 Inria, Univ Rennes, CNRS, IRISA, France

Abstract In the h-Majority dynamics, each of n agents holds one of k opinions and, in every synchronous round, observes the opinions of h agents chosen independently and uniformly at random and adopts a most frequent one among them, breaking ties uniformly at random. Write M0 for the initial number of agents holding the most frequent opinion, and ∆0 for its bias, its lead over √ the second most frequent opinion. We show that, for every sample size h ≥ 3, if ∆0 ≥ L M0 log n · max{1, n/(h2 M0 )} for a sufficiently large constant L, then h-Majority reaches consensus on the initially most frequent opinion within O((1 + n/(h2 M0 )) log n) rounds with high probability. This is the time bound proved p for the DéjàVu dynamics with ph samples; our bias condition is that of DéjàVu when h ≥ n/M0 , and larger by a factor n/(h2 M0 ) otherwise. Our main contribution is the analysis of one round, which rests on a comparison principle: among all rules that read the same observations and treat opinions symmetrically, plurality maximizes the difference between the probability of outputting the most frequent opinion and that of outputting any fixed competitor. We apply it to the rule that adopts the first opinion repeated among h − 1 observations, and otherwise the h-th observation (which stands in for the agent’s own opinion); its output law is the law of the new opinion of a uniformly random agent after one round of DéjàVu with h − 1 samples. Hence, in expectation, one round of h-Majority increases the gap between the most frequent opinion and each competitor at least as much as that round of DéjàVu, whose analysis we use as a black box. Independently and concurrently, d’Amore, Rybicki, Shimizu, Shiraga and Vacus obtained, p among other results, the same time bound under the weaker bias condition of DéjàVu, ∆0 = Ω( max{M0 , n/h2 } log n), with a different analysis of one round and a martingale analysis over many rounds.

1

Introduction

Plurality consensus asks a population of n agents, initially split among k opinions, to converge to the opinion with the largest initial support [BCN20]. In the h-Majority dynamics [BCN+ 17], in every synchronous round each agent observes the opinions of h agents chosen independently and uniformly at random, and adopts a most frequent opinion among its h observations, breaking ties uniformly at random. Observing h random agents per round is the PULL(h) model [DGM+ 11, BCN+ 16, BCN+ 17]. For h = 3, h-Majority is 3-Majority; for h ≤ 2, it has the transition law of the voter dynamics [HP01], which does not favor any opinion. 3-Majority and the related 2-Choices dynamics [CER14, EFK+ 16], in which an agent adopts the opinion of two random agents if they agree and otherwise keeps its own, are well understood. √ From an arbitrary initial configuration, 3-Majority reaches consensus within Õ(min{k, n}) rounds and 2-Choices within Õ(k) rounds [SS25], improving on [BCN+ 17, BCE+ 17, GL18]; moreover, up to logarithmic factors, the consensus time of either dynamics depends on the initial configuration 1

only through the largest initial opinion density [D’A26]. For general h, Becchetti et al. [BCN+ 17] gave a lower bound of Ω(k/h2 ) rounds for h-Majority, valid for suitable initial configurations close to the uniform one whenever k/h = O(n1/4−ε ) for some constant ε > 0. Let M0 be the initial count of the most frequent opinion, and let ∆0 , its bias, be the difference between M0 and the initial count of the second most frequent opinion. Apart from the concurrent work discussed below, the only upper bound for h-Majority that allows both h and k to grow √ requires very large samples: if M0 = ω(log n), ∆0 = ω( M0 ) and h = ω(n log n/M0 ), then hMajority reaches consensus on the initially most frequent opinion within O(log n) rounds with high probability [dDGN25]. From almost balanced configurations, in which M0 is of order n/k, this condition on the sample size reads h = ω(k log n). The DéjàVu dynamics [dDG+ 26a, dDG+ 26b] replaces counting by repetition detection. In its variant DéjàVu(h) in PU LL(h), an agent reads its h observations of a round in order and adopts the first opinion that it observes twice; if the h observations are pairwise distinct, it keeps + its opinion. p d’Amore et al. [dDG 26b, Theorem 1] showed that, provided M0 = ω(log n) and ∆0 = Ω( max{M0 , n/h2 } log n), DéjàVu(h) brings all agents to the initial plurality opinion within O((1 + n/(h2 M0 )) log n) rounds with high probability. Upper bounds of this kind for h-Majority with smaller samples were left open there. Our results. We show that, for every h ≥ 3, h-Majority has the time bound of DéjàVu(h) (Theorem 1). If the bias satisfies n

∆0 ≥ Lc M0 log n · max 1, p

n o h2 M0

for a sufficiently large constant Lc , then h-Majority reaches consensus on the initially most frequent opinion within   n  log n O 1+ 2 h M0 p √ rounds with high probability. For h ≥ n/M0 , this bias condition reads ∆0 ≥ Lc pM0 log n, as for DéjàVu(h); for smaller h, it exceeds the condition for DéjàVu(h) by the factor n/(h2 M0 ). The main contribution of this note is the analysis of one round: a comparison principle that reduces one round of h-Majority to one round of DéjàVu(h − 1), whose analysis [dDG+ 26b, Lemma 23] we use as a black box. It differs from the analysis of one round in the concurrent work discussed below. We derive Theorem 1 from the one-round estimates with a short round-by-round argument. Concurrent work. Independently and concurrently, d’Amore, Rybicki, Shimizu, Shiraga and Vacus proved the time bound of Theorem 1 under the weaker bias condition r

∆0 = Ω

n

max M0 ,

 no log n h2

[dRS+ 26, Theorem 1.2].1 They also proved that, for every h ≥ 3 and from every initial configuration, h-Majority reaches consensus within √ o  n 1 n Õ 1 + min , 2 min{h M0 /n, 1} h Their detailed statement [dRS+ 26, Theorem 6.1] has success probability at least 1 − 1/n; our proof gives 1 − n−c for every fixed c > 0, with Lc depending on c. 1

2

rounds [dRS+ 26, Theorem 1.1]. Their lower bound for neutral h-input dynamics (fixed, possibly randomized rules that depend only on the h observations and the agent’s current opinion, output one of these h + 1 opinions, and treat opinions symmetrically) matches this bound, as a function of n, h and M0 and for M0 < n, up to polylogarithmic factors [dRS+ 26, Theorem 1.3]. The two analyses differ in the one-round estimate. Theirs bounds the growth of the relative gap q1 /qj − 1 between the output probabilities q1 of the most frequent opinion and qj of a competitor [dRS+ 26, Lemma 3.1], through probability-transport arguments on the vectors of sample counts. Ours bounds the growth of the difference q1 − qj , by comparing plurality with a first-repetition rule, which reduces the estimate to the one-round analysis of DéjàVu [dDG+ 26b]. Their multi-round analysis follows the martingale framework based on Freedman’s inequality that was developed for 3-Majority by Cooper, Mallmann-Trenn, Radzik, Shimizu and Shiraga [CMR+ 25] (in an asynchronous setting) and for 3-Majority and 2-Choices by Shimizu and Shiraga [SS25]. Both works prove that plurality does not decrease the ratio of the most frequent opinion to any other, qj /q1 ≤ pj /p1 (Lemma 3 and [dRS+ 26, Corollary 5.12]). They also compare one round of h-Majority with one round of plurality on fewer observations, through a majorization of output laws [dRS+ 26, Lemma 5.15 and Corollary 5.18], which they use in their final phase with three observations [dRS+ 26, Lemma 6.9], as we do in Lemma 7(e). That comparison is between plurality rules with different numbers of observations. Lemma 4 compares plurality with every label-equivariant rule on the same observations, which is what makes the first-repetition rule, and hence DéjàVu, available. Write q (m) for the output law of plurality on m observations, with opinion 1 a most frequent opinion. Applied to plurality on the first m < h observations, Lemma 4 gives (h) (m) q1 ≥ q1 , the first prefix inequality of their majorization, but not the others. Our analysis of one round (the comparison principle of Lemma 4 and its application to firstrepetition rules) was written up in a draft dated 26 September 2026, before the work of d’Amore et al. [dRS+ 26] appeared on arXiv on 29 October 2026. Approach. The main step is a lower bound on the expected growth, in one round, of the gap between the count of the most frequent opinion and that of each competitor. A heuristic gives the rate of this growth. If opinion 1 has density p1 and a competitor j has density pj , a given pair of observations shows opinion 1 twice with probability p21 and opinion j twice with probability p2j .
Among h observations there are h2 pairs, so repetitions favor opinion 1 over j by about h 2

!

p21 − p2j ≈ h2 p1 (p1 − pj ),

which is h2 p1 times the density gap, as long as h2 p1 ≤ 1. At the initial configuration, p1 = M0 /n, and this rate is the scale min{h2 M0 /n, 1} that appears in the bias condition and in the time bound. The output law of plurality on h observations is a sum over count vectors with no tractable closed form, so we do not compute it. Instead, we use the first-repetition rule Dh , which reads the h observations in order and outputs the first one among the first h − 1 that repeats an earlier one, or the last observation if the first h − 1 are pairwise distinct. Its output law is the law of the next opinion of a uniformly random agent in DéjàVu(h − 1). Indeed, an agent of DéjàVu(h − 1) that sees no repetition among its h − 1 observations keeps its current opinion, and the current opinion of a uniformly random agent is distributed as one more observation, independent of the others. The analysis of DéjàVu [dDG+ 26b, Lemma 23] shows that DéjàVu(h − 1) multiplies, in expectation, the gap to every competitor by 1 + Ω(min{h2 C1 /n, 1}) as long as C1 < 3n/4, where C1 is the current count of the most frequent opinion. A comparison principle (Lemma 4) transfers this amplification to plurality (Lemma 6): among all randomized rules that treat opinions symmetrically and read the 3

same observations, plurality maximizes the difference between the probability of outputting the most likely opinion and that of outputting any fixed competitor. Given these one-round estimates, the analysis over many rounds is short (Section 4). Under the bias condition, Bernstein’s inequality shows that the fluctuations of one round are a small fraction of the expected growth of every gap. Hence, with high probability, every round multiplies the bias by 1 + Ω(min{h2 M0 /n, 1}), does not decrease the count of opinion 1, and preserves the bias condition (Lemma 8). Once at least 3n/4 agents hold opinion 1, the expected number of the other agents decreases by a constant factor in every round (Lemma 9). Section 2 defines the model and states the result, Section 3 analyzes one round of h-Majority, and Section 4 proves Theorem 1.

2

Model, results and tools

Configurations. There are n agents, each holding an opinion in the set [k] = {1, . . . , k}, where 2 ≤ k ≤ n; some opinions may be held by no agent, initially or later. The configuration is C = (C1 , . . . , Ck ), where Ci is the number of agents holding opinion i, and p = C/n is the vector of opinion densities. Primes denote the next round (C ′ and p′ ). Opinion 1 is a largest opinion if C1 = maxi Ci . For every opinion j ̸= 1 we write ∆j = C1 − Cj ,

∆ = min ∆j = C1 − max Cj . j̸=1

j̸=1

When ∆ > 0, opinion 1 is the unique largest opinion, ∆ is its bias, and ∆/C1 is its relative bias. Logarithms are natural. A sequence of events holds with high probability (w.h.p.) if its probability is at least 1 − n−c , where c > 0 is fixed but arbitrary; all constants implicit in O(·) or in “sufficiently large” may depend on c only, and not on n, k, h or the initial configuration. h-Majority in PULL(h). In the PU LL(h) model, time is divided into synchronous rounds. In each round, every agent samples h agents independently and uniformly at random (with replacement, so an agent, possibly itself, may be sampled several times) and learns their current opinions; afterwards all agents update at the same time. In h-Majority, an agent adopts a most frequent opinion among its h observations, breaking ties uniformly at random and independently of everything else; it ignores its current opinion. Since every adopted opinion has just been observed, an opinion held by no agent never returns; in particular, consensus is absorbing. Given a probability vector p on [k] and an integer m ≥ 1, draw m labels independently from p, and select uniformly at random one of the labels that occur most often; the output law of plurality on m draws is the law q = q(p) of the selected label. Given the configuration C, the h observations of an agent are independent draws from p = C/n, independently across agents. Hence, given C, the next opinions of the agents of h-Majority are independent, each with law q(p) for m = h. In particular, given C, the next configuration C ′ has the multinomial distribution with parameters n and q(p); this is the transition law of h-Majority in PULL(h). Its mean is E[Ci′ | C] = n qi (p)

2.1

(i ∈ [k]).

(1)

Result

Theorem 1 (h-Majority in PU LL(h)). For every constant c > 0 there are constants Lc , Ac > 0, depending only on c, such that the following holds. Let n ≥ 2 and 2 ≤ k ≤ n, and let h ≥ 3 be an

4

integer, which may depend on n and on the initial configuration. Suppose that opinion 1 is initially the unique largest opinion, with count M0 and bias ∆0 . If the bias condition n

∆0 ≥ Lc M0 log n · max 1, p

n o h2 M0

(2)

holds, then, with probability at least 1 − n−c , h-Majority in PU LL(h) reaches consensus on opinion 1 within  n  Ac 1 + 2 log n h M0 rounds. Both quantities are governed by the amplification scale α(x) = min

n h2 x

n

o

,1

(x ≥ 0).

Since 1/α(M0 ) = max{1, n/(h2 M0 )}, the bias condition reads α(M0 ) ∆0 ≥ Lc M0 log n, p

and the time bound is O(log n/α(M0 )). For h ≥ n/M0 , we have α(M0 ) = 1: the bias condition √ reads ∆0 ≥ Lc M0 log n, and the time bound is O(log n). Since ∆0 ≤ M0 and α(M0 ) ≤ 1, the bias condition implies M0 ≥ L2c log n, so the theorem needs no separate lower bound on M0 . In our proof, h ≥ 3 is used twice: h-Majority is compared with DéjàVu with h − 1 ≥ 2 samples (Lemma 6), and, once C1 ≥ 3n/4, with plurality on three of its observations (Lemma 7(e)). The restriction h ≥ 3 is needed: for h ∈ {1, 2}, q(p) = p (for h = 2, p2i + pi (1 − pi ) = pi ), so the count of opinion 1 is a bounded martingale, and consensus, which is reached almost surely, is on opinion 1 with probability M0 /n. p

2.2

Bernstein’s inequality

For a sum X of independent random variables Y1 , . . . , YN with |Yi − EYi | ≤ J and Var X ≤ V , Bernstein’s inequality [BLM13, Corollary 2.11], applied to X and to −X, states that Pr(|X − EX| ≥ z) ≤ 2 exp(−z 2 /(2(V + Jz/3))) for every z > 0. We use it in the following form. Lemma 2 (Bernstein’s inequality). Let X = Y1 + · · · + YN be a sum of independent random variables with |Yi − EYi | ≤ J and Var X ≤ V . Then, for every y > 0, Pr |X − EX| ≥ Proof. Let z =

√

p

2V y + Jy ≤ 2e−y .

2V y + Jy. Then p p
2 2 z 2 − 2V y = 2Jy 2V y + J 2 y 2 ≥ Jy 2V y + Jy = Jyz, 3 3

that is, z 2 /(2(V + Jz/3)) ≥ y, and Bernstein’s inequality gives the claim.

3

One round of h-Majority

Throughout this section, p is a probability vector on [k], and q = q(p) is the output law of plurality on h independent draws from p; by (1), nq is the expected configuration after one round of h-Majority from C = np. The goal of the section is Lemma 7, which collects the one-round properties of h-Majority used in Section 4. 5

3.1

Majority boosting

The first property is that plurality preserves the order of the densities and can only increase their ratios. In the terminology of d’Amore et al. [dDG+ 26b], who show that the squared Euclidean norm of the configuration is a submartingale for every such dynamics [dDG+ 26b, Lemma 35], h-Majority with uniform tie-breaking is majority boosting. The next lemma and its proof also appear in [DGGN26], and its claims for a largest label 1 are also proved, for h ≥ 3, in the concurrent work [dRS+ 26, Corollary 5.12]; we include the proof to keep the note self-contained. For a vector P x ∈ Zk≥0 of counts with ℓ xℓ = h, the labels attaining maxℓ xℓ form a set W(x), and label i wins the Q uniform tie-break with probability wi (x) = 1[i ∈ W(x)]/|W(x)|. Writing P (x) = Qh!x ! ℓ pxℓ ℓ (with 00 = 1) for the multinomial probability of x under h draws from p, we have qi =

ℓ ℓ P

x P (x)wi (x).

Lemma 3 (Majority boosting). Let h ≥ 1, and let i, j be labels with pi ≥ pj . Then pj qi ≥ pi qj and qi ≥ qj . If moreover p1 = maxℓ pℓ , then q1 ≥ p1

and

q1 (p1 − pj ) p1

q 1 − qj ≥

for every label j.

Proof. We first prove pj qi ≥ pi qj . This is immediate if i = j, or if pj = 0, since then label j is never drawn and qj = 0. Otherwise write u = pi ≥ v = pj > 0 and d(x) = P (x) vwi (x) − uwj (x) ,

so that

vqi − uqj =

X

d(x).

x

We group the count vectors so that each group has a nonnegative total contribution. For a count vector x, let x̃ be x with its i- and j-counts exchanged. With the counts xℓ , ℓ ∈ / {i, j}, fixed, we have P (x) = F (xi , xj ), where F (a, b) =

κua v b , a! b!

κ = h!

pxℓ ℓ ≥ 0. x ! ℓ ℓ∈{i,j} / Y

Unequal counts. Pair each count vector x with xi ̸= xj with its image x̃, choosing the representative with xi = a > b = xj . Label j is not of maximal count in x, and exchanging the two counts exchanges the selection probabilities of i and j: wj (x) = 0, wi (x̃) = 0 and wj (x̃) = wi (x). Thus d(x) + d(x̃) = wi (x) vF (a, b) − uF (b, a) =

κwi (x) (uv)b+1 ua−b−1 − v a−b−1 ≥ 0, a! b!

since u ≥ v and a − b − 1 ≥ 0. Equal counts. Let xi = xj = a. If i and j are not of maximal count, then d(x) = 0. Otherwise both belong to W(x), so |W(x)| ≥ 2 and wi (x) = wj (x) = 1/|W(x)|; moreover a ≥ 1, since a label of maximal count among h ≥ 1 draws is drawn at least once. Then d(x) = F (a, a)

v−u κ(uv)a (u − v) =− ≤ 0. |W(x)| (a!)2 |W(x)|

To offset this term, let y be x with one draw moved from j to i, so yi = a + 1 and yj = a − 1. Label i is the unique label of maximal count in y, so wi (y) = 1, and the computation for unequal counts, with a + 1 and a − 1 in place of a and b, gives d(y) + d(ỹ) =

κ(uv)a (u − v) a|W(x)| = −d(x) ≥ −d(x), (a + 1)! (a − 1)! a+1

6

since a|W(x)| ≥ 2a ≥ a + 1. Distinct such x give distinct pairs {y, ỹ}, because x is recovered from {y, ỹ} by replacing the i- and j-counts by their average. Every count vector now lies in exactly one of the following groups: a vector x with xi = xj in which i and j are of maximal count, together with its pair {y, ỹ}; a remaining pair {x, x̃} with xi ̸= xj ; a vector with xi = xj in which i and j are not of maximal count. Every group has a nonnegative total contribution, hence vqi − uqj ≥ 0. If pj > 0, this gives qi ≥ (pi /pj )qj ≥ qj ; if pj = 0, then qj = 0 ≤ qi . Now let p1 = maxℓ pℓ , so that p1 > 0. Summing pj q1 − p1 qj ≥ 0 over all labels j gives q1 − p1 ≥ 0. Finally, p1 qj ≤ pj q1 gives q1 − qj ≥ q1 − (pj /p1 )q1 = (q1 /p1 )(p1 − pj ).

3.2

Plurality maximizes the gap to every competitor

A rule that reads m labels and outputs a label, possibly using independent randomness, is labelequivariant if renaming the labels of its input renames its output in the same way: for every permutation ψ of [k] and every s ∈ [k]m , its output on ψ(s) = (ψ(s1 ), . . . , ψ(sm )) has the same law as ψ applied to its output on s. Plurality with uniform tie-breaking is label-equivariant, since relabeling permutes the set of labels of maximal count. The output law of a rule on p is the law of its output when it reads m independent draws from p. Lemma 4 (Plurality maximizes the gap to every competitor). Let p1 = maxℓ pℓ and m ≥ 1. Let r be the output law on p of a label-equivariant rule that reads m labels, and let q be the output law of plurality on m draws from p. Then, for every label j, r1 − rj ≤ q1 − qj ; consequently, r1 ≤ q1 . Plurality on m multinomial draws is the classical single-sample procedure for selecting the most probable cell [BEM59]. The consequence r1 ≤ q1 is the analogue, for one multinomial sample, of the classical optimality of the natural selection rule among rules that treat the candidates symmetrically, which goes back to Bahadur and Goodman [BG52] for independent samples from k populations; see also [Leh66]. The inequality r1 − rj ≤ q1 − qj is what the upper bound needs: to show that plurality amplifies the gap between opinion 1 and a competitor j, it suffices to exhibit one label-equivariant rule on the same draws that does. The proof writes r1 − rj as the expected reward of a rule that earns +1 for outputting opinion 1, −1 for outputting j, and 0 otherwise. This reward is not monotone in the probabilities: if pt < pj for some t ∈ / {1, j}, then t earns more than the more likely opinion j. Therefore it does not suffice to compare two labels by exchanging the probabilities they carry, and case (c) of the proof groups the assignments of probabilities to three labels; it uses that the label output by plurality has the largest count among all observed labels, not only a count at least that of the label it is compared with. Proof. The second claim follows from the first: summing r1 − rj ≤ q1 − qj over all labels j ∈ [k] and P P using j rj = j qj = 1 gives kr1 − 1 ≤ kq1 − 1. For the first claim, the case j = 1 is trivial; let j ̸= 1. We interpret both sides as the expected reward in a guessing game, and show that plurality plays this game optimally after every observation. A guessing game. Call the indices 1, . . . , k roles: role t carries probability pt . Choose a uniformly random permutation π of [k], with the convention that label ℓ carries role π(ℓ), and, given π, draw S = (S1 , . . . , Sm ) independently with Pr(Sb = ℓ | π) = pπ(ℓ) . Given π, the relabeled sequence π(S) consists of m independent draws from p. Let Q be the output of the rule on S. Since the rule is label-equivariant, given π the label π(Q) has the law of the output of the rule on π(S), so 7

Pr(π(Q) = t | π) = rt for every role t. Naming label ℓ earns the reward ηπ(ℓ) , where η1 = 1, ηj = −1 and ηt = 0 for t ∈ / {1, j}. The expected reward of the rule is therefore E[ηπ(Q) ] = r1 − rj , and the same argument for plurality gives q1 − qj . Posterior rewards. Fix an observed sequence s ∈ [k]m with count vector x. Under the assignment Q ℓ π, its probability is Lπ (x) = ℓ pxπ(ℓ) . Every π has prior probability 1/k!, so Bayes’ formula gives P Pr(π | S = s) = Lπ (x)/L(x), where L(x) = τ Lτ (x) is the total likelihood; sequences with L(x) = 0 have probability zero and are ignored. The randomness of the rule is independent of π given S. If the rule outputs label i with probability ϱi (s) on seeing s, its conditional expected reward given S = s is therefore X i

ϱi (s)

Ψi (x) Ψi (x) ≤ max , i L(x) L(x)

where

Ψi (x) =

X

ηπ(i) Lπ (x).

π

We show below that every label i of maximal count in x maximizes Ψi (x). Then all labels of maximal count have the same, maximal, value of Ψ, plurality attains maxi Ψi (x)/L(x) after every observation, and averaging over S gives r1 − rj ≤ q1 − qj . Grouping the assignments. Fix a label i of maximal count in x and another label i′ . Write a = xi ≥ b = xi′ , u = p1 and v = pj ; we use only that u ≥ pt for every role t (in particular u ≥ v), and no relation between v and the other probabilities. We show that Ψi (x) − Ψi′ (x) =

X

ηπ(i) − ηπ(i′ ) Lπ (x) ≥ 0

π

by grouping the assignments so that each group has a nonnegative total contribution. Within each group below, the roles of the labels outside a set B of at most three labels are fixed, and κ ≥ 0 xℓ ′ ′ / B. denotes the product of the factors pπ(ℓ ′ ) over the labels ℓ ∈ (a) If neither role 1 nor role j is carried by i or i′ , the contribution is zero. (b) If roles 1 and j are carried by i and i′ , group the two assignments that differ by exchanging them (B = {i, i′ }). Their contribution is 2κ ua v b − v a ub = 2κ(uv)b ua−b − v a−b ≥ 0.

(c) Otherwise, exactly one of the roles 1 and j is carried by i or i′ . The other one is carried by a third label ℓ, with count d = xℓ ≤ a, and the remaining label of {i, i′ } carries a role t ∈ / {1, j}, ′ with w = pt ≤ u. Fixing ℓ, t and the roles outside B = {i, i , ℓ} leaves four assignments: (π(i), π(i′ ), π(ℓ)) ηπ(i) − ηπ(i′ ) likelihood factor of i, i′ , ℓ (1, t, j) +1 ua wb v d (t, 1, j) −1 wa ub v d (j, t, 1) −1 v a wb ud (t, j, 1) +1 wa v b ud Their total contribution is κΞ, where Ξ = wb ua v d − v a ud − wa ub v d − v b ud .

If b < d, the first bracket is (uv)d (ua−d − v a−d ) ≥ 0 and the second is (uv)b (v d−b − ud−b ) ≤ 0, so Ξ ≥ 0. If b ≥ d, put δ1 = a − b and δ2 = b − d; using wa = wb wδ1 and uδ1 +δ2 − v δ1 +δ2 = uδ1 (uδ2 − v δ2 ) + v δ2 (uδ1 − v δ1 ), Ξ = (uv)d wb (uδ1 − wδ1 )(uδ2 − v δ2 ) + v δ2 (uδ1 − v δ1 ) ≥ 0. 



8

Each assignment belongs to exactly one group, so Ψi (x) ≥ Ψi′ (x). If i′ also has maximal count, exchanging the roles of i and i′ gives Ψi (x) = Ψi′ (x). No step divides by u, v or w, so labels of probability zero are covered.

3.3

Comparison with DéjàVu

To apply Lemma 4 we need a label-equivariant rule whose output law amplifies the gap. We obtain one from the DéjàVu dynamics [dDG+ 26b]. For an integer m ≥ 2, in DéjàVu(m) in PU LL(m) every agent observes, in every synchronous round, the opinions of m agents chosen independently and uniformly at random (with replacement, so an agent may observe itself, as in PU LL(h)); it reads these observations in order and adopts the first opinion that repeats an earlier observation, and if the m observations are pairwise distinct, it keeps its current opinion [dDG+ 26b, Section 3]. The following one-round estimate for this dynamics is [dDG+ 26b, Lemma 23], which we use as a black box.2 Lemma 5 (One round of DéjàVu [dDG+ 26b, Lemma 23]). There is an absolute constant γ1 > 0 such that the following holds for every integer m ≥ 2. Let C be a configuration with C1 ≥ C2 ≥ · · · ≥ Ck > 0 and C1 < 3n/4, and let Ce be the configuration after one round of DéjàVu(m) in PULL(m) from C. Then, with β = γ1 min{m2 C1 /n, 1}, E Ce1 − Cej C ≥ (1 + β) (C1 − Cj ) 



(2 ≤ j ≤ k),

E Ce1 C ≥ C1 + β (C1 − C2 ). 



The connection with h-Majority is a rule that reads h ≥ 3 labels: the rule Dh reads X1 , . . . , Xh in order and outputs the first label Xt with t ≤ h − 1 that repeats an earlier one; if X1 , . . . , Xh−1 are pairwise distinct, it outputs Xh . It is label-equivariant: relabeling the input by a permutation ψ maps the first label that repeats an earlier one to its image under ψ, and Xh to ψ(Xh ). The rule Dh has the same output law as the rule that outputs the first label that repeats an earlier one among all h draws, and a uniformly random draw if the h draws are pairwise distinct. Indeed, both rules output the same label unless the h draws are pairwise distinct; and, by exchangeability of the draws, the probability that the h draws are pairwise distinct and the uniformly chosen draw is i equals the probability that they are pairwise distinct and Xh = i. So the h-th observation plays no special role in Dh . Lemma 6 (h-Majority dominates DéjàVu(h − 1)). Let h ≥ 3, and let opinion 1 be a largest opinion of a configuration C. Let C ′ be the configuration after one round of h-Majority in PULL(h) from C, and let Ce be the configuration after one round of DéjàVu(h − 1) in PULL(h − 1) from C. Then, for every label j, E[C1′ − Cj′ | C] ≥ E Ce1 − Cej C , 



E[C1′ | C] ≥ E Ce1 C . 



Proof. Let p = C/n, let d be the output law of Dh on p, and let q be the output law of plurality on h draws from p. For a label i, let Fi be the probability that among h − 1 independent draws from p some draw repeats an earlier one and the first such draw is i, and let N be the probability that the h − 1 draws are pairwise distinct. In DéjàVu(h − 1), the observations of the agents are independent draws from p, independent of the agents’ current opinions, and an agent adopts i if the first repetition among its observations is i, or if its observations are pairwise distinct and its current opinion is i. Summing over the agents, E[Cei | C] = nFi + Ci N = n(Fi + pi N ). The rule Dh 2

In the notation of Lemma 5 below: [dDG+ 26b, Lemma 23] states explicit constants; we only use that some absolute constant works. When m > k + 1, a repetition occurs within the first k + 1 observations, so DéjàVu(m) coincides with DéjàVu(k + 1), and both scales min{m2 C1 /n, 1} and min{(k + 1)2 C1 /n, 1} equal 1, since kC1 ≥ n.

9

outputs i if the first repetition among X1 , . . . , Xh−1 is i, or if X1 , . . . , Xh−1 are pairwise distinct and Xh = i; as Xh is independent of X1 , . . . , Xh−1 , di = Fi + N pi . Hence E[Cei | C] = ndi for every label i, while E[Ci′ | C] = nqi by (1). Since Dh is label-equivariant and reads h labels, Lemma 4 gives d1 − dj ≤ q1 − qj and d1 ≤ q1 , and multiplying by n gives the claims. For h = 3, DéjàVu(2) is 2-Choices, and Lemma 6 holds with equality: D3 and plurality P on three draws both have output law pi (1 + pi − ℓ p2ℓ ), so one round of 3-Majority and one round of 2-Choices have the same expected effect. In general, the agent’s current opinion, which DéjàVu(h − 1) keeps when it sees no repetition, has the same effect on the expected configuration as a fresh observation, and Dh uses its h-th observation in this role.

3.4

One-round estimates

We now collect the properties of one round of h-Majority used in Section 4. Let C be a configuration in which opinion 1 is a largest opinion, so that C1 > 0, and let C ′ be the configuration after one round of h-Majority in PULL(h) from C. The expected growth factor of the count of opinion 1 is ρ = ρ(C) =

E[C1′ | C] q1 = , C1 p1

and α is the amplification scale of Section 2.1. Finally, U = n − C1 and U ′ = n − C1′ are the numbers of agents that do not hold opinion 1 in C and in C ′ . Lemma 7 (One-round estimates). There is an absolute constant γ0 ∈ (0, 1] such that the following holds. Let h ≥ 3, and let opinion 1 be a largest opinion of C. Then, for every j ̸= 1: (a) Ratio drift and order. ρ ≥ 1 and E[∆′j | C] ≥ ρ∆j . Moreover, Ci ≥ Ci′ implies E[Ci′ | C] ≥ E[Ci′′ | C], for all labels i, i′ . (b) Variance. Given C, C1′ and ∆′j are sums of n independent terms, one per agent, with values in {0, 1} and in {−1, 0, 1} respectively, and Var(C1′ | C) ≤ ρC1 ,

Var(∆′j | C) ≤ 2ρC1 .

(c) Growth of opinion 1. If C1 < 3n/4, then ρ − 1 ≥ γ0 α(C1 )

∆ . C1

(d) Growth of the gaps. If C1 < 3n/4, then E[∆′j | C] ≥ max ρ, 1 + γ0 α(C1 ) ∆, 

and, if moreover Cj > 0, the same bound holds with ∆j in place of ∆. (e) Endgame. If C1 ≥ 3n/4, then E[U ′ | C] ≤

3U 2 . n

Part (c) says that opinion 1 grows in proportion to its relative bias ∆/C1 , at the rate α(C1 ).

10

Proof. (a) By (1), E[Ci′ | C] = nqi . Since p1 = maxℓ pℓ , Lemma 3 gives q1 ≥ p1 , that is ρ ≥ 1, and n(q1 − qj ) ≥ (q1 /p1 ) n(p1 − pj ) = ρ∆j . If Ci ≥ Ci′ , then pi ≥ pi′ , and Lemma 3 gives qi ≥ qi′ . (b) Given C, the next opinions of the agents are independent with law q (Section 2). The term of an agent in C1′ is the indicator that its next opinion is 1, and its term in ∆′j is that indicator minus the indicator that its next opinion is j. Hence Var(C1′ | C) = nq1 (1 − q1 ) ≤ nq1 = ρC1 , and Var(∆′j | C) = n q1 + qj − (q1 − qj )2 ≤ n(q1 + qj ) ≤ 2nq1 = 2ρC1 , 



using qj ≤ q1 from (a). (c) and (d) Let γ1 be the constant of Lemma 5, and let γ0 = min{4γ1 /9, 1}. Let C1 < 3n/4, and let S be the set of opinions held by at least one agent in C. Opinions outside S are never observed, and every current opinion lies in S, so they do not affect one round of DéjàVu(h − 1) from C, which is one round of the same dynamics on the opinions in S. Since C1 < 3n/4, S contains an opinion other than 1, and ∆ = C1 − maxℓ∈S\{1} Cℓ . Renaming opinions does not change the transition law of DéjàVu. Renaming the opinions in S as 1, . . . , |S| in nonincreasing order of count, with opinion 1 first (possible since C1 = maxℓ Cℓ ), we may therefore apply Lemma 5 with m = h − 1 ≥ 2 and |S| in place of k, and there C1 − C2 = ∆; as (h − 1)2 ≥ 4h2 /9 for h ≥ 3, its parameter satisfies β = γ1 min{(h − 1)2 C1 /n, 1} ≥ γ0 α(C1 ). Let Ce be the configuration after one round of DéjàVu(h − 1) from C. For (c), Lemmas 5 and 6 give ρC1 = E[C1′ | C] ≥ E[Ce1 | C] ≥ C1 + γ0 α(C1 ) ∆. For (d), the bound E[∆′j | C] ≥ ρ∆j ≥ ρ∆ is (a). If Cj > 0, then j ∈ S, and Lemmas 5 and 6 give  

E[∆′j | C] ≥ E Ce1 − Cej C ≥ 1 + γ0 α(C1 ) ∆j ≥ 1 + γ0 α(C1 ) ∆. If Cj = 0, then Cj′ = 0 and ∆′j = C1′ , so (c) and ∆ ≤ C1 give E[∆′j | C] = ρC1 ≥ C1 + γ0 α(C1 ) ∆ ≥ (1 + γ0 α(C1 ))∆. (e) Let C1 ≥ 3n/4, so that p1 = maxℓ pℓ . The rule that outputs the most frequent of its first three observations, breaking ties uniformly at random, reads h ≥ 3 labels and is label-equivariant; let r be its output law on p. If at most one of the first three observations differs from 1, then 1 is the unique most frequent of them. Each observation differs from 1 with probability U/n, independently, so 1 − r1 ≤ 3(U/n)2 . By Lemma 4, q1 ≥ r1 , and hence E[U ′ | C] = n(1 − q1 ) ≤ n(1 − r1 ) ≤ 3U 2 /n.

4

From one round to consensus

Throughout this section, h ≥ 3, C (t) is the configuration of h-Majority in PU LL(h) after t rounds, p(t) = C (t) /n is the vector of opinion densities, and Ft is the history up to round t. We write (t) (t) C1 , ∆(t) and ∆j for the quantities of Section 2 at round t, and ρt = ρ(C (t) ) when opinion 1 is a largest opinion of C (t) . Labels are not reordered over time: opinion 1 is the initially largest opinion throughout. By the transition law of Section 2, given Ft , the configuration C (t+1) has the multinomial distribution with parameters n and q(p(t) ), which depends on the history only through C (t) . Hence (C (t) )t≥0 is a time-homogeneous Markov chain, and each lemma below, stated for an arbitrary initial configuration, also applies from a stopping time, conditionally on the history up to it (strong Markov property). While fewer than 3n/4 agents hold opinion 1, every round multiplies the bias by 1 + Ω(α(M0 )) with high probability (Lemma 8); then the remaining agents adopt opinion 1 within O(log n) rounds (Lemma 9). This round-by-round argument follows the one for DéjàVu(h) in [dDG+ 26b, Section 6.3], with Lemma 7 in place of the one-round estimates for DéjàVu(h). With this argument, our bias condition is stronger than that of DéjàVu(h) [dDG+ 26b, Theorem 1] because of the 11

fluctuations: in DéjàVu(h) only the agents that see a repetition can change opinion, and the variance of one round carries the probability of this event as a factor [dDG+ 26b, Lemma 18], whereas in h-Majority every agent resamples, and the variance can be of order C1 (Lemma 7(b) bounds it by ρC1 ). In this section, γ0 is the absolute constant of Lemma 7.

4.1

One round under the bias condition

Lemma 8 (One round under the bias condition). For every c > 0 there is a constant λc ≥ 1, depending only on c, such that the following holds for every λ ≥ λc . Let C be a configuration in which opinion 1 is the unique largest opinion, with C1 < 3n/4 and α(C1 ) ∆ ≥ λ C1 log n.

(3)

p

Let C ′ be the configuration after one round of h-Majority in PU LL(h) from C, and let γ = γ0 α(C1 ). With probability at least 1 − 2n−(c+2) , C1′ ≥ C1 ,

 3  ∆′ ≥ 1 + γ ∆, 4

q

α(C1′ ) ∆′ ≥ λ C1′ log n.

In particular, opinion 1 is the unique largest opinion of C ′ . √ Proof. Let Kc = 2 c + 3 + 2(c + 3); we prove the lemma with λc = 8Kc /γ0 . Expected values. Let ρ = ρ(C), and note that γ ≤ 1, as γ0 ≤ 1 and α(C1 ) ≤ 1. By Lemma 7(d), for every j ̸= 1, E[∆′j | C] ≥ max{ρ, 1 + γ} ∆. By Lemma 7(c),

E[C1′ | C] = ρC1 ≥ C1 + γ∆.

√ Fluctuations. Since ∆ ≤ C1 and α(C1 ) ≤ 1, (3) gives C1 ≥ λ C1 log n, that is, C1 ≥ λ2 log n. Let y = (c + 3) log n and p D = 4ρC1 y + 2y. By Lemma 7(b), each of C1′ and ∆′j (j ̸= 1) is, given C, a sum of n independent terms that differ from their means by at most 2, with variance at most 2ρC1 . Lemma 2 with J = 2 and V = 2ρC1 shows that each of these at most n variables differs from its conditional mean by less than D, except with probability at most 2e−y = 2n−(c+3) . By a union bound, all of them do so with probability at least 1 −√2n−(c+2) , and we work on this event from now on. Since λ ≥ 1 and C1 ≥ λ2 log n, we have log n ≤ C1 log n; together with ρ ≥ 1, (3) and λ ≥ 8Kc /γ0 , this gives √ ρ γ∆ Kc √ √ p √ α(C1 )∆ D ≤ Kc ρ C1 log n ≤ Kc ρ = ρ γ∆ ≤ . λ γ0 λ 8 Growth of the bias and of the count. If ρ ≤ 4, then D ≤ γ∆/4, and, using ∆ ≤ C1 , n

∆′ ≥ max ρ −

γ 3 o , 1 + γ ∆, 4 4

C1 ≤ C1 + γ∆ −

If ρ > 4, then D ≤ ρ∆/16, because γ ≤ 1 and ∆′ ≥

15 ρ∆, 16

√

 γ∆ γ ≤ C1′ ≤ ρ + C1 . 4 4

ρ ≤ ρ/2; hence

C1 ≤

15 17 ρC1 ≤ C1′ ≤ ρC1 . 16 16

In both cases C1′ ≥ C1 and ∆′ ≥ (1 + 34 γ)∆. In particular ∆′ > 0, so opinion 1 is the unique largest opinion of C ′ . 12

√ √ √ The condition (3) is preserved. We have α(x)/ x = min{h2 x/n, 1/p x}, and, when x increases √ ′ , the first term increases and the second decreases by the factor ′ . Hence α(x′ )/ x′ ≥ to x x/x p √ x/x′ α(x)/ x for x′ ≥ x > 0. As C1′ ≥ C1 , this and (3) give α(C1′ ) ∆′ q

C1′

∆′ ≥ ∆

so it suffices to show that ∆′ /∆ ≥

s

∆′ C1 α(C1 ) ∆ √ ≥ · C1′ ∆ C1

s

C1 p · λ log n, C1′

q

C1′ /C1 . We distinguish three cases.

• If ρ ≤ 1 + γ, then C1′ /C1 ≤ 1 + 45 γ, and s

C1′ 5 3 ∆′ ≤1+ γ ≤1+ γ ≤ . C1 8 4 ∆

• If 1 + γ < ρ ≤ 4, let x = ρ − γ/4, so that x > 1 + 34 γ and C1′ /C1 ≤ x + γ/2. Since x2 − x = x(x − 1) ≥ 43 γ ≥ γ2 , s

• If ρ > 4, then

s

C1′ ≤ C1

r

C1′ ≤ C1

r

x+

γ ∆′ ≤x≤ . 2 ∆

17 15 ∆′ ρ≤ ρ≤ , 16 16 ∆

where the middle inequality holds because ρ ≥ 272/225.

4.2

The endgame

Lemma 9 (Endgame). For every c > 0 there is nc , depending only on c, such that the following (0) holds for n ≥ nc . If C1 ≥ 3n/4, then, with probability at least 1 − n−(c+1) , the configuration is a consensus on opinion 1 in round tc = ⌈(c + 3) log4/3 n⌉ = O(log n). (t)

Proof. Let Ut = n − C1 , and let At be the event that Us ≤ n/4 for all s ≤ t (with A−1 the sure event). On At , Lemma 7(e) gives E[Ut+1 | Ft ] ≤ 3Ut2 /n ≤ 43 Ut . Since At ⊆ At−1 and Ut ≥ 0,     3  3  E Ut+1 1At ≤ E Ut 1At ≤ E Ut 1At−1 , 4 4

and by induction E[Ut 1At−1 ] ≤ (3/4)t U0 ≤ n(3/4)t . Moreover, on At , given Ft , Ut+1 is a sum of n 2 independent indicators with mean at most 3U 2 √ t /n ≤ 3n/16 and variance at most 3n/16; Lemma with J = 1, V = 3n/16 and y = n/256 gives 2V y + Jy < n/16, so Pr(Ut+1 > n/4 | Ft ) ≤ 2e−n/256 on At . Hence Pr(Utc ≥ 1) ≤ Pr(Actc −1 ) + E Utc 1Atc −1 ≤ 2tc e−n/256 + n 



for n ≥ nc .

13

 3 tc

4

≤ 2tc e−n/256 + n−(c+2) ≤ n−(c+1)

4.3

Proof of Theorem 1

Fix c > 0, let λ = λc be as in Lemma 8, and let log n T1 = . log(1 + 3γ0 α(M0 )/4) 



Since log(1 + x) ≥ x/2 for 0 ≤ x ≤ 1, and 1/α(M0 ) = max{1, n/(h2 M0 )}, T1 ≤ 1 +

  8 n  log n . log n = O 1 + 2 3γ0 α(M0 ) h M0

Moreover, α(M0 ) ≥ min{9/n, 1} ≥ 1/n, as h ≥ 3 and M0 ≥ 1, so T1 ≤ 1 + 3n log n/γ0 . Let n′c ≥ 3 be at least the nc of Lemma 9 and such that 2(1 + 3n log n/γ0 ) n−(c+2) ≤ n−c /2 for all n ≥ n′c . We prove the theorem with Lc = max{λ, L∗c }, where L∗c is such that (L∗c )2√> n/ log n for all 2 ≤ n < n′c . As noted after Theorem 1, the bias condition reads α(M0 )∆0 ≥ Lc M0 log n and implies n ≥ M0 ≥ L2c log n; hence n ≥ n′c . (τ ) Let τ be the first round with C1 ≥ 3n/4 (so τ = 0 if M0 ≥ 3n/4). Let B be the event that, for some round t < min{τ, T1 }, the configuration C (t) satisfies the hypotheses of Lemma 8 but its conclusions fail for the transition from C (t) to C (t+1) . Applying Lemma 8 conditionally on Ft for each t < T1 , and a union bound, gives Pr(B) ≤ 2T1 n−(c+2) ≤ n−c /2, by the choice of n′c . On the complement of B, we show by induction that, for 0 ≤ t ≤ min{τ, T1 }, opinion 1 is the unique largest opinion of C (t) and (t) C1 ≥ M0 ,

q

(t)
α C1 ∆(t) ≥ λ

(t)

C1 log n,

t  3 ∆(t) ≥ 1 + γ0 α(M0 ) ∆0 . 4

(4)

For t = 0, this is the bias condition, as λ ≤ Lc . Let t < min{τ, T1 } and assume (4) at round t. Since (t) t < τ , we have C1 < 3n/4, so C (t) satisfies the hypotheses of Lemma 8, and its conclusions hold (t) outside B. They give (4) at round t + 1, because α is nondecreasing and C1 ≥ M0 , so that the (t) factor of Lemma 8 is 1 + 43 γ0 α(C1 ) ≥ 1 + 34 γ0 α(M0 ). Outside B, we have τ ≤ T1 : otherwise (4) at t = T1 and ∆0 ≥ 1 would give ∆(T1 ) ≥ n, whereas (T ) ∆(T1 ) ≤ C1 1 < 3n/4. At round τ , a stopping time, at least 3n/4 agents hold opinion 1. By the strong Markov property and Lemma 9, the configuration is a consensus on opinion 1 tc rounds later, except with probability at most n−(c+1) . Hence, except with probability at most n−c /2 + n−(c+1) ≤ n−c , consensus on opinion 1 is reached within T1 + tc rounds. As n ≥ 3, the bounds on T1 and tc give T1 + tc ≤ Ac (1 + n/(h2 M0 )) log n for a constant Ac depending only on c. Consensus is absorbing, which completes the proof of Theorem 1.

AI usage statement Large language models from OpenAI, Anthropic and Google were used throughout this work, both to develop the proofs and to draft the text. The authors are fully responsible for all content of the note.

References [BCE+ 17]

Petra Berenbrink, Andrea Clementi, Robert Elsässer, Peter Kling, Frederik Mallmann-Trenn, and Emanuele Natale. Ignore or comply?: On breaking symmetry in consensus. In ACM Symposium on Principles of Distributed Computing, PODC, pages 335–344, 2017.

14

[BCN+ 16]

Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan. Stabilizing consensus with many opinions. In Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 620–635, 2016.

[BCN+ 17]

Luca Becchetti, Andrea Clementi, Emanuele Natale, Francesco Pasquale, Riccardo Silvestri, and Luca Trevisan. Simple dynamics for plurality consensus. Distributed Computing, 30(4):293–306, 2017.

[BCN20]

Luca Becchetti, Andrea Clementi, and Emanuele Natale. Consensus dynamics: An overview. ACM SIGACT News, 51(1):58–104, 2020.

[BEM59]

Robert E. Bechhofer, Salah E. Elmaghraby, and Norman Morse. A single-sample multiple-decision procedure for selecting the multinomial event which has the highest probability. Ann. Math. Statist., 30(1):102–119, 1959.

[BG52]

Raghu Raj Bahadur and Leo A. Goodman. Impartial decision rules and sufficient statistics. Ann. Math. Statist., 23(4):553–562, 1952.

[BLM13]

Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press, 2013.

[CER14]

Colin Cooper, Robert Elsässer, and Tomasz Radzik. The power of two choices in distributed voting. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, pages 435–446, 2014.

[CMR+ 25] Colin Cooper, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. Asynchronous 3-Majority dynamics with many opinions. In 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 4095–4131, 2025. [D’A26]

Niccolò D’Archivio. Consensus time in 3-Majority and 2-Choices is determined by the maximum initial opinion density. In 40th International Symposium on Distributed Computing, DISC, 2026. To appear. arXiv:2606.11778.

[dDG+ 26a] Francesco d’Amore, Niccolò D’Archivio, George Giakkoupis, Frédéric Giroire, and Emanuele Natale. Brief announcement: DéjàVu: A minimalistic mechanism for distributed plurality consensus. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2026, Egham, United Kingdom, July 6-10, 2026, pages 437–440, 2026. [dDG+ 26b] Francesco d’Amore, Niccolò D’Archivio, George Giakkoupis, Frédéric Giroire, and Emanuele Natale. DéjàVu: A minimalistic mechanism for distributed plurality consensus. arXiv:2604.03648v3, 2026. [dDGN25]

Francesco d’Amore, Niccolò D’Archivio, George Giakkoupis, and Emanuele Natale. On the h-Majority dynamics with many opinions. In 39th International Symposium on Distributed Computing, DISC, pages 27:1–27:24, 2025.

[DGGN26] Niccolò D’Archivio, George Giakkoupis, Frédéric Giroire, and Emanuele Natale. DéjàVu: Plurality consensus by first repetition. Manuscript, 2026. [DGM+ 11] Benjamin Doerr, Leslie Ann Goldberg, Lorenz Minder, Thomas Sauerwald, and Christian Scheideler. Stabilizing consensus with the power of two choices. In Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 149–158. ACM, 2011. [dRS+ 26]

Francesco d’Amore, Joel Rybicki, Nobutaka Shimizu, Takeharu Shiraga, and Robin Vacus. Nearly-optimal time-sample trade-off in consensus dynamics. arXiv:2610.40562v2, 2026.

[EFK+ 16]

Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Frederik Mallmann-Trenn, and Horst Trinker. Efficient k-party voting with two choices. arXiv:1602.04667, 2016.

[GL18]

Mohsen Ghaffari and Johannes Lengler. Nearly-tight analysis for 2-Choice and 3-Majority consensus dynamics. In 2018 ACM Symposium on Principles of Distributed Computing, PODC, pages 305–313, 2018.

15

[HP01]

Yehuda Hassin and David Peleg. Distributed probabilistic polling and applications to proportionate agreement. Inf. Comput., 171(2):248–268, 2001.

[Leh66]

Erich L. Lehmann. On a theorem of Bahadur and Goodman. Ann. Math. Statist., 37(1):1–6, 1966.

[SS25]

Nobutaka Shimizu and Takeharu Shiraga. 3-Majority and 2-Choices with many opinions. In ACM Symposium on Principles of Distributed Computing, PODC, pages 207–217, 2025.

16

Related documents

• Minimax Binary Counting under Shuffle Privacy: Poisson Limits and Randomized-Response Optimality#1354864
• A Local Central Limit Theorem for Clique Counts in Sparse Random Graphs#625427
• A Local Central Limit Theorem for Clique Counts in Sparse Random Graphs#623154
• CoDiNG -- Naming Game with Continuous Latent Opinions of Individual Agents#792595
• CoDiNG -- Naming Game with Continuous Latent Opinions of Individual Agents#788595