{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,5]],"date-time":"2026-09-05T16:41:20Z","timestamp":1788626480863,"version":"build-2803163510"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T00:00:00Z","timestamp":1635379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Austrian Science Fund","award":["SIC (P26436 FWF) and ADynNet (P28182 FWF)"],"award-info":[{"award-number":["SIC (P26436 FWF) and ADynNet (P28182 FWF)"]}]},{"DOI":"10.13039\/501100004794","name":"Centre National de la Recherche Scientifique","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004794","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DigiCosme working group HicDiesMeus"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>Agreeing on a common value among a set of agents is a fundamental problem in distributed computing, which occurs in several variants: In contrast to exact consensus, approximate variants are studied in systems where exact agreement is not possible or required, e.g., in human-made distributed control systems and in the analysis of natural distributed systems, such as bird flocking and opinion dynamics.<\/jats:p>\n          <jats:p>We study the time complexity of two classical agreement problems: non-terminating asymptotic consensus and terminating approximate consensus. Asymptotic consensus, requires agents to repeatedly set their outputs such that the outputs converge to a common value within the convex hull of initial values; approximate consensus requires agents to eventually stop setting their outputs, which must then lie within a predefined distance of each other.<\/jats:p>\n          <jats:p>We prove tight lower bounds on the contraction ratios of asymptotic consensus algorithms subject to oblivious message adversaries, from which we deduce bounds on the time complexity of approximate consensus algorithms. In particular, the obtained bounds show optimality of asymptotic and approximate consensus algorithms presented by Charron-Bost et\u00a0al. (ICALP\u201916) for certain systems, including the strongest oblivious message adversary in which asymptotic and approximate consensus are solvable. As a corollary we also obtain asymptotically tight bounds for asymptotic consensus in the classical asynchronous model with crashes.<\/jats:p>\n          <jats:p>Central to the lower-bound proofs is an extended notion of valency, the set of reachable limits of an asymptotic consensus algorithm starting from a given configuration. We further relate topological properties of valencies to the solvability of exact consensus, shedding some light on the relation of these three fundamental problems in dynamic networks.<\/jats:p>","DOI":"10.1145\/3485242","type":"journal-article","created":{"date-parts":[[2021,10,28]],"date-time":"2021-10-28T17:40:31Z","timestamp":1635442831000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Tight Bounds for Asymptotic and Approximate Consensus"],"prefix":"10.1145","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5765-0301","authenticated-orcid":false,"given":"Matthias","family":"F\u00fcgger","sequence":"first","affiliation":[{"name":"CNRS, LMF, ENS Paris-Saclay, Universit\u00e9 Paris-Saclay, Inria, Gif-sur-Yvette, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1690-9342","authenticated-orcid":false,"given":"Thomas","family":"Nowak","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris-Saclay, CNRS, Gif-sur-Yvette, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Manfred","family":"Schwarz","sequence":"additional","affiliation":[{"name":"TU Wien, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,10,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11516798_17"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-018-0345-3"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90056-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00498-006-0006-0"},{"key":"e_1_2_1_5_1","volume-title":"Murray","author":"Astr\u00f6m Karl Johan","year":"2008"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/21.156582"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90020-F"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 47th IEEE Conference on Decision and Control, and the European Control Conference (CDC-ECC\u201908)","author":"Bliman Pierre-Alexandre"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.15803\/ijnc.6.1_27"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/060657029"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 44th IEEE Conference on Decision and Control, and the European Control Conference (CDC-ECC\u201905)","author":"Cao Ming"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.10.012"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1186\/s13173-017-0065-8"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1080\/17445760.2012.668546"},{"key":"e_1_2_1_15_1","unstructured":"Bernadette Charron-Bost Matthias F\u00fcgger and Thomas Nowak. 2014. Approximate consensus in highly dynamic networks. arXiv:1408.0620. Retrieved from http:\/\/arxiv.org\/abs\/1408.0620.  Bernadette Charron-Bost Matthias F\u00fcgger and Thomas Nowak. 2014. Approximate consensus in highly dynamic networks. arXiv:1408.0620. Retrieved from http:\/\/arxiv.org\/abs\/1408.0620."},{"key":"e_1_2_1_16_1","unstructured":"Bernadette Charron-Bost Matthias F\u00fcgger and Thomas Nowak. 2015. Amortized averaging algorithms for approximate consensus. arXiv:cs.DC\/1512.04222. Retrieved from http:\/\/arxiv.org\/abs\/1512.04222.  Bernadette Charron-Bost Matthias F\u00fcgger and Thomas Nowak. 2015. Amortized averaging algorithms for approximate consensus. arXiv:cs.DC\/1512.04222. Retrieved from http:\/\/arxiv.org\/abs\/1512.04222."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_42"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP\u201916)","author":"Charron-Bost Bernadette","year":"2016"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0084-6"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/100791671"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446475"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.01.024"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(89)90021-X"},{"key":"e_1_2_1_24_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 27th International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201920), Andrea Richa and Christian Scheideler (Eds.)","author":"Delporte-Gallet Carole"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/5925.5931"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.976029"},{"key":"e_1_2_1_27_1","first-page":"443","article-title":"Convergence time for unbiased quantized consensus","volume":"61","author":"Etesami Seyed Rasoul","year":"2016","journal-title":"IEEE Trans. Automat. Contr."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01783662"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1094"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01843568"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing (DISC\u201918)","author":"F\u00fcgger Matthias","year":"2018"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212762"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/277697.277724"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611477"},{"key":"e_1_2_1_36_1","first-page":"1","article-title":"Opinion dynamics and bounded confidence models, analysis, and simulation","volume":"5","author":"Hegselmann Rainer","year":"2002","journal-title":"J. Artif. Societ. Soc. Simul."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Maurice Herlihy Dmitry Kozlov and Sergio Rajsbaum. 2014. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann Waltham.  Maurice Herlihy Dmitry Kozlov and Sergio Rajsbaum. 2014. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann Waltham.","DOI":"10.1016\/B978-0-12-404578-1.00003-6"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.04.007"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701397412"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146408"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1959045.1959064"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2006.25"},{"key":"e_1_2_1_43_1","volume-title":"Cooperative Control: A Post-Workshop Volume, 2003 Block Island Workshop on Cooperative Control, Vijay Kumar, Naomi Leonard, and A. Stephen Morse (Eds.). Springer","author":"Lin J.","year":"2005"},{"key":"e_1_2_1_44_1","volume-title":"Distributed Algorithms. Morgan Kaufmann","author":"Lynch Nancy A."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0240-5"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/0150098"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2004.841888"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364006"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2009.2031203"},{"key":"e_1_2_1_50_1","unstructured":"Thomas Nowak. 2010. Topology in Distributed Computing. Master Thesis. TU Wien.  Thomas Nowak. 2010. Topology in Distributed Computing. Master Thesis. TU Wien."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331624"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ifacol.2015.10.313"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/110837462"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0028994"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/DSN.2001.941391"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.75.1226"},{"key":"e_1_2_1_57_1","volume-title":"An overview of recent results for consensus in directed dynamic networks. Bull. EACTS 128","author":"Winkler Kyrill","year":"2019"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2013.02.015"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485242","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485242","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:35Z","timestamp":1750191515000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485242"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,28]]},"references-count":58,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3485242"],"URL":"https:\/\/doi.org\/10.1145\/3485242","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,28]]},"assertion":[{"value":"2019-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}