TY - JOUR
T1 - Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations
AU - Kowalski, Dariusz R.
AU - Mosteiro, Miguel A.
N1 - Funding Information:
An extended abstract of this work was published at ICALP 2018 [15] and received the Track C Best Paper Award. This work was supported by National Science Center Poland (NCN) Grant 2017/25/B/ST6/02553, UK Royal Society International Exchanges 2017 Round 3 Grant #170293, and the Pace University SRC Grant and Kenan Fund. Authors’ addresses: D. R. Kowalski, School of Computer and Cyber Sciences, Augusta University, 1120 15th Street, Augusta, GA 30912, USA and SWPS University of Social Sciences and Humanities, Chodakowska 19/31, 03-815 Warszawa, Poland; email; dkowalski@augusta.edu; M. A. Mosteiro, Computer Science Department, Pace University, One Pace Plaza, New York, NY 10038, USA; email: mmosteiro@pace.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2020 Association for Computing Machinery. 0004-5411/2020/04-ART11 $15.00 https://doi.org/10.1145/3385075
Publisher Copyright:
© 2020 ACM.
PY - 2020/5/4
Y1 - 2020/5/4
N2 - Starting with with work of Michail et al., the problem of Counting the number of nodes in Anonymous Dynamic Networks has attracted a lot of attention. The problem is challenging because nodes are indistinguishable (they lack identifiers and execute the same program), and the topology may change arbitrarily from round to round of communication, as long as the network is connected in each round. The problem is central in distributed computing, as the number of participants is frequently needed to make important decisions, including termination, agreement, synchronization, among others. A variety of distributed algorithms built on top of mass-distribution techniques have been presented, analyzed, and experimentally evaluated; some of them assumed additional knowledge of network characteristics, such as bounded degree or given upper bound on the network size. However, the question of whether Counting can be solved deterministically in sub-exponential time remained open. In this work, we answer this question positively by presenting Methodical Counting, which runs in polynomial time and requires no knowledge of network characteristics. Moreover, we also show how to extend Methodical Counting to compute the sum of input values and more complex functions without extra cost. Our analysis leverages previous work on random walks in evolving graphs, combined with carefully chosen alarms in the algorithm that control the process and its parameters. To the best of our knowledge, our Counting algorithm and its extensions to other algebraic and Boolean functions are the first that can be implemented in practice with worst-case guarantees.
AB - Starting with with work of Michail et al., the problem of Counting the number of nodes in Anonymous Dynamic Networks has attracted a lot of attention. The problem is challenging because nodes are indistinguishable (they lack identifiers and execute the same program), and the topology may change arbitrarily from round to round of communication, as long as the network is connected in each round. The problem is central in distributed computing, as the number of participants is frequently needed to make important decisions, including termination, agreement, synchronization, among others. A variety of distributed algorithms built on top of mass-distribution techniques have been presented, analyzed, and experimentally evaluated; some of them assumed additional knowledge of network characteristics, such as bounded degree or given upper bound on the network size. However, the question of whether Counting can be solved deterministically in sub-exponential time remained open. In this work, we answer this question positively by presenting Methodical Counting, which runs in polynomial time and requires no knowledge of network characteristics. Moreover, we also show how to extend Methodical Counting to compute the sum of input values and more complex functions without extra cost. Our analysis leverages previous work on random walks in evolving graphs, combined with carefully chosen alarms in the algorithm that control the process and its parameters. To the best of our knowledge, our Counting algorithm and its extensions to other algebraic and Boolean functions are the first that can be implemented in practice with worst-case guarantees.
KW - Anonymous Dynamic Networks
KW - Boolean functions
KW - counting
KW - deterministic algorithms
KW - distributed algorithms
UR - http://www.scopus.com/inward/record.url?scp=85085739741&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85085739741&partnerID=8YFLogxK
U2 - 10.1145/3385075
DO - 10.1145/3385075
M3 - Article
AN - SCOPUS:85085739741
SN - 0004-5411
VL - 67
JO - Journal of the ACM
JF - Journal of the ACM
IS - 2
M1 - 11
ER -