We study the leader election problem in a theoretical wireless network setting. We show that it can be solved in two communication rounds.

We study the Leader Election Problem in the Signal-to-Interference-plus-Noise-Ratio (SINR) model where nodes can adjust their transmission power. We show that in this setting it is possible to solve the leader election problem in two communication rounds, with high probability. Previously, it was known that Ω(log n) rounds were sufficient and necessary when using uniform power, where n is the number of nodes in the network.

Research Areas


Magnus Halldorsson

Stephan Holzer