Provided by: ETH Zurich
Date Added: Aug 2014
The authors study deterministic leader election in multi-hop radio networks in the beeping model. More specifically, they address explicit leader election: one node is elected as the leader, the other nodes know its identifier, and the algorithm terminates at some point with the network being quiescent. No initial knowledge of the network is assumed, i.e., nodes know neither the size of the network nor their degree; they only have a unique identifier. Their main contribution is a deterministic explicit leader election algorithm in the synchronous beeping model with a run time of O(Dlog n) rounds.