{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,2]],"date-time":"2023-01-02T05:54:56Z","timestamp":1672638896047},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"name":"National Science Center Poland","award":["2017\/25\/B\/ST6\/02553"]},{"DOI":"10.13039\/501100000288","name":"Royal Society","doi-asserted-by":"crossref","award":["170293"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"\n Starting with with work of Michail et al., the problem of\n Counting<\/jats:italic>\n 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\n mass-distribution<\/jats:italic>\n 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 M\n ethodical<\/jats:sc>\n C\n ounting<\/jats:sc>\n , which runs in polynomial time and requires no knowledge of network characteristics. Moreover, we also show how to extend M\n ethodical<\/jats:sc>\n C\n ounting<\/jats:sc>\n 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.\n <\/jats:p>","DOI":"10.1145\/3385075","type":"journal-article","created":{"date-parts":[[2020,5,4]],"date-time":"2020-05-04T07:14:28Z","timestamp":1588576468000},"page":"1-17","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Polynomial Counting in Anonymous Dynamic Networks with Applications to Anonymous Dynamic Algebraic Computations"],"prefix":"10.1145","volume":"67","author":[{"given":"Dariusz R.","family":"Kowalski","sequence":"first","affiliation":[{"name":"Augusta University and SWPS University of Social Sciences and Humanities, Warszawa, Poland"}]},{"ORCID":"http:\/\/orcid.org\/0000-0001-5842-6256","authenticated-orcid":false,"given":"Miguel A.","family":"Mosteiro","sequence":"additional","affiliation":[{"name":"Pace University, New York, NY, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,4,17]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Cover time and mixing time of random walks on dynamic graphs. Random Structures 8 Algorithms 52, 4","author":"Avin Chen","year":"2018","unstructured":"Chen Avin , Michal Kouck\u1ef3 , and Zvi Lotker . 2018. Cover time and mixing time of random walks on dynamic graphs. Random Structures 8 Algorithms 52, 4 ( 2018 ), 576--596. Chen Avin, Michal Kouck\u1ef3, and Zvi Lotker. 2018. Cover time and mixing time of random walks on dynamic graphs. Random Structures 8 Algorithms 52, 4 (2018), 576--596."},{"key":"e_1_2_1_2_1","volume-title":"Di Luna","author":"Baldoni Roberto","year":"2016","unstructured":"Roberto Baldoni and Giuseppe A . Di Luna . 2016 . Counting on Anonymous Dynamic Networks: Bounds and Algorithms. Unpublished manuscript. Roberto Baldoni and Giuseppe A. Di Luna. 2016. Counting on Anonymous Dynamic Networks: Bounds and Algorithms. Unpublished manuscript."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2316801"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874516"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1080\/17445760.2012.668546"},{"key":"e_1_2_1_6_1","volume-title":"Mosteiro","author":"Chakraborty Maitri","year":"2016","unstructured":"Maitri Chakraborty , Alessia Milani , and Miguel A . Mosteiro . 2016 . Counting in practical anonymous dynamic networks is polynomial. In Networked Systems. Lecture Notes in Computer Science, Vol. 9944 . Springer , 131--136. DOI:https:\/\/doi.org\/10.1007\/978-3-319-46140-3_10 10.1007\/978-3-319-46140-3_10 Maitri Chakraborty, Alessia Milani, and Miguel A. Mosteiro. 2016. Counting in practical anonymous dynamic networks is polynomial. In Networked Systems. Lecture Notes in Computer Science, Vol. 9944. Springer, 131--136. DOI:https:\/\/doi.org\/10.1007\/978-3-319-46140-3_10"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2247462"},{"key":"e_1_2_1_8_1","series-title":"Lecture Notes in Computer Science","volume-title":"Distributed Computing and Networking","author":"Di Luna Giuseppe Antonio","unstructured":"Giuseppe Antonio Di Luna , Roberto Baldoni , Silvia Bonomi , and Ioannis Chatzigiannakis . 2014. Conscious and unconscious counting on anonymous dynamic networks . In Distributed Computing and Networking . Lecture Notes in Computer Science , Vol. 8314 . Springer , 257--271. Giuseppe Antonio Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis. 2014. Conscious and unconscious counting on anonymous dynamic networks. In Distributed Computing and Networking. Lecture Notes in Computer Science, Vol. 8314. Springer, 257--271."},{"key":"e_1_2_1_9_1","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithms for Sensor Systems","author":"Di Luna Giuseppe Antonio","unstructured":"Giuseppe Antonio Di Luna , Silvia Bonomi , Ioannis Chatzigiannakis , and Roberto Baldoni . 2014. Counting in anonymous dynamic networks: An experimental perspective . In Algorithms for Sensor Systems . Lecture Notes in Computer Science , Vol. 8243 . Springer , 139--154. Giuseppe Antonio Di Luna, Silvia Bonomi, Ioannis Chatzigiannakis, and Roberto Baldoni. 2014. Counting in anonymous dynamic networks: An experimental perspective. In Algorithms for Sensor Systems. Lecture Notes in Computer Science, Vol. 8243. Springer, 139--154."},{"key":"e_1_2_1_10_1","volume-title":"Lecture Notes in Computer Science","volume":"7256","author":"Farach-Colton M.","unstructured":"M. Farach-Colton , A. Fern\u00e1ndez Anta , A. Milani , M. A. Mosteiro , and S. Zaks . 2012. Opportunistic information dissemination in mobile ad-hoc networks: Adaptiveness vs. obliviousness and randomization vs. determinism. In Latin 2012: Theoretical Informatics . Lecture Notes in Computer Science , Vol. 7256 . Springer, 303--314. M. Farach-Colton, A. Fern\u00e1ndez Anta, A. Milani, M. A. Mosteiro, and S. Zaks. 2012. Opportunistic information dissemination in mobile ad-hoc networks: Adaptiveness vs. obliviousness and randomization vs. determinism. In Latin 2012: Theoretical Informatics. Lecture Notes in Computer Science, Vol. 7256. Springer, 303--314."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9905-5"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0165-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1142\/S1793830910000796"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238221"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918)","author":"Dariusz","year":"2018","unstructured":"Dariusz R. Kowalski and Miguel A. Mosteiro. 2018. Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations . In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918) . Article 156, 14 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP. 2018 .156 10.4230\/LIPIcs.ICALP.2018.156 Dariusz R. Kowalski and Miguel A. Mosteiro. 2018. Polynomial counting in anonymous dynamic networks with applications to anonymous dynamic algebraic computations. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP\u201918). Article 156, 14 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2018.156"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1086"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806760"},{"key":"e_1_2_1_18_1","unstructured":"Giuseppe Antonio Di Luna and Roberto Baldoni. 2015. Investigating the cost of anonymity on dynamic networks. arxiv:1505.03509. Giuseppe Antonio Di Luna and Roberto Baldoni. 2015. Investigating the cost of anonymity on dynamic networks. arxiv:1505.03509."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS\u201915)","author":"Di Luna Giuseppe Antonio","year":"2015","unstructured":"Giuseppe Antonio Di Luna and Roberto Baldoni . 2015 . Non trivial computations in anonymous dynamic networks . In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS\u201915) . Article 33, 16 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS. 2015.33 10.4230\/LIPIcs.OPODIS.2015.33 Giuseppe Antonio Di Luna and Roberto Baldoni. 2015. Non trivial computations in anonymous dynamic networks. In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS\u201915). Article 33, 16 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2015.33"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 34th International Conference on Distributed Computing Systems (ICDCS\u201914)","author":"Di Luna Giuseppe Antonio","year":"2014","unstructured":"Giuseppe Antonio Di Luna , Roberto Baldoni , Silvia Bonomi , and Ioannis Chatzigiannakis . 2014 . Counting in anonymous dynamic networks under worst-case adversary . In Proceedings of the 34th International Conference on Distributed Computing Systems (ICDCS\u201914) . IEEE, Los Alamitos, CA, 338--347. DOI:https:\/\/doi.org\/10.1109\/ICDCS. 2014.42 10.1109\/ICDCS.2014.42 Giuseppe Antonio Di Luna, Roberto Baldoni, Silvia Bonomi, and Ioannis Chatzigiannakis. 2014. Counting in anonymous dynamic networks under worst-case adversary. In Proceedings of the 34th International Conference on Distributed Computing Systems (ICDCS\u201914). IEEE, Los Alamitos, CA, 338--347. DOI:https:\/\/doi.org\/10.1109\/ICDCS.2014.42"},{"key":"e_1_2_1_21_1","volume-title":"Spirakis","author":"Michail Othon","year":"2013","unstructured":"Othon Michail , Ioannis Chatzigiannakis , and Paul G . Spirakis . 2013 . Naming and counting in anonymous unknown dynamic networks. In Stabilization, Safety, and Security of Distributed Systems. Springer , 281--295. Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis. 2013. Naming and counting in anonymous unknown dynamic networks. In Stabilization, Safety, and Security of Distributed Systems. Springer, 281--295."},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 19th International Conference on Distributed Systems (OPODIS\u201915)","author":"Milani Alessia","year":"2015","unstructured":"Alessia Milani and Miguel A. Mosteiro . 2015. A faster counting protocol for anonymous dynamic networks . In Proceedings of the 19th International Conference on Distributed Systems (OPODIS\u201915) . Article 28, 13 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS. 2015 .28 10.4230\/LIPIcs.OPODIS.2015.28 Alessia Milani and Miguel A. Mosteiro. 2015. A faster counting protocol for anonymous dynamic networks. In Proceedings of the 19th International Conference on Distributed Systems (OPODIS\u201915). Article 28, 13 pages. DOI:https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2015.28"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.924648"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2009.2031203"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.909171"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3385075","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T07:07:09Z","timestamp":1672556829000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3385075"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,17]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3385075"],"URL":"http:\/\/dx.doi.org\/10.1145\/3385075","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2020,4,17]]},"assertion":[{"value":"2019-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-17","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}