{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:51Z","timestamp":1750219791805,"version":"3.41.0"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,20]],"date-time":"2023-06-20T00:00:00Z","timestamp":1687219200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Polish National Science Center NCN","award":["UMO-2017\/25\/B\/ST6\/02553"],"award-info":[{"award-number":["UMO-2017\/25\/B\/ST6\/02553"]}]},{"name":"NSF","award":["2131538"],"award-info":[{"award-number":["2131538"]}]},{"name":"Pace University SR Grant and Kenan Fund"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>How do we reach consensus on an average value in a dynamic crowd without revealing identity? In this work, we study the problem of average network consensus in Anonymous Dynamic Networks (ADN). Network dynamicity is specified by the sequence of topology-graph isoperimetric numbers occurring over time, which we call the isoperimetric dynamicity of the network. The consensus variable is the average of values initially held by nodes, which is customary in the network-consensus literature. Given that having an algorithm to compute the average one can compute the network size (i.e., the counting problem) and vice versa, we focus\u00a0on\u00a0the\u00a0latter.<\/jats:p>\n          <jats:p>We present a deterministic distributed average network consensus algorithm for ADNs that we call isoperimetric Scalable Coordinated Anonymous Local Aggregation, and we analyze its performance for different scenarios, including worst-case (adversarial) and stochastic dynamic topologies. Our solution utilizes supervisor nodes, which have been shown to be necessary for computations in ADNs. The algorithm uses the isoperimetric dynamicity of the network as an input, meaning that only the isoperimetric\u00a0number parameters (or their lower bound) must be given, but topologies may occur arbitrarily or stochastically as long as they comply with those parameters.<\/jats:p>\n          <jats:p>Previous work for adversarial ADNs overestimates the running time to deal with worst-case scenarios. For ADNs with given isoperimetric dynamicity, our analysis shows improved performance for some practical dynamic topologies, with cubic time or better for stochastic ADNs, and our experimental evaluation indicates that our theoretical bounds could not be substantially improved for some models of dynamic networks.<\/jats:p>","DOI":"10.1145\/3593426","type":"journal-article","created":{"date-parts":[[2023,4,24]],"date-time":"2023-04-24T12:12:01Z","timestamp":1682338321000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Faster Supervised Average Consensus in Adversarial and Stochastic Anonymous Dynamic Networks"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-7125-628X","authenticated-orcid":false,"given":"Aleksandar","family":"Kamenev","sequence":"first","affiliation":[{"name":"Pace University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1316-7788","authenticated-orcid":false,"given":"Dariusz R.","family":"Kowalski","sequence":"additional","affiliation":[{"name":"Augusta University, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5842-6256","authenticated-orcid":false,"given":"Miguel A.","family":"Mosteiro","sequence":"additional","affiliation":[{"name":"Pace University, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,20]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/0471478210"},{"key":"e_1_3_3_3_2","volume-title":"Random Geometric Graphs: An Algorithmic Perspective","author":"Avin Chen","year":"2006","unstructured":"Chen Avin. 2006. Random Geometric Graphs: An Algorithmic Perspective. Ph.D. Dissertation. University of California, Los Angeles, Los Angeles, CA."},{"key":"e_1_3_3_4_2","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/978-3-540-70575-8_11","volume-title":"Automata, Languages and Programming","author":"Avin Chen","year":"2008","unstructured":"Chen Avin, Michal Kouck\u1ef3, and Zvi Lotker. 2008. How to explore a fast-changing world (cover time of a simple random walk on evolving graphs). In Automata, Languages and Programming. Springer, 121\u2013132."},{"key":"e_1_3_3_5_2","unstructured":"Roberto Baldoni and Giuseppe A. Di Luna. 2016. Counting on anonymous dynamic networks: Bounds and algorithms. University of Rome Tech. Report BD_C 16 (2016). http:\/\/midlab.dis.uniroma1.it\/articoli\/techrepBD_C16.pdf."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2316801"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1038\/scientificamerican0503-60"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.5555\/1323937.1323940"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1982.1102982"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874516"},{"key":"e_1_3_3_12_2","doi-asserted-by":"crossref","unstructured":"Stephen Boyd Arpita Ghosh Balaji Prabhakar and Devavrat Shah. 2006. Randomized gossip algorithms. IEEE\/ACM Transactions on Networking 14 SI (2006) 2508\u20132530.","DOI":"10.1109\/TIT.2006.874516"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90093-3"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2005.1582514"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46140-3_10"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0367-4"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2247462"},{"key":"e_1_3_3_18_2","series-title":"Proceedings of the 34th International Symposium on Distributed Computing (DISC\u201920)","first-page":"30:1\u201330:18","volume":"179","author":"Chlebus Bogdan S.","year":"2020","unstructured":"Bogdan S. Chlebus, Dariusz R. Kowalski, and Jan Olkowski. 2020. Fast agreement in networks with byzantine nodes. In Proceedings of the 34th International Symposium on Distributed Computing (DISC\u201920), LIPIcs, Vol. 179. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 30:1\u201330:18."},{"key":"e_1_3_3_19_2","unstructured":"Bogdan S. Chlebus Dariusz R. Kowalski Jan Olkowski and Jedrzej Olkowski. 2021. Consensus in networks prone to link failures. arxiv:2102.01251. Retrieved from https:\/\/arxiv.org\/abs\/2102.01251."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10009-020-00576-x"},{"key":"e_1_3_3_21_2","unstructured":"Leibniz-Zentrum f\u00fcr Informatik Proceedings of the 19th International Conference on Principles of Distributed Systems Giuseppe Antonio Di Luna Roberto Baldoni Non trivial computations in anonymous dynamic networks 2015"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-45249-9_17"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2014.42"},{"key":"e_1_3_3_24_2","series-title":"Proceedings of the 9th Algosensors","first-page":"139","volume":"8243","author":"Luna Giuseppe Antonio Di","year":"2014","unstructured":"Giuseppe Antonio Di Luna, Silvia Bonomi, Ioannis Chatzigiannakis, and Roberto Baldoni. 2014. Counting in anonymous dynamic networks: An experimental perspective. In Proceedings of the 9th Algosensors, LNCS, Vol. 8243. Springer, 139\u2013154."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.2307\/1999107"},{"key":"e_1_3_3_26_2","volume-title":"Random Graph Dynamics","author":"Durrett Richard","year":"2007","unstructured":"Richard Durrett. 2007. Random Graph Dynamics. Vol. 200. Citeseer."},{"key":"e_1_3_3_27_2","doi-asserted-by":"crossref","unstructured":"P. Erd\u0151s and A. R\u00e9nyi. 1959. On random graphs I. Publicationes Mathematicae Debrecen 6 (1959) 290\u2013297.","DOI":"10.5486\/PMD.1959.6.3-4.12"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29344-3_26"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.64.026704"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0165-9"},{"issue":"04","key":"e_1_3_3_31_2","first-page":"445","article-title":"Contention resolution in multiple-access channels: k-selection in radio networks","volume":"02","author":"Anta A. Fern\u00e1ndez","year":"2010","unstructured":"A. Fern\u00e1ndez Anta and M. A. Mosteiro. 2010. Contention resolution in multiple-access channels: k-selection in radio networks. Discr. Math. Algor. Appl. 02, 04 (2010), 445\u2013456.","journal-title":"Discr. Math. Algor. Appl."},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2012.09.013"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0075"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706098"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10114-012-0387-6"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2003.812781"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/NANO.2016.7751543"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946317"},{"key":"e_1_3_3_41_2","first-page":"180","volume-title":"International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics","author":"Kowalski Dariusz R.","year":"2018","unstructured":"Dariusz R. Kowalski and Jaros\u0142aw Mirek. 2018. Reaching consensus in ad-hoc diffusion networks. In International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics. Springer, 180\u2013192."},{"key":"e_1_3_3_42_2","first-page":"156:1\u2013156:14","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming","author":"Kowalski Dariusz R.","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. 156:1\u2013156:14."},{"key":"e_1_3_3_43_2","series-title":"Proceedings of the 46th International Colloquium on Automata, Languages, and Programming","first-page":"147:1\u2013147:15","volume":"132","author":"Kowalski Dariusz R.","year":"2019","unstructured":"Dariusz R. Kowalski and Miguel A. Mosteiro. 2019. Polynomial anonymous dynamic distributed computing without a unique leader. In Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, LIPIcs, Vol. 132. Leibniz-Zentrum f\u00fcr Informatik, 147:1\u2013147:15."},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3385075"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461811"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS51616.2021.00050"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2021.07.002"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2003.1272825"},{"key":"e_1_3_3_49_2","volume-title":"Distributed Algorithms","author":"Lynch Nancy A.","year":"1996","unstructured":"Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kauffman."},{"key":"e_1_3_3_50_2","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/978-3-319-03089-0_20","volume-title":"Stabilization, Safety, and Security of Distributed Systems","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\u2013295."},{"key":"e_1_3_3_51_2","series-title":"Proceedings of the 19th International Conference on Principles of Distributed Systems","first-page":"1","volume":"46","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 Principles of Distributed Systems, Vol. 46. Leibniz-Zentrum f\u00fcr Informatik, 1\u201313."},{"key":"e_1_3_3_52_2","volume-title":"Elementary Inequalities","author":"Mitrinovi\u0107 D. S.","year":"1964","unstructured":"D. S. Mitrinovi\u0107. 1964. Elementary Inequalities. P. Noordhoff Ltd., Groningen."},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(89)90029-4"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2003.1273094"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.924648"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2004.834113"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198506263.001.0001"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743520"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.909171"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.02.044"},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1986.1104412"},{"key":"e_1_3_3_63_2","volume-title":"Problems in Decentralized Decision Making and Computation.","author":"Tsitsiklis John Nikolas","year":"1984","unstructured":"John Nikolas Tsitsiklis. 1984. Problems in Decentralized Decision Making and Computation.Technical Report, Cambridge Lab for Information and Decision Systems, Massachusetts Institute of Technology."},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1109\/JIOT.2021.3074877"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3593426","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3593426","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3593426","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:38:00Z","timestamp":1750178280000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3593426"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,20]]},"references-count":64,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3593426"],"URL":"https:\/\/doi.org\/10.1145\/3593426","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"type":"print","value":"2329-4949"},{"type":"electronic","value":"2329-4957"}],"subject":[],"published":{"date-parts":[[2023,6,20]]},"assertion":[{"value":"2022-04-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-04-18","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}