Near-Optimal Leader Election in Population Protocols on Graphs

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 Θ (n log n) Θ ( n log n ) expected steps using Θ (log log n) Θ ( log log n ) states, whereas protocols that use O (1) states require Θ (n²) Θ ( 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 Θ (n³) Θ ( 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 ²n) O ( log 2 n ) states that is at most a factor O(log n) 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) 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.