Leader election in ad hoc radio networks: A keen ear helps

• Radio network modeled as an undirected graph, nodes do not know topology.
• Collision detection: capability of distinguishing collision from silence.
• Collision detection speeds up deterministic leader election.
• Deterministic leader election with collision detection in linear time.
• Without collision detection super-linear lower bound.

We address the fundamental distributed problem of leader election in ad hoc radio networks modeled as undirected graphs. A signal from a transmitting node reaches all neighbors but a message is received successfully by a node, if and only if exactly one of its neighbors transmits in this round. If two neighbors of a node transmit simultaneously in a given round, we say that a collision occurred at this node. Collision detection is the ability of nodes to distinguish a collision from silence. We show that collision detection speeds up leader election in arbitrary radio networks. Our main result is a deterministic leader election algorithm working in time O(n)O(n) in all n  -node networks, if collision detection is available, while it is known that deterministic leader election requires time Ω(nlogn), even for complete networks, if there is no collision detection.