Leader election in shared spectrum radio networks
Sebastian Daum, Seth Lewis Gilbert, Fabian Kühn, Calvin C. Newport · 2012
We study the leader election problem in the context of a congested single-hop radio network. We assume a collection of N synchronous devices with access to a shared band of the radio spectrum, divided into F frequencies. To model unpredictable congestion, we assume an abstract interference adversary that can choose up to t < F frequencies in each round to disrupt, preventing communication. The devices are individually activated in arbitrary rounds by an adversary. On activation, a device does not know how many other devices (if any) are also active. The goal of the leader election problem is for each active device to output the id of a leader as soon as possible after activation, while preserving the safety constraint that all devices output the same leader, with high probability.