Self-Stabilizing Leader Election for Single-Hop Wireless Networks Despite Jamming
Electing a leader is a fundamental task in distributed computations. Many coordination problems, such as the access to a shared resource, and the resulting inefficiencies, can be avoided by relying on a leader. This paper presents SELECT, a leader election protocol for wireless networks where nodes communicate over a shared medium. SELECT is very robust in two respects. First, the protocol is self-stabilizing in the sense that it converges to a correct solution from any possible initial network state (e.g., where no or multiple nodes consider themselves a leader). This is an appealing property, especially for dynamic networks. Second, the described protocol is resilient against a powerful reactive jammer that blocks a significant fraction of all communication rounds.