dc.contributor |
Háskólinn í Reykjavík |
dc.contributor |
Reykjavik University |
dc.contributor.author |
Halldórsson, Magnús M. |
dc.contributor.author |
Holzer, Stephan |
dc.contributor.author |
Markatou, Evangelia Anna |
dc.contributor.author |
Lynch, Nancy |
dc.date.accessioned |
2020-09-02T14:33:04Z |
dc.date.available |
2020-09-02T14:33:04Z |
dc.date.issued |
2020-04 |
dc.identifier.issn |
0304-3975 |
dc.identifier.issn |
1879-2294 (eISSN) |
dc.identifier.uri |
https://hdl.handle.net/20.500.11815/2033 |
dc.description |
Post-print (lokagerð höfundar) |
dc.description.abstract |
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 |
dc.description.sponsorship |
This work was funded by Icelandic Research Fund grants 152679-05, 174484-05,
AFOSR FA9550-13-1-0042, NSF CCF-1461559 and NSF CCF-0939370. |
dc.format.extent |
21-28 |
dc.language.iso |
en |
dc.publisher |
Elsevier BV |
dc.relation.ispartofseries |
Theoretical Computer Science;811 |
dc.rights |
info:eu-repo/semantics/openAccess |
dc.subject |
Theoretical Computer Science |
dc.subject |
Algorithms |
dc.subject |
Wireless communication systems |
dc.subject |
Tölvunarfræði |
dc.subject |
Reiknirit |
dc.subject |
Þráðlaus kerfi |
dc.title |
Leader election in SINR model with arbitrary power control |
dc.type |
info:eu-repo/semantics/article |
dcterms.license |
Post print (lokagerð höfundar) |
dc.description.version |
"Peer Reviewed" |
dc.identifier.journal |
Theoretical Computer Science;811 |
dc.identifier.doi |
10.1016/j.tcs.2019.01.024 |
dc.contributor.department |
Tölvunarfræðideild (HR) |
dc.contributor.department |
School of Computer Science (RU) |
dc.contributor.school |
Tæknisvið (HR) |
dc.contributor.school |
School of Technology (RU) |