# Population protocol model

CRN where each reaction has 2 reactants, 2 products, and rate constant 1, e.g., $X,Y \to X,Z$.

__Translation key:__
*state* = chemical species
*transition* = reaction
*agent* = molecule
*interaction* = collision of two molecules (may or may not result in a reaction)

Any unspecified transition is *null*: $x,y \to x,y$

The two reactants are distinguished, even if they are in the same state: first is "sender" and second is "receiver".
- Some distributed computing studies make a big deal of inability to break symmetry between identical agents in an interaction, i.e., disallowing asymmetric interactions such as $L,L \to L,F$.

## Time complexity
population size $=n$
time = # interactions / $n$

In other words, each agent has $O(1)$ interactions per unit time. This corresponds exactly to Gillespie kinetics with volume $n$.
- Except for continuous time versus discrete time: PPs say exactly $n$ interactions happen in 1 time unit, but CRNs say number of interactions in one time unit is Poisson with expected value $n$.

# Majority problem

Given two initial opinions $A,B$ in population of $n$ agents, determine which is greater count.

In initial configuration $\vec{i}$, let $g(\vec{i}) = \vec{i}(A) - \vec{i}(B)$ be the *initial gap*. Goal is to determine $\mathrm{sign}(g)$.

## approximate majority protocol
$A,B \to U,U$ $\quad$ (cancel)
$A,U \to A,A$ $\quad$ (split)
$B,U \to B,B$ $\quad$ (split)

Called "approximate" because it might get the answer wrong.

Pr[correct] depends on initial gap $g$.
- If $g = \Omega(\sqrt{n \log n})$, then Pr[correct] $\approx 1$.
- Otherwise Pr[correct] $\approx 1/2$.

Convergence time is $O(\log n)$. (optimal)

## Goal: solve majority "exactly" (i.e., with probability 1) and quickly

Simple slow ($O(n \log n)$ time) exact protocol:
$A,B \to a,b$ $\quad$ (leaders with opposite opinions become followers)
$A,b \to A,a$ $\quad$ (leaders change opinions of followers)
$B,a \to B,b$ $\quad$ (leaders change opinions of followers)

Majority cannot be solved with probability 1 in $o(n)$ time using $O(1)$ states. So we need to let # states grow with $n$ to achieve $o(n)$ time.

When states are allowed to grow with $n$, two kinds of protocols:
- **nonuniform:** states and transitions can depend "weakly" on $n$. Typically shows up as the constant $\lceil \log n \rceil$ being available to all agents in each interaction.
- **uniform:** transition function computable by a single Turing machine with no knowledge of $n$.

Below all protocols will be nonuniform.

## Two methods for solving majority exactly in polylog(n) time

### Fast integer averaging (Alistarh, Gelashvili and Vojnovic, PODC 2015)

Assign A,B integer *biases*: bias(A) = $3n$ and bias(B) = $-3n$. (Or some power of 2 greater than $3n$ if we only have $\lceil \log n \rceil$ available)

Worst case of gap = 1 (one more A than B) means population-wide bias is $3n = \sum_{\text{agents } u} \mathrm{bias}(u)$.

Integer averaging protocol:
$i,j \to \lceil \frac{i+j}{2} \rceil, \lfloor \frac{i+j}{2} \rfloor$
(e.g., $-10,2 \to -4,-4$ and $3,12 \to 7,8$)

Preserves the population-wide bias.

Positive states vote for A; negative states vote for B.

