  In the stochastic population protocol model, we are given a connected graph
with $n$ nodes, and in every time step, a scheduler samples an edge of the
graph uniformly at random and the nodes connected by this edge interact. A
fundamental task in this model is stable leader election, in which all nodes
start in an identical state and the aim is to reach a configuration in which
(1) exactly one node is elected as leader and (2) this node remains as the
unique leader no matter what sequence of interactions follows. On cliques, the
complexity of this problem has recently been settled: time-optimal protocols
stabilize in $\Theta(n \log n)$ expected steps using $\Theta(\log \log n)$
states, whereas protocols that use $O(1)$ states require $\Theta(n^2)$ expected
steps.
  In this work, we investigate the complexity of stable leader election on
graphs. We provide the first non-trivial time lower bounds on general graphs,
showing that, when moving beyond cliques, the complexity of stable leader
election can range from $O(1)$ to $\Theta(n^3)$ expected steps. We describe a
protocol that is time-optimal on many graph families, but uses
polynomially-many states. In contrast, we give a near-time-optimal protocol
that uses only $O(\log^2n)$ states that is at most a factor $O(\log n)$ slower.
Finally, we observe that for many graphs the constant-state protocol of
Beauquier et al. [OPODIS 2013] is at most a factor $O(n \log n)$ slower than
the fast polynomial-state protocol, and among constant-state protocols, this
protocol has near-optimal average case complexity on dense random graphs.

Distributed, Parallel, and Cluster Computing