[{"status":"public","day":"01","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"OA_type":"gold","citation":{"chicago":"Cooper, Colin, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu, and Takeharu Shiraga. “Undecided State Dynamics with Many Opinions.” In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, 77–87. Association for Computing Machinery, 2026. <a href=\"https://doi.org/10.1145/3796701.3815920\">https://doi.org/10.1145/3796701.3815920</a>.","apa":"Cooper, C., Mallmann-Trenn, F., Radzik, T., Shimizu, N., &#38; Shiraga, T. (2026). Undecided state dynamics with many opinions. In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i> (pp. 77–87). Egham, United Kingdom: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3796701.3815920\">https://doi.org/10.1145/3796701.3815920</a>","mla":"Cooper, Colin, et al. “Undecided State Dynamics with Many Opinions.” <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2026, pp. 77–87, doi:<a href=\"https://doi.org/10.1145/3796701.3815920\">10.1145/3796701.3815920</a>.","short":"C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, T. Shiraga, in:, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 77–87.","ieee":"C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, and T. Shiraga, “Undecided state dynamics with many opinions,” in <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Egham, United Kingdom, 2026, pp. 77–87.","ista":"Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. 2026. Undecided state dynamics with many opinions. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 77–87.","ama":"Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. Undecided state dynamics with many opinions. In: <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2026:77-87. doi:<a href=\"https://doi.org/10.1145/3796701.3815920\">10.1145/3796701.3815920</a>"},"scopus_import":"1","_id":"22367","oa_version":"Published Version","acknowledgement":"Nobutaka Shimizu is supported by JSPS KAKENHI Grant Number\r\n23K16837. Takeharu Shiraga is supported by JSPS KAKENHI Grant\r\nNumber 23K16840, and JST CRONOS Grant Number JPMJCS24K2.\r\nColin Cooper is supported by a Mercator Fellowship from DFG\r\nProject 491453517 at the University of Hamburg. We thank the\r\nanonymous reviewers for their helpful comments and suggestions.","type":"conference","date_published":"2026-07-01T00:00:00Z","language":[{"iso":"eng"}],"month":"07","date_updated":"2026-07-21T07:54:01Z","publisher":"Association for Computing Machinery","department":[{"_id":"MoHe"}],"arxiv":1,"file_date_updated":"2026-07-21T07:51:58Z","oa":1,"publication_identifier":{"isbn":["9798400725128"]},"doi":"10.1145/3796701.3815920","das_tickbox":"1","publication":"Proceedings of the Annual ACM Symposium on Principles of Distributed Computing","date_created":"2026-07-19T22:01:47Z","year":"2026","researchdata_availability":"no","has_accepted_license":"1","conference":{"start_date":"2026-07-06","name":"PODC: Symposium on Principles of Distributed Computing","location":"Egham, United Kingdom","end_date":"2026-07-10"},"ddc":["000"],"supplementarymaterial":"no","corr_author":"1","quality_controlled":"1","file":[{"file_id":"22380","file_size":709077,"date_updated":"2026-07-21T07:51:58Z","relation":"main_file","checksum":"9ada61feba1e93fd72867a5ba4ee8bb8","access_level":"open_access","content_type":"application/pdf","file_name":"2026_ACMPODC_Cooper.pdf","date_created":"2026-07-21T07:51:58Z","creator":"dernst","success":1}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"full_name":"Cooper, Colin","first_name":"Colin","last_name":"Cooper"},{"first_name":"Frederik","last_name":"Mallmann-Trenn","id":"68748c44-84d5-11f1-b4f6-ca083374e553","full_name":"Mallmann-Trenn, Frederik"},{"full_name":"Radzik, Tomasz","last_name":"Radzik","first_name":"Tomasz"},{"full_name":"Shimizu, Nobutaka","first_name":"Nobutaka","last_name":"Shimizu"},{"full_name":"Shiraga, Takeharu","first_name":"Takeharu","last_name":"Shiraga"}],"OA_place":"publisher","keyword":["consensus dynamics","undecided state dynamics","gossip model","population protocol model"],"title":"Undecided state dynamics with many opinions","article_processing_charge":"No","page":"77-87","publication_status":"published","external_id":{"arxiv":["2603.02636"]},"abstract":[{"lang":"eng","text":"We study the Undecided-State Dynamics (USD), a fundamental consensus process in which each vertex holds one of k decided opinions or the undecided state. We consider both the gossip model and the population protocol model. Prior work established tight bounds on the consensus time of this process only for the regime \r\nk\r\n=\r\nO\r\n(\r\nn\r\n/\r\n(\r\nlog\r\n⁡\r\nn\r\n)\r\n2\r\n)\r\n (for the population protocol model) and k = O((n/log n)1/3) (for the gossip model), often under restrictive assumptions on the initial configuration.\r\nIn this paper, we obtain the first consensus-time guarantees for USD that hold for arbitrary 2 ≤ k ≤ n and for arbitrary initial configurations in both the gossip model and the population protocol model. In the gossip model, USD reaches consensus within \r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\n,\r\nn\r\n}\r\n)\r\n synchronous rounds with probability 1 - p⊥ - n-c, where p⊥ is the gossip-specific probability of collapsing to the all-undecided state in the first round. In the population protocol model, USD reaches consensus within \r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\nn\r\n,\r\nn\r\n3\r\n/\r\n2\r\n}\r\n)\r\n asynchronous interactions with high probability. We also present lower bounds that match the upper bounds up to polylogarithmic factors for a specific initial configuration and show that our upper bounds are essentially optimal."}]},{"ec_funded":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","short":"CC BY (4.0)"},"alternative_title":["LIPIcs"],"status":"public","day":"01","citation":{"mla":"Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.” <i>33rd International Symposium on Distributed Computing</i>, vol. 146, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17, doi:<a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">10.4230/LIPICS.DISC.2019.29</a>.","apa":"Nowak, T., &#38; Rybicki, J. (2019). Byzantine approximate agreement on graphs. In <i>33rd International Symposium on Distributed Computing</i> (Vol. 146, p. 29:1--29:17). Budapest, Hungary: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">https://doi.org/10.4230/LIPICS.DISC.2019.29</a>","chicago":"Nowak, Thomas, and Joel Rybicki. “Byzantine Approximate Agreement on Graphs.” In <i>33rd International Symposium on Distributed Computing</i>, 146:29:1--29:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. <a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">https://doi.org/10.4230/LIPICS.DISC.2019.29</a>.","ama":"Nowak T, Rybicki J. Byzantine approximate agreement on graphs. In: <i>33rd International Symposium on Distributed Computing</i>. Vol 146. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2019:29:1--29:17. doi:<a href=\"https://doi.org/10.4230/LIPICS.DISC.2019.29\">10.4230/LIPICS.DISC.2019.29</a>","ista":"Nowak T, Rybicki J. 2019. Byzantine approximate agreement on graphs. 33rd International Symposium on Distributed Computing. DISC: Symposium on Distributed Computing, LIPIcs, vol. 146, 29:1--29:17.","ieee":"T. Nowak and J. Rybicki, “Byzantine approximate agreement on graphs,” in <i>33rd International Symposium on Distributed Computing</i>, Budapest, Hungary, 2019, vol. 146, p. 29:1--29:17.","short":"T. Nowak, J. Rybicki, in:, 33rd International Symposium on Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, p. 29:1--29:17."},"project":[{"call_identifier":"H2020","name":"ISTplus - Postdoctoral Fellowships","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"oa_version":"Published Version","intvolume":"       146","type":"conference","_id":"6931","scopus_import":"1","oa":1,"file_date_updated":"2020-07-14T12:47:44Z","month":"11","language":[{"iso":"eng"}],"date_published":"2019-11-01T00:00:00Z","department":[{"_id":"DaAl"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","arxiv":1,"date_updated":"2025-07-10T11:54:03Z","year":"2019","date_created":"2019-10-08T12:41:38Z","publication_identifier":{"eisbn":["978-3-95977-126-9"]},"doi":"10.4230/LIPICS.DISC.2019.29","publication":"33rd International Symposium on Distributed Computing","file":[{"creator":"jrybicki","date_created":"2019-10-08T12:47:19Z","file_name":"LIPIcs-DISC-2019-29.pdf","content_type":"application/pdf","access_level":"open_access","checksum":"2d2202f90c6ac991e50876451627c4b5","relation":"main_file","date_updated":"2020-07-14T12:47:44Z","file_size":639378,"file_id":"6934"}],"quality_controlled":"1","has_accepted_license":"1","conference":{"start_date":"2019-10-14","name":"DISC: Symposium on Distributed Computing","end_date":"2019-10-18","location":"Budapest, Hungary"},"ddc":["004"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"last_name":"Nowak","first_name":"Thomas","full_name":"Nowak, Thomas"},{"full_name":"Rybicki, Joel","id":"334EFD2E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6432-6646","last_name":"Rybicki","first_name":"Joel"}],"volume":146,"page":"29:1--29:17","article_processing_charge":"No","abstract":[{"text":"Consider a distributed system with n processors out of which f can be Byzantine faulty. In the\r\napproximate agreement task, each processor i receives an input value xi and has to decide on an\r\noutput value yi such that\r\n1. the output values are in the convex hull of the non-faulty processors’ input values,\r\n2. the output values are within distance d of each other.\r\n\r\n\r\nClassically, the values are assumed to be from an m-dimensional Euclidean space, where m ≥ 1.\r\nIn this work, we study the task in a discrete setting, where input values with some structure\r\nexpressible as a graph. Namely, the input values are vertices of a finite graph G and the goal is to\r\noutput vertices that are within distance d of each other in G, but still remain in the graph-induced\r\nconvex hull of the input values. For d = 0, the task reduces to consensus and cannot be solved with\r\na deterministic algorithm in an asynchronous system even with a single crash fault. For any d ≥ 1,\r\nwe show that the task is solvable in asynchronous systems when G is chordal and n > (ω + 1)f,\r\nwhere ω is the clique number of G. In addition, we give the first Byzantine-tolerant algorithm for a\r\nvariant of lattice agreement. For synchronous systems, we show tight resilience bounds for the exact\r\nvariants of these and related tasks over a large class of combinatorial structures.","lang":"eng"}],"external_id":{"arxiv":["1908.02743"]},"publication_status":"published","title":"Byzantine approximate agreement on graphs","keyword":["consensus","approximate agreement","Byzantine faults","chordal graphs","lattice agreement"]}]