Dependencies

If \(M(c) = \{ m\} \) and \(s(c) \ge 22\sqrt{\min \{ 2k, (n/\log n)^{1/3}\} \, n\log n}\), then 3-majority reaches consensus on \(m\) in \(O(\min \{ 2k, (n/\log n)^{1/3}\} \log n)\) rounds w.h.p. Precisely, for \(\log n \ge 40\) and \(k \ge 2\): at most \(130\lambda \log n\) rounds with probability at least \(1 - 143\lambda \log n/n\).

If \(c_m \ge n/\log ^\ell n\) and \(s(c) \ge 22\sqrt{n\log ^{\ell +1}n}\), consensus takes \(O(\log ^{\ell +1} n)\) rounds w.h.p. If \(c_m \ge n/\beta \) and \(s(c) \ge 22\sqrt{\beta n\log n}\) for a constant \(\beta \ge 3\), it takes \(O(\log n)\) rounds w.h.p.

In the binary 3-majority process, if the initial majority leads by at least \(22\sqrt{3n\log n}\) nodes (a fraction \(\frac12 + O(\sqrt{\log n/n})\)) and \(\log n \ge 40\), all nodes adopt it within at most \(390\log n\) rounds with probability at least \(1 - 429\log n/n\).

A coloring is a map \(x \colon [n] \to [k]\). The number of nodes of color \(j\) is \(c_j = |\{ v : x(v) = j\} |\), and \(\sum _j c_j = n\). The vector \(c = (c_1,\dots ,c_k)\) is the paper’s \(k\)-color distribution (\(k\)-cd).

A rule is conservative if it returns one of its inputs. It has the clear-majority property if it returns the majority color whenever two inputs agree. For colors \(r \ne b\), \(\Delta _r\) counts the orderings of \((r,r,b)\) on which the rule returns \(r\). For distinct \(r,g,b\), \(\delta _c\) counts the orderings of \((r,g,b)\) on which it returns \(c\); the rule is uniform if \(\delta _r = 2\) for all distinct triples. It is an \((s,\varepsilon )\)-solver if from every coloring whose unique plurality color \(m\) has bias at least \(s\), consensus on \(m\) is eventually reached with probability at least \(1-\varepsilon \).

Every node samples \(h\) nodes and a uniformly random ordering \(\sigma \) of the \(h\) sample positions, and adopts the color of the position of smallest \(\sigma \)-rank among those whose color is most frequent. All tied colors appear equally often, so each is chosen with the same probability.

The process with rule \(f\) is the finite Markov kernel on colorings whose row at \(x\) is the law of one round of \(f\) from \(x\). Its \(T\)-step event probabilities are the expectations over \(T\) independent uniform rounds.

\(x\) is in consensus on \(m\) if every node has color \(m\), i.e. \(c_m = n\). For every 3-input rule, consensus is absorbing.

Fix \(m\), \(\lambda \), \(\Lambda \) and let \(q = 1 + 1/(6\lambda )\), \(B = n^{1/4}\log n\). Growth phase \(i\): \(c_m {\gt} \frac23 n\), or \(M(c) = \{ m\} \), \(c_m \ge n/\lambda \) and \(s(c) \ge \Lambda q^i\). Saturation phase \(j\): \(n - c_m {\lt} \max \{ \frac n3 (\frac{17}{18})^j,\ B\} \). Consensus: \(c_m = n\).

For a \(k\)-cd \(c\) with \(\sum _h c_h = n\): \(m(c) = \max _h c_h\), \(M(c) = \{ j : c_j = m(c)\} \), the bias \(s(c) = m(c) - \max _{h \notin M(c)} c_h\) if \(|M(c)| = 1\) and \(0\) otherwise, \(\alpha (c) = (n - m(c))\, s(c)/n^2\) and \(\gamma (c) = (n\, m(c) - \sum _h c_h^2)/n^2 - \alpha (c)\).

A 3-input rule is a map \(f \colon [k]^3 \to [k]\) with \(f(a,b,c) \in \{ a,b,c\} \). The 3-majority rule is \(\mathrm{maj}_3(a,b,c) = b\) if \(b = c\) and \(a\) otherwise; it returns the majority color, and the first color if all three differ.

A round is a map \(r \colon [n] \to [n]^3\) (the three samples of every node), drawn uniformly. The next coloring under rule \(f\) is \(v \mapsto f(x(r_v^1), x(r_v^2), x(r_v^3))\). The process after \(T\) rounds folds this step over \(T\) independent uniform rounds.

For every coloring and every color \(j\),

