TY - GEN
T1 - Polynomial anonymous dynamic distributed computing without a unique leader
AU - Kowalski, Dariusz R.
AU - Mosteiro, Miguel A.
N1 - Funding Information:
Funding This work was supported by the National Science Center Poland (NCN) grant 2017/25/B/ ST6/02553; the UK Royal Society International Exchanges 2017 Round 3 Grant #170293; and Pace University SR Grant and Kenan Fund.
Funding Information:
This work was supported by the National Science Center Poland (NCN) grant 2017/25/B/ ST6/02553; the UK Royal Society International Exchanges 2017 Round 3 Grant #170293; and Pace University SR Grant and Kenan Fund.
Publisher Copyright:
© Dariusz R. Kowalski and Miguel A. Mosteiro; licensed under Creative Commons License CC-BY
PY - 2019/7/1
Y1 - 2019/7/1
N2 - Counting the number of nodes in Anonymous Dynamic Networks is enticing from an algorithmic perspective: an important computation in a restricted platform with promising applications. Starting with Michail, Chatzigiannakis, and Spirakis [18], a flurry of papers sped up the running time guarantees from doubly-exponential to polynomial [16]. There is a common theme across all those works: a distinguished node is assumed to be present, because Counting cannot be solved deterministically without at least one. In the present work we study challenging questions that naturally follow: how to efficiently count with more than one distinguished node, or how to count without any distinguished node. More importantly, what is the minimal information needed about these distinguished nodes and what is the best we can aim for (count precision, stochastic guarantees, etc.) without any. We present negative and positive results to answer these questions. To the best of our knowledge, this is the first work that addresses them.
AB - Counting the number of nodes in Anonymous Dynamic Networks is enticing from an algorithmic perspective: an important computation in a restricted platform with promising applications. Starting with Michail, Chatzigiannakis, and Spirakis [18], a flurry of papers sped up the running time guarantees from doubly-exponential to polynomial [16]. There is a common theme across all those works: a distinguished node is assumed to be present, because Counting cannot be solved deterministically without at least one. In the present work we study challenging questions that naturally follow: how to efficiently count with more than one distinguished node, or how to count without any distinguished node. More importantly, what is the minimal information needed about these distinguished nodes and what is the best we can aim for (count precision, stochastic guarantees, etc.) without any. We present negative and positive results to answer these questions. To the best of our knowledge, this is the first work that addresses them.
KW - Anonymous Dynamic Networks
KW - Counting
KW - Distributed algorithms
UR - http://www.scopus.com/inward/record.url?scp=85069213672&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85069213672&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ICALP.2019.147
DO - 10.4230/LIPIcs.ICALP.2019.147
M3 - Conference contribution
AN - SCOPUS:85069213672
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
A2 - Baier, Christel
A2 - Chatzigiannakis, Ioannis
A2 - Flocchini, Paola
A2 - Leonardi, Stefano
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019
Y2 - 9 July 2019 through 12 July 2019
ER -