Near-Optimal Leader Election in Population Protocols on Graphs

Dan Alistarh, Joel Rybicki, Sasha Voitovych

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…