TY - JOUR

T1 - Leader election in SINR model with arbitrary power control

AU - Halldórsson, Magnús M.

AU - Holzer, Stephan

AU - Markatou, Evangelia Anna

AU - Lynch, Nancy

PY - 2020/4

Y1 - 2020/4

N2 - We consider the Leader Election Problem in the Signal-to-Interference-plusNoise-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 Θ(log n) 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Ω(n) , even when n is known. We complement this with an algorithm that uses power range 2O˜(n)1, when n is known, and 2O˜(n 1.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/Θ(t) ) is sufficient and necessary

AB - We consider the Leader Election Problem in the Signal-to-Interference-plusNoise-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 Θ(log n) 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Ω(n) , even when n is known. We complement this with an algorithm that uses power range 2O˜(n)1, when n is known, and 2O˜(n 1.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/Θ(t) ) is sufficient and necessary

KW - Theoretical Computer Science

KW - Algorithms

KW - Wireless communication systems

KW - Tölvunarfræði

KW - Reiknirit

KW - Þráðlaus kerfi

KW - Theoretical Computer Science

KW - Algorithms

KW - Wireless communication systems

KW - Tölvunarfræði

KW - Reiknirit

KW - Þráðlaus kerfi

U2 - 10.1016/j.tcs.2019.01.024

DO - 10.1016/j.tcs.2019.01.024

M3 - Article

SP - 21

EP - 28

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -