How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model (Q692907)

Population protocols is one of the distributed computing models where a number of mobile agents change their states by pairwise interactions. A self-stabilizing protocol ensures that the system converges to the desired behavior regardless its initial configuration. A leader election allows to distinguish a single agent with the final state ELECTED, the state of the other agents is NON-ELECTED. Global fairness guarantees the occurrence of any possible transition. This paper proves that under the assumption of global fairness, no protocol using only \(n-1\) states (where \(n\) is the number of agents) can solve the self-stabilizing leader election in complete interaction graphs.