Stable Leader Election in Population Protocols Requires Linear Time

David Doty, David Soloveichik

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 c…