For every \(k\)-cd \(c\): (a) \(0 \le s(c) \le m(c) - (n - m(c))/(k-1)\); (b) \(0 \le \alpha (c) \le \min \{ s(c)/n,\ 1/4\} \); (c) \(0 \le \gamma (c) \le 1/8\).

Let \(m \in M(c)\) and let \(\ell \ne m\) have the most nodes among the other colors. Then (a) \(\mu _m(c) = c_m(1 + \gamma + \alpha )\); (b) \(\mu _j(c) = c_j(1 + \gamma + \alpha - (m(c) - c_j)/n)\) for every \(j\); (c) \(\mu _\ell (c) = c_\ell (1 + \gamma + \alpha - s(c)/n)\).

If \(M(c) = \{ m\} \) then for every \(j \ne m\),

If \(M(c) = \{ m\} \) then \(\Pr (C_{m,t+1} \le c_m(1 + \gamma + \alpha /2) \mid C_t = c) \le \exp (-c_m\alpha ^2/11)\).

If \(M(c) = \{ m\} \), \(0 {\lt} \lambda \le 2/3\), \(\lambda n \le c_m \le (2/3)n\) and \(s(c) \ge 22\sqrt{(1/\lambda )\, n\log n}\), then for every \(j \ne m\)

For every \(m \in M(c)\), writing \(\bar C_{m,t+1} = n - C_{m,t+1}\),

Let \(\log n \ge 40\), \(M(c) = \{ m\} \). (i) If \(s(c) \ge n/3\) and \(n - c_m \ge n^{1/4}\log n\) then \(\Pr (\bar C_{m,t+1} \ge \frac{17}{18}(n - c_m)) \le 1/n^2\). (ii) If \(n - c_m {\lt} n^{1/4}\log n\) then \(\Pr (\bar C_{m,t+1} {\gt} 0) \le n^{-1/5}\) and \(\Pr (\bar C_{m,t+1} \ge n^{1/4}\log n) \le 1/n^2\).

Let \(k\sqrt{n\log n} \le b \le n/k\). If \(c_j \le n/k + b\), then \(\Pr (C_{j,t+1} \ge n/k + (1 + 3/k)b \mid C_t = c) \le 1/n^2\).

If \(c_j \le a \le 2n/k\), then \(\Pr (C_{j,t+1} \ge a(1 + 2h^2/k)) \le \exp (-2(ah^2/k)^2/n)\), which is at most \(e^{-2nh^4/k^4}\) when \(a \ge n/k\).

Let \(A_1 \supseteq \cdots \supseteq A_T\) be sets of states of a finite Markov chain such that from every state of \(A_i\) the chain stays in \(A_i\) with probability \(\ge 1-\varepsilon \) and, for \(i {\lt} T\), moves into \(A_{i+1}\) with probability \(\ge 1 - \nu \). Then from any state of \(A_1\), after \(\ell T\) steps the chain is in \(A_T\) with probability at least \(1 - T(\ell \varepsilon + \nu ^\ell )\).

The new count of color \(j\) is a sum of \(n\) independent indicators, one per node. Under 3-majority, a node adopts \(j\) with probability \(x_j^2 + x_j(1 - \sum _h x_h^2)\), where \(x_h = c_h/n\).

Let the rule be conservative with the clear-majority property, let only \(r, g, b\) be present and \(\delta _r \le 1\). Then \(p(r) \le 3x^2 - 2x^3 + \delta _r x_r x_g x_b \le x(3x - 2x^2 + (1-x)^2/4)\), which is at most \(0.97x\) for \(x \le 2/5\); and from \(x \le 2/5\) one round ends above \(2n/5\) with probability at most \(e^{-9n/31250}\).

Under a conservative rule a color without nodes never returns. Hence for all \(T, T_0\), the probability of consensus on \(m\) at time \(T\) is at most the probability that \(m\) has a node at time \(T_0\).

If \(c_m = m(c)\) then \(c_h + s(c) \le m(c)\) for every \(h \ne m\), with equality for some \(h\) when \(k \ge 2\). Moreover \(\gamma (c)\, n^2 = \sum _{h \ne m} c_h\, (m(c) - s(c) - c_h)\).

If \(n - c_m {\lt} n/3\) then \(M(c) = \{ m\} \) and \(s(c) \ge n/3\). If \(m\) leads every other color by at least \(g {\gt} 0\) and \(c_m \ge g\), then \(M(c) = \{ m\} \) and \(s(c) \ge g\). A color without nodes stays without nodes.

If a round-based process starts in \(G_0\) and, for every \(t {\lt} T\), one round from any state of \(G_t\) misses \(G_{t+1}\) with probability at most \(p\), then after \(T\) rounds it lies outside \(G_T\) with probability at most \(Tp\).

