Approximate majority on a graph with a random initial placement (CRN-4) #
The 3-state approximate-majority protocol of Angluin, Aspnes and Eisenstat [AAE08] on an
arbitrary graph G with the probabilistic scheduler [MNRS14, §2]: each step activates a
uniformly random oriented edge (a uniform edge with a uniform orientation; Dynamics.EdgeRound),
whose tail is the initiator and head the responder. The states are the species X, Y, B of
Crn.ApproxMajority (CRN-1), and the transition is the one-way rule of [MNRS14, eq. (1)]
(rule): the initiator never changes; an X/Y initiator turns an opposite responder blank
and recruits a blank responder. Every effective transition is one of the four reactions of the
approximate-majority CRN network (rule_mem_network, exists_rule_of_mem_network).
[MNRS14, Theorem 4]: if the m ≥ n − m majority agents (Y, the paper's green g) and
the n − m minority agents (X, red r) are placed uniformly at random, the probability that
the protocol converges to the minority is at most the probability that it converges to the
majority.
Convergence is formalized in the finite probability layer of dynamics/: winProb G m s t is
the probability (over the placement and the scheduler) that at time t every agent is in state
s. Unanimous configurations are absorbing, so winProb is nondecreasing in t
(winProb_monotone) and the convergence probability is its supremum, absorbProb G m s
(the limit, tendsto_winProb), as for Dynamics.Kernel.iSup_event_of_invariant. We pin:
- the finite-time inequality
winProb_minority_le_majority(everyt, every graph with an edge), and its limitabsorbProb_minority_le_majority; - the paper's literal statement
half_le_absorbProb_majority("with probability at least1/2"), on connected graphs, using that the protocol is absorbed almost surely (tendsto_event_unanimous), a step the paper leaves implicit.
The proof follows [MNRS14, proof of Theorem 4]:
- monotonicity (eq. (19), "increasing the initial number of agents of type
rincreases the probability that agents of typerwin", stated without proof in the paper): for the orderY < B < X(rank) the rule is monotone in both states (rule_mono), so running two ordered configurations with the same oriented edges keeps them ordered (graphStep_mono), andP(all X at time t)is monotone in the initial configuration (event_allX_mono); - symmetry (eq. (20)): exchanging
XandY(swap) commutes with the dynamics (graphStep_swap,event_swap); - a system of distinct representatives (Corollary 1, from Hall's theorem): every
m-setSgets an(n − m)-subsetA_S ⊆ S, injectively (exists_injective_subset, from the generalexists_injective_of_regular).
References #
- [AAE08] D. Angluin, J. Aspnes, D. Eisenstat, A simple population protocol for fast robust approximate majority, Distributed Computing 21 (2008).
- [MNRS14] G. B. Mertzios, S. E. Nikoletseas, C. L. Raptopoulos, P. G. Spirakis, Determining majority in networks with local interactions and very small local memory, ICALP 2014; arXiv:1404.7671.
The one-way rule of [AAE08] and its relation to the CRN network #
The transition function of the 3-state protocol of [AAE08], [MNRS14, eq. (1)], on the
states of (initiator, responder): δ(x, y) = (x, x) if y = B and x ≠ B, δ(x, y) = (x, B)
if {x, y} = {X, Y}, and no change otherwise (equal states, or a blank initiator).
Equations
- Crn.ApproxMajority.rule (Crn.ApproxMajority.Species.X, Crn.ApproxMajority.Species.Y) = (Crn.ApproxMajority.Species.X, Crn.ApproxMajority.Species.B)
- Crn.ApproxMajority.rule (Crn.ApproxMajority.Species.Y, Crn.ApproxMajority.Species.X) = (Crn.ApproxMajority.Species.Y, Crn.ApproxMajority.Species.B)
- Crn.ApproxMajority.rule (Crn.ApproxMajority.Species.X, Crn.ApproxMajority.Species.B) = (Crn.ApproxMajority.Species.X, Crn.ApproxMajority.Species.X)
- Crn.ApproxMajority.rule (Crn.ApproxMajority.Species.Y, Crn.ApproxMajority.Species.B) = (Crn.ApproxMajority.Species.Y, Crn.ApproxMajority.Species.Y)
- Crn.ApproxMajority.rule x✝ = x✝
Instances For
The 3-state protocol of [AAE08] as a population protocol: input true ↦ X,
false ↦ Y, output true exactly in state X.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The chain on a graph #
One step of the protocol on G: the endpoints of the oriented edge d interact (tail
initiator, head responder) [MNRS14, §2].
Equations
Instances For
The Markov chain of the protocol on G under the probabilistic scheduler [MNRS14, §2]:
each step activates a uniformly random oriented edge (EdgeRound G), i.e. a uniform edge with
a uniform orientation.
Instances For
The initial placement with the majority type Y exactly on S and the minority type X
elsewhere [MNRS14, proof of Theorem 4: (R₀, G₀) = (V − S, S)].
Equations
Instances For
The probability that at time t every agent is in state s, when the m agents of type
Y are placed uniformly at random (a uniform m-subset S, [MNRS14, eq. (18)]) and the
protocol runs on G with the probabilistic scheduler.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The probability that the protocol eventually converges to s from a uniformly random
placement of m agents of type Y: the supremum (the limit, tendsto_winProb) of the
finite-time probabilities winProb.
Equations
- Crn.ApproxMajority.absorbProb G m s = ⨆ (t : ℕ), Crn.ApproxMajority.winProb G m s t
Instances For
Monotonicity and symmetry #
The order Y < B < X on states (the paper's g < b < r).
Equations
Instances For
Exchange of the two opinions X ↔ Y.
Equations
Instances For
One step of the chain averages an observable over the uniformly random oriented edge.
Monotone coupling, t steps. If an observable is monotone for the agentwise order
Y < B < X, so is its expectation after t steps.
The dynamics commutes with the exchange of X and Y, at every time t.
Monotonicity [MNRS14, eq. (19)]: the probability that every agent is X at time t
can only increase when the initial configuration increases agentwise in the order
Y < B < X.
Symmetry [MNRS14, eq. (20)]: the probability that every agent is X at time t from
c is the probability that every agent is Y at time t from the exchanged configuration.
A unanimous configuration is absorbing.
Systems of distinct representatives #
[MNRS14, Corollary 1] (a consequence of Hall's theorem, Jukna, Extremal
Combinatorics, ch. 5): r-element subsets T i of a universe of y elements such that each
element belongs to the same number d ≥ 1 of them, with x ≤ y sets, have a system of
distinct representatives.
[MNRS14, proof of Theorem 4]: if n − m ≤ m, every m-subset S of the agents can be
assigned an (n − m)-subset A_S ⊆ S, injectively.
Almost sure absorption: helper lemmas #
Spreading on a connected graph: from a configuration with an agent in state s ≠ B,
the configuration in which every agent is in state s is reachable (activate twice an edge
from an agent in state s to an agent in another state, until there is none).
Access: if b is reachable from a on G and an observable g ≤ 1 is below 1 at
b, then its expectation at some finite time from a is below 1.
From a configuration with a non-blank agent, all agents are never simultaneously blank.
Theorem 4 #
Unanimity is absorbing, so the finite-time convergence probabilities are nondecreasing.
The finite-time convergence probabilities lie in [0, 1].
The convergence probability is the limit of the finite-time probabilities.
[MNRS14, Theorem 4], finite-time form. On every graph with an edge, if the m ≥ n − m
agents of the majority type Y and the n − m agents of the minority type X are placed
uniformly at random, then at every time t the probability that every agent is X (the
minority has won) is at most the probability that every agent is Y (the majority has won).
[MNRS14, Theorem 4]. On every graph with an edge, with a uniformly random placement of
m ≥ n − m majority agents, the protocol of [AAE08] converges to the initial majority with
probability at least the probability that it converges to the initial minority.
Almost sure convergence (implicit in [MNRS14, Theorem 4]): on a connected graph, from
every configuration with a non-blank agent, the probability that the protocol has converged to
X or to Y by time t tends to 1.
[MNRS14, Theorem 4], as stated. On a connected graph, with a uniformly random placement
of m ≥ n − m majority agents (m ≤ n), the protocol of [AAE08] converges to the initial
majority with probability at least 1/2.