  Population protocols are networks of finite-state agents, interacting
randomly, and updating their states using simple rules. Despite their extreme
simplicity, these systems have been shown to cooperatively perform complex
computational tasks, such as simulating register machines to compute standard
arithmetic functions. The election of a unique leader agent is a key
requirement in such computational constructions. Yet, the fastest currently
known population protocol for electing a leader only has linear stabilization
time, and, it has recently been shown that no population protocol using a
constant number of states per node may overcome this linear bound.
  In this paper, we give the first population protocol for leader election with
polylogarithmic stabilization time, using polylogarithmic memory states per
node. The protocol structure is quite simple: each node has an associated
value, and is either a leader (still in contention) or a minion (following some
leader). A leader keeps incrementing its value and "defeats" other leaders in
one-to-one interactions, and will drop from contention and become a minion if
it meets a leader with higher value. Importantly, a leader also drops out if it
meets a minion with higher absolute value. While these rules are quite simple,
the proof that this algorithm achieves polylogarithmic stabilization time is
non-trivial. In particular, the argument combines careful use of concentration
inequalities with anti-concentration bounds, showing that the leaders' values
become spread apart as the execution progresses, which in turn implies that
straggling leaders get quickly eliminated. We complement our analysis with
empirical results, showing that our protocol stabilizes extremely fast, even
for large network sizes.
