{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:08Z","timestamp":1740109328259,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T00:00:00Z","timestamp":1707782400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T00:00:00Z","timestamp":1707782400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006764","name":"Technische Universit\u00e4t Berlin","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006764","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the problem of solving consensus in synchronous directed dynamic networks, in which communication is controlled by an oblivious message adversary that picks the communication graph to be used in a round from a fixed set of graphs <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textbf{D}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>D<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> arbitrarily. In this fundamental model, determining consensus solvability and designing efficient consensus algorithms is surprisingly difficult. Enabled by a decision procedure that is derived from a well-established previous consensus solvability characterization for a given set <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\textbf{D}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>D<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, we study, for the first time, the time complexity of solving consensus in this model: We provide both upper and lower bounds for this time complexity, and also relate it to the number of iterations required by the decision procedure. Among other results, we find that reaching consensus under an oblivious message adversary can take exponentially longer than both deciding consensus solvability and broadcasting the input value of some unknown process to all other processes.\n<\/jats:p>","DOI":"10.1007\/s00453-024-01209-4","type":"journal-article","created":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T10:02:20Z","timestamp":1707818540000},"page":"1830-1861","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Time Complexity of Consensus Under Oblivious Message Adversaries"],"prefix":"10.1007","volume":"86","author":[{"given":"Kyrill","family":"Winkler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ami","family":"Paz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hugo Rincon","family":"Galeana","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stefan","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulrich","family":"Schmid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,2,13]]},"reference":[{"issue":"9","key":"1209_CR1","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1177\/0037549707085632","volume":"83","author":"C Newport","year":"2007","unstructured":"Newport, C., Kotz, D., Yuan, Y., Gray, R.S., Liu, J., Elliott, C.: Experimental evaluation of wireless simulation assumptions. SIMULATION: Trans. Soc. Model. Simul. Int. 83(9), 643\u2013661 (2007). https:\/\/doi.org\/10.1177\/0037549707085632","journal-title":"SIMULATION: Trans. Soc. Model. Simul. Int."},{"key":"1209_CR2","doi-asserted-by":"publisher","unstructured":"Schwarz, M., Winkler, K., Schmid, U.: Fast consensus under eventually stabilizing message adversaries. In: Proceedings of the 17th International Conference on Distributed Computing and Networking. ICDCN \u201916, pp. 7\u20131710. ACM, New York, NY, USA (2016) . https:\/\/doi.org\/10.1145\/2833312.2833323","DOI":"10.1145\/2833312.2833323"},{"issue":"5","key":"1209_CR3","doi-asserted-by":"publisher","first-page":"1912","DOI":"10.1137\/S009753970443999X","volume":"38","author":"U Schmid","year":"2009","unstructured":"Schmid, U., Weiss, B., Keidar, I.: Impossibility results and lower bounds for consensus under link failures. SIAM J. Comput. 38(5), 1912\u20131951 (2009). https:\/\/doi.org\/10.1137\/S009753970443999X","journal-title":"SIAM J. Comput."},{"key":"1209_CR4","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Oshman, R., Moses, Y.: Coordinated consensus in dynamic networks. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. PODC \u201911. ACM (2011)","DOI":"10.1145\/1993806.1993808"},{"key":"1209_CR5","doi-asserted-by":"publisher","unstructured":"Afek, Y., Gafni, E.: Asynchrony from synchrony. In: Distributed Computing and Networking. Lecture Notes in Computer Science, vol. 7730, pp. 225\u2013239. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-35668-1_16","DOI":"10.1007\/978-3-642-35668-1_16"},{"key":"1209_CR6","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/j.tcs.2015.01.024","volume":"584","author":"\u00c9 Coulouma","year":"2015","unstructured":"Coulouma, \u00c9., Godard, E., Peters, J.G.: A characterization of oblivious message adversaries for which consensus is solvable. Theor. Comput. Sci. 584, 80\u201390 (2015). https:\/\/doi.org\/10.1016\/j.tcs.2015.01.024","journal-title":"Theor. Comput. Sci."},{"key":"1209_CR7","doi-asserted-by":"crossref","unstructured":"Santoro, N., Widmayer, P.: Time is not a healer. In: Proceeding of 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS\u201989). LNCS 349, pp. 304\u2013313. Springer, Paderborn (1989)","DOI":"10.1007\/BFb0028994"},{"key":"1209_CR8","doi-asserted-by":"crossref","unstructured":"El-Hayek, A., Henzinger, M., Schmid, S.: Brief announcement: broadcasting time in dynamic rooted trees is linear. In: PODC, pp. 54\u201356. ACM (2022)","DOI":"10.1145\/3519270.3538460"},{"key":"1209_CR9","unstructured":"El-Hayek, A., Henzinger, M., Schmid, S.: Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks. In: 14th Innovations in Theoretical Computer Science (ITCS) (2023)"},{"key":"1209_CR10","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/j.dam.2018.08.015","volume":"255","author":"M Zeiner","year":"2019","unstructured":"Zeiner, M., Schwarz, M., Schmid, U.: On linear-time data dissemination in dynamic rooted trees. Discrete Appl. Math. 255, 307\u2013319 (2019). https:\/\/doi.org\/10.1016\/j.dam.2018.08.015","journal-title":"Discrete Appl. Math."},{"key":"1209_CR11","doi-asserted-by":"publisher","first-page":"257","DOI":"10.1016\/j.dam.2020.02.013","volume":"282","author":"M F\u00fcgger","year":"2020","unstructured":"F\u00fcgger, M., Nowak, T., Winkler, K.: On the radius of nonsplit graphs and information dissemination in dynamic networks. Discrete Appl. Math. 282, 257\u2013264 (2020). https:\/\/doi.org\/10.1016\/j.dam.2020.02.013","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"1209_CR12","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"MJ Fischer","year":"1985","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374\u2013382 (1985)","journal-title":"J. ACM"},{"issue":"3","key":"1209_CR13","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1016\/0196-6774(90)90020-F","volume":"11","author":"O Biran","year":"1990","unstructured":"Biran, O., Moran, S., Zaks, S.: A combinatorial characterization of the distributed 1-solvable tasks. J. Algorithms 11(3), 420\u2013440 (1990)","journal-title":"J. Algorithms"},{"key":"1209_CR14","unstructured":"Ongaro, D., Ousterhout, J.: In search of an understandable consensus algorithm. In: Proc. USENIX Annual Technical Conference (ATC), pp. 305\u2013319 (2014)"},{"issue":"1","key":"1209_CR15","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1145\/1959045.1959064","volume":"42","author":"F Kuhn","year":"2011","unstructured":"Kuhn, F., Oshman, R.: Dynamic networks: models and algorithms. SIGACT News 42(1), 82\u201396 (2011)","journal-title":"SIGACT News"},{"key":"1209_CR16","doi-asserted-by":"publisher","unstructured":"Casta\u00f1eda, A., Fraigniaud, P., Paz, A., Rajsbaum, S., Roy, M., Travers, C.: A topological perspective on distributed network algorithms. In: Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO, pp. 3\u201318 (2019). https:\/\/doi.org\/10.1007\/978-3-030-24922-9_1","DOI":"10.1007\/978-3-030-24922-9_1"},{"key":"1209_CR17","unstructured":"Winkler, K., Schmid, U.: An overview of recent results for consensus in directed dynamic networks. Bull. EATCS 128 (2019)"},{"key":"1209_CR18","unstructured":"Abraham, I., Malkhi, D., et al.: The blockchain consensus layer and BFT. Bull. EATCS 3(123) (2017)"},{"issue":"2\u20133","key":"1209_CR19","doi-asserted-by":"publisher","first-page":"232","DOI":"10.1016\/j.tcs.2007.04.036","volume":"384","author":"N Santoro","year":"2007","unstructured":"Santoro, N., Widmayer, P.: Agreement in synchronous networks with ubiquitous faults. Theor. Comput. Sci. 384(2\u20133), 232\u2013249 (2007)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1209_CR20","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s00446-009-0084-6","volume":"22","author":"B Charron-Bost","year":"2009","unstructured":"Charron-Bost, B., Schiper, A.: The Heard-Of model: computing in distributed systems with benign faults. Distrib. Comput. 22(1), 49\u201371 (2009). https:\/\/doi.org\/10.1007\/s00446-009-0084-6","journal-title":"Distrib. Comput."},{"issue":"40","key":"1209_CR21","doi-asserted-by":"publisher","first-page":"5602","DOI":"10.1016\/j.tcs.2010.09.032","volume":"412","author":"M Biely","year":"2011","unstructured":"Biely, M., Schmid, U., Weiss, B.: Synchronous consensus under hybrid process and link failures. Theor. Comput. Sci. 412(40), 5602\u20135630 (2011). https:\/\/doi.org\/10.1016\/j.tcs.2010.09.032","journal-title":"Theor. Comput. Sci."},{"key":"1209_CR22","doi-asserted-by":"publisher","unstructured":"Charron-Bost, B., F\u00fcgger, M., Nowak, T.: Approximate consensus in highly dynamic networks: The role of averaging algorithms. In: Halld\u00f2rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) Automata, Languages, and Programming. Lecture Notes in Computer Science, vol. 9135, pp. 528\u2013539. Springer, ??? (2015). https:\/\/doi.org\/10.1007\/978-3-662-47666-6_42","DOI":"10.1007\/978-3-662-47666-6_42"},{"key":"1209_CR23","doi-asserted-by":"publisher","unstructured":"F\u00fcgger, M., Nowak, T., Schwarz, M.: Tight bounds for asymptotic and approximate consensus. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. PODC \u201918, pp. 325\u2013334. ACM, New York, NY, USA (2018). https:\/\/doi.org\/10.1145\/3212734.3212762","DOI":"10.1145\/3212734.3212762"},{"key":"1209_CR24","doi-asserted-by":"publisher","unstructured":"Gafni, E.: Round-by-round fault detectors (extended abstract): unifying synchrony and asynchrony. In: Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, pp. 143\u2013152. ACM Press, Puerto Vallarta, Mexico (1998). https:\/\/doi.org\/10.1145\/277697.277724","DOI":"10.1145\/277697.277724"},{"key":"1209_CR25","doi-asserted-by":"crossref","unstructured":"Keidar, I., Shraer, A.: Timeliness, failure detectors, and consensus performance. In: Proceedings of the Twenty-fifth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC\u201906), pp. 169\u2013178. ACM Press, New York (2006)","DOI":"10.1145\/1146381.1146408"},{"key":"1209_CR26","doi-asserted-by":"publisher","unstructured":"Fevat, T., Godard, E.: Minimal obstructions for the coordinated attack problem and beyond. In: 25th IEEE International Symposium on Parallel and Distributed Processing, IPDPS 2011, Anchorage, Alaska, USA, 16\u201320 May, 2011 - Conference Proceedings, pp. 1001\u20131011 (2011). https:\/\/doi.org\/10.1109\/IPDPS.2011.96","DOI":"10.1109\/IPDPS.2011.96"},{"key":"1209_CR27","doi-asserted-by":"publisher","unstructured":"Biely, M., Robinson, P., Schmid, U.: Agreement in directed dynamic networks. In: Proceedings 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201912). LNCS 7355, pp. 73\u201384. Springer (2012). https:\/\/doi.org\/10.1007\/978-3-642-31104-8_7","DOI":"10.1007\/978-3-642-31104-8_7"},{"key":"1209_CR28","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.tcs.2018.02.019","volume":"726","author":"M Biely","year":"2018","unstructured":"Biely, M., Robinson, P., Schmid, U., Schwarz, M., Winkler, K.: Gracefully degrading consensus and k-set agreement in directed dynamic networks. Theor. Comput. Sci. 726, 41\u201377 (2018). https:\/\/doi.org\/10.1016\/j.tcs.2018.02.019","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"1209_CR29","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s00446-019-00348-0","volume":"32","author":"K Winkler","year":"2019","unstructured":"Winkler, K., Schwarz, M., Schmid, U.: Consensus in directed dynamic networks with short-lived stability. Distrib. Comput. 32(5), 443\u2013458 (2019). https:\/\/doi.org\/10.1007\/s00446-019-00348-0","journal-title":"Distrib. Comput."},{"key":"1209_CR30","doi-asserted-by":"publisher","unstructured":"Nowak, T., Schmid, U., Winkler, K.: Topological characterization of consensus under general message adversaries. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29\u2013August 2, 2019, pp. 218\u2013227 (2019) (Full version: http:\/\/arxiv.org\/abs\/1905.09590). https:\/\/doi.org\/10.1145\/3293611.3331624","DOI":"10.1145\/3293611.3331624"},{"key":"1209_CR31","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Lynch, N.A., Oshman, R.: Distributed computation in dynamic networks. In: STOC, pp. 513\u2013522 (2010)","DOI":"10.1145\/1806689.1806760"},{"key":"1209_CR32","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Kozlov, D.N., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann (2013). https:\/\/store.elsevier.com\/product.jsp?isbn=9780124045781","DOI":"10.1016\/B978-0-12-404578-1.00003-6"},{"key":"1209_CR33","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.tcs.2012.09.012","volume":"512","author":"H Attiya","year":"2013","unstructured":"Attiya, H., Casta\u00f1eda, A.: A non-topological proof for the impossibility of k-set agreement. Theor. Comput. Sci. 512, 41\u201348 (2013)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"1209_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/16M1081439","volume":"48","author":"H Attiya","year":"2019","unstructured":"Attiya, H., Casta\u00f1eda, A., Herlihy, M., Paz, A.: Bounds on the step and namespace complexity of renaming. SIAM J. Comput. 48(1), 1\u201332 (2019). https:\/\/doi.org\/10.1137\/16M1081439","journal-title":"SIAM J. Comput."},{"key":"1209_CR35","unstructured":"Kozlov, D.N.: Structure theory of flip graphs with applications to weak symmetry breaking. CoRR http:\/\/arxiv.org\/1511.00457 (2015)"},{"key":"1209_CR36","doi-asserted-by":"publisher","unstructured":"Kozlov, D.N.: Combinatorial Topology of the Standard Chromatic Subdivision and Weak Symmetry Breaking for Six Processes, pp. 155\u2013194. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-31580-5_7","DOI":"10.1007\/978-3-319-31580-5_7"},{"key":"1209_CR37","doi-asserted-by":"publisher","unstructured":"Winkler, K., Schmid, U., Moses, Y.: A characterization of consensus solvability for closed message adversaries. In: 23rd International Conference on Principles of Distributed Systems, OPODIS 2019, December 17\u201319, 2019, Neuch\u00e2tel, Switzerland. LIPIcs, vol. 153, pp. 17\u201311716. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, ??? (2019). https:\/\/doi.org\/10.4230\/LIPIcs.OPODIS.2019.17","DOI":"10.4230\/LIPIcs.OPODIS.2019.17"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01209-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01209-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01209-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,22]],"date-time":"2024-05-22T07:03:20Z","timestamp":1716361400000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01209-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,13]]},"references-count":37,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2024,6]]}},"alternative-id":["1209"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01209-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,2,13]]},"assertion":[{"value":"11 August 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter or materials discussed in this manuscript. The authors have no financial or proprietary interests in any material discussed in this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}