Stable Leader Election in Population Protocols Requires Linear Time

A population protocol stably elects a leader if, for all $n$, starting from an initial configuration with $n$ agents each in an identical state, with probability 1 it reaches a configuration $\mathbf{y}$ that is correct (exactly one agent is in a special leader state $\mathrm{\ell }$) and stable (every configuration reachable from $\mathbf{y}$ also has a single agent in state $\mathrm{\ell }$). We show that any population protocol that stably elects a leader requires $\mathrm{\Omega }(n)$ expected “parallel time” — $\mathrm{\Omega }(n^2)$ expected total pairwise interactions — to reach such a stable configuration. Our result also informs the understanding of the time complexity of chemical self-organization by showing an essential difficulty in generating exact quantities of molecular species quickly.