- *Bad news:* Takes $\Omega(n)$ time to converge in worst case. (If converging to all agents having a single value $i$; eventually we have a single $i-1$, a single $i+1$, and $n-2$ $i$'s.)
- *Good news:* In $O(\log n)$ time reaches *three consecutive* values $i,i+1,i+2$. **Very sketchy proof:** Suppose 4 values exist: $i,i+1,i+2,i+3$. By pigeonhole at least one of them, call it $j$, has count $\geq n/4$. Can have reactions between $j$ and $k$ if $|j-k|\geq 2$. Then there's a fast reaction between $j$ and either $j-2$ or $j+2$, i.e., no need to rely on bottleneck reaction between two states both with count $o(n)$.

**Claim:** Population bias $\geq 3n \implies i > 0$. **Proof:** Otherwise, suppose $i=0$ and three consecutive values are $0,1,2$: even if all agents are $2$, no way for $n$ of them to add up to $3n$. Even worse if $i<0$. In other words all agents $u$ have the same $\mathrm{sign}(\mathrm{bias}(u)) = +$, so all agree majority opinion is A.

time = $O(\log n)$ (optimal)
states = $\Theta(n)$ (bad)

### Synchronized phases of cancel and split (most other papers)

#### Aside about synchonization
Population protocols are not naturally synchronized, but we can create high-probability synchonization, e.g., with a "leaderless phase clock":

Each agent has a field "hour" and another field "counter", initially $0$. On every interaction, the "receiver" (second agent) increments counter. Any agent to hit counter $= 4 \log n$ increments hour and sets counter back to $0$. Maximum hour propagates by epidemic:

$hour_1,hour_2 \to \max(hour_1,hour_2), \max(hour_1,hour_2)$

Agents also reset counter = 0 when increasing hour by this reaction.

With high probability:
- it takes $\geq 2 \log n$ time for the first agent to increment their hour, and
- it takes $\leq 2 \log n$ time for the new largest hour to propagate.

So with high probability, at any time all agents are in the same two consecutive hours: no two even-numbered hours will be present simultaneously.

We can divide computation into synchronized "phases" $p_0,p_1,p_2,p_3,\ldots$ where phase $p_i$ corresponds to hour $2i$.

#### Using synchonized phases to control cancel and split more carefully

States are *biases* $0,\pm 1, \pm \frac{1}{2}, \pm \frac{1}{4}, \pm \frac{1}{8},\ldots, \pm \frac{1}{2^L}$, where $L \approx \log n$. Initial biases are $A = +1, B = -1$.

$+ \frac{1}{2^{i}}, - \frac{1}{2^{i}} \to 0,0$ $\quad\quad$ (cancel: "most" agents cancel in $O(\log n)$ time, but some remain)
$\pm \frac{1}{2^{i}}, 0 \to \pm \frac{1}{2^{i+1}}, \pm \frac{1}{2^{i+1}}$ $\quad$ (split, e.g., $\frac{1}{4}, 0 \to \frac{1}{8}, \frac{1}{8}$; faster than cancel so all agents split WHP in $O(\log n)$ time)

Actually this doesn't work as stated. (See Fig. 1 in paper.) But it does work if we synchonize and allow split to level $i$ only in phases $p \geq i$:

$\pm \frac{1}{2^{i}}, 0_p \to \pm \frac{1}{2^{i+1}}, \pm \frac{1}{2^{i+1}}$,
where $0_p$ represents that agent is in phase $p$.

Cancel reactions preserve the difference in votes for A and B.

Each split reaction changes the difference.

Goal of cancel reactions: create enough $0_p$ agents to act as "fuel" so that all remaining agents can do one split in the next split phase.

One such successful round of cancel/split phases doubles the difference between counts of majority and minority agents.

Takes $\log n$ time per phase, and requires $\log n$ phases to double the difference until minority is gone.

time = $O(\log^2 n)$ (almost optimal)
states = $O(\log n)$ (probably optimal)

## Our paper

time = $O(\log n)$ (optimal)
states = $O(\log n)$ (probably optimal)

**Main idea:**
Use a faster phase clock, which still goes through $\log n$ hours, but takes $O(1)$ time per hour instead of $O(\log n)$ time per hour.

**Main analysis challenge:**
With $O(1)$ time per hour, there is not enough time for every opinionated agent to split before the next hour starts. In other words it's not "fully" synchronized. We need to analyze a more complex process where many agents are at different biases.

## "Fixed resolution" phase clock
$C_m,C_m \to C_m,C_{m+1}$ $\quad\quad\quad$ (drip reaction, increases "minute")
$C_i,C_m \to C_m,C_m$ if $i<m\quad$ (propogate highest minute by epidemic)

$C_m,0_h \to C_m,0_{h'}$ where $h' = \lfloor m/5 \rfloor$ $\quad$ (5 minutes per hour)

See Fig. 2 in paper.