Under the hypotheses of Lemma 38, starting with at most \(2n/5\) nodes of \(r\), the probability that \(r\) still has a node after \(T\) rounds is at most \(0.97^T c_r + T e^{-9n/31250}\).

A node adopts \(j\) with probability at most \(x_j + \frac{h^2}{2}x_j^2\).

Let \(\log n \ge 40\), \(k \ge 2\), \(\lambda \ge 3\) and \(\Lambda \ge 22\sqrt{\lambda n \log n}\). From growth phase \(i\) the chain enters growth phase \(i+1\) with probability \(\ge 1 - 1/n\). From saturation phase \(j\) it enters saturation phase \(j+1\) with probability \(\ge 1 - 1/n^2\). From fewer than \(B\) dissenting nodes it reaches consensus with probability \(\ge 1 - n^{-1/5}\), and consensus is kept with probability \(1\). The phase sets are nested, and growth phase \(i\) lies in saturation phase \(0\) once \(\Lambda q^i {\gt} n\).

With \(T_1 = \lceil \log n/\log q\rceil \) growth phases, \(T_2 = \lceil \log n/\log (18/17)\rceil + 1\) saturation phases and one consensus phase, \(T = T_1 + T_2 + 1 \le 13\lambda \log n\) for \(\lambda \ge 3\) and \(\log n \ge 40\).

For \(X = \sum _i Y_i(\omega _i)\) with independent uniform coordinates: Bernstein’s inequality \(\Pr (X \ge \mathbb {E}X + \lambda ) \le \exp (-\lambda ^2/(2\sigma ^2(1 + b\lambda /(3\sigma ^2))))\) when \(Y_i - \mathbb {E}Y_i \le b\) and \(\sum _i \mathrm{Var}\, Y_i \le \sigma ^2\); Hoeffding’s inequality for \(\{ 0,1\} \) coordinates; the multiplicative Chernoff lower tail \(\Pr (X \le (1-\delta )\mu ) \le \exp (-\delta ^2\mu /2)\); and Markov’s inequality \(\Pr (X \ge 1) \le \mathbb {E}X\) for \(\{ 0,1\} \) coordinates.

Let \(\log n \ge 40\), \(k \ge 2\) and \(\lambda \ge 3\). If \(M(c) = \{ m\} \), \(c_m \ge n/\lambda \) and \(s(c) \ge 22\sqrt{\lambda n\log n}\), then after \(10T \le 130\lambda \log n\) rounds all nodes support \(m\) with probability at least \(1 - 11T/n \ge 1 - 143\lambda \log n/n\).

Let \(k \ge 3\). If every color starts with at most \(\frac32\cdot \frac nk\) nodes and \(T \le \frac{k}{2h^2}\log \frac43\), then after \(T\) rounds of \(h\)-plurality the coloring is monochromatic with probability at most \(kT e^{-2nh^4/k^4}\).

Let \(k \ge 3\) and suppose every color starts with at most \(n/k + b\) nodes, where \(b \ge k\sqrt{n\log n}\). If \(b(1 + 3/k)^T \le n/k\), in particular if \(T \le \frac k3 \log \frac{n}{kb}\), then the coloring after \(T\) rounds is monochromatic with probability at most \(kT/n^2\).

Let \(8 \mid n\). With only colors \(r, b\) present and \(x\) the fraction of \(r\), a node adopts \(r\) with probability \(p(x)\), where \(p(x) - x = x(1-x)\bigl(x(\Delta _r - 2) + (1-x)(2 - \Delta _b)\bigr)\). If \(\Delta _r \le 2 \le \Delta _b\), the number of \(r\) nodes is a supermartingale, so from \(5n/8\) nodes of \(r\) (bias \(n/4\)) consensus on \(r\) has probability at most \(5/8\) at every time: the rule is not an \((n/4, 1/4)\)-solver. Consequently, for an \((n/4, 1/4)\)-solver and every pair \(r \ne b\), either \(\Delta _r = \Delta _b = 3\) or \(\Delta _r, \Delta _b \le 1\).

Let \(60 \mid n\) and \(\log n \ge 20\). A rule with the clear-majority property that is an \((n/20, 1/4)\)-solver has the uniform property.

With \(k = 2\) the set of nodes of color \(1\) evolves exactly as the binary 3-majority process of the three_majority package. Hence, if \(c_1 \ge \frac35 n\) and \(\log n \ge 30\), all nodes support color \(1\) after \(O(\log n)\) rounds with probability at least \(1 - 500/n\).