{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:09:49Z","timestamp":1750219789112,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T00:00:00Z","timestamp":1686873600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["2131538"],"award-info":[{"award-number":["2131538"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,19]]},"DOI":"10.1145\/3583668.3594599","type":"proceedings-article","created":{"date-parts":[[2023,6,16]],"date-time":"2023-06-16T22:28:38Z","timestamp":1686954518000},"page":"344-354","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4884-941X","authenticated-orcid":false,"given":"Bogdan","family":"Chlebus","sequence":"first","affiliation":[{"name":"Augusta University, Augusta, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1316-7788","authenticated-orcid":false,"given":"Dariusz Rafal","family":"Kowalski","sequence":"additional","affiliation":[{"name":"Augusta University, Augusta, United States of America"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9278-3935","authenticated-orcid":false,"given":"Jan","family":"Olkowski","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,16]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331629"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-017-0315-1"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792240881"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/090751906"},{"volume-title":"Impossibility Results for Distributed Computing","author":"Attiya Hagit","key":"e_1_3_2_1_5_1","unstructured":"Hagit Attiya and Faith Ellen. 2014. Impossibility Results for Distributed Computing. Morgan & Claypool Publishers."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/983102"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/277697.277733"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90035-E"},{"key":"e_1_3_2_1_9_1","volume-title":"Proceedings of the 6th International Workshop on Distributed Algorithms (WDAG) (Lecture Notes in Computer Science","volume":"237","author":"Berman Piotr","unstructured":"Piotr Berman, Juan A. Garay, and Kenneth J. Perry. 1992. Optimal early stopping in distributed consensus (extended abstract). In Proceedings of the 6th International Workshop on Distributed Algorithms (WDAG) (Lecture Notes in Computer Science, Vol. 647). Springer, 221--237."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.02.003"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2006.08.001"},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 20th International Symposium on Distributed Computing (DISC) (Lecture Notes in Computer Science","volume":"328","author":"Bogdan","unstructured":"Bogdan S. Chlebus and Dariusz R. Kowalski. 2006. Time and communication efficient consensus for crash failures. In Proceedings of the 20th International Symposium on Distributed Computing (DISC) (Lecture Notes in Computer Science, Vol. 4167). Springer, 314--328."},{"volume-title":"Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 290--299","author":"Bogdan","key":"e_1_3_2_1_13_1","unstructured":"Bogdan S. Chlebus and Dariusz R. Kowalski. 2009. Locally scalable randomized consensus for synchronous crash failures. In Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 290--299."},{"key":"e_1_3_2_1_14_1","volume-title":"Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication. CoRR abs\/2305.11644","author":"Chlebus Bogdan S.","year":"2023","unstructured":"Bogdan S. Chlebus, Dariusz R. Kowalski, and Jan Olkowski. 2023. Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication. CoRR abs\/2305.11644 (2023)."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582738"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15763-9_24"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/65950.65956"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280838"},{"volume-title":"Elementary Number Theory","author":"Davidoff Giuliana","key":"e_1_3_2_1_19_1","unstructured":"Giuliana Davidoff, Peter Sarnak, and Alain Valette. 2003. Elementary Number Theory, Group Theory, and Ramanujan Graphs. Cambridge University Press."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/197917.198082"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484269"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2455.214112"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/96559.96565"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212045"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492674"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.05.019"},{"key":"e_1_3_2_1_27_1","volume-title":"Proceedings of the 21st International Symposium on Distributed Computing (DISC) (Lecture Notes in Computer Science","volume":"297","author":"Gilbert Seth","unstructured":"Seth Gilbert, Rachid Guerraoui, and Dariusz R. Kowalski. 2007. On the message complexity of indulgent consensus. In Proceedings of the 21st International Symposium on Distributed Computing (DISC) (Lecture Notes in Computer Science, Vol. 4731). Springer, 283--297."},{"key":"e_1_3_2_1_28_1","volume-title":"Kowalski","author":"Gilbert Seth","year":"2010","unstructured":"Seth Gilbert and Dariusz R. Kowalski. 2010. Distributed agreement with optimal communication complexity. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 965--977."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01187074"},{"key":"e_1_3_2_1_30_1","unstructured":"Maurice Herlihy and Nir Shavit. 2012. The Art of Multiprocessor Programming. Morgan Kaufmann."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989727.1989732"},{"key":"e_1_3_2_1_33_1","volume-title":"Kowalski and Jaroslaw Mirek","author":"Dariusz","year":"2019","unstructured":"Dariusz R. Kowalski and Jaroslaw Mirek. 2019. On the complexity of fault-tolerant consensus. In Revised Selected Papers from the 7th International Conference on Networked Systems (NETYS) (Lecture Notes in Computer Science, Vol. 11704). Springer, 19--31."},{"volume-title":"Expander Families and Cayley Graphs: a beginner's guide","author":"Krebs Mike","key":"e_1_3_2_1_34_1","unstructured":"Mike Krebs and Anthony Shaheen. 2011. Expander Families and Cayley Graphs: a beginner's guide. Oxford University Press."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"volume-title":"Distributed Algorithms","author":"Lynch Nancy A.","key":"e_1_3_2_1_36_1","unstructured":"Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann Publishers."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"volume-title":"Fault-tolerant Agreement in Synchronous Message-passing Systems","author":"Raynal Michel","key":"e_1_3_2_1_38_1","unstructured":"Michel Raynal. 2010. Fault-tolerant Agreement in Synchronous Message-passing Systems. Morgan & Claypool Publishers."},{"key":"e_1_3_2_1_39_1","volume-title":"Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 173--182","author":"Robinson Peter","year":"2018","unstructured":"Peter Robinson, Christian Scheideler, and Alexander Setzer. 2018. Breaking the [EQUATION] Barrier: Fast consensus under a late adversary. In Proceedings of the 30th Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 173--182."}],"event":{"name":"PODC '23: 2023 ACM Symposium on Principles of Distributed Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory","SIGOPS ACM Special Interest Group on Operating Systems"],"location":"Orlando FL USA","acronym":"PODC '23"},"container-title":["Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594599","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583668.3594599","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3583668.3594599","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:55Z","timestamp":1750178275000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3583668.3594599"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,16]]},"references-count":39,"alternative-id":["10.1145\/3583668.3594599","10.1145\/3583668"],"URL":"https:\/\/doi.org\/10.1145\/3583668.3594599","relation":{},"subject":[],"published":{"date-parts":[[2023,6,16]]},"assertion":[{"value":"2023-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}