Leader election in SINR model with arbitrary power control

We consider 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 elect a leader in two communication rounds, with high probability. Previously, it was known that Theta(logn) rounds were sufficient and necessary when using uniform power, where n is the number of nodes in the network. We then examine how much power control is needed to achieve fast leader election. We show that every 2-round leader election algorithm in the SINR model running correctly w.h.p. requires a power range 2(Omega(n)), even when n is known. We complement this with an algorithm that uses power range 2((o) over tilde (n)1), when n is known, and 2((o) over tilde (n1.5)), when n is not known. We also explore tradeoffs between time and power used, and show that to elect a leader in t rounds, a range of possible power levels of size exp(n(1/Theta(t))) is sufficient and necessary. (C) 2019 Elsevier B.V. All rights reserved.