{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:11Z","timestamp":1750220351817,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467949","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"259-262","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Brief Announcement"],"prefix":"10.1145","author":[{"given":"Manish","family":"Kumar","sequence":"first","affiliation":[{"name":"Indian Statistical Institute, Kolkata, Kolkata, India"}]},{"given":"Anisur Rahaman","family":"Molla","sequence":"additional","affiliation":[{"name":"Indian Statistical Institute, Kolkata, Kolkata, India"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0220023"},{"key":"e_1_3_2_2_2_1","unstructured":"D. P. Anderson and J. Kubiatowicz. 2002. Introduction to Distributed Algorithms. (2002).  D. P. Anderson and J. Kubiatowicz. 2002. Introduction to Distributed Algorithms. (2002)."},{"key":"e_1_3_2_2_3_1","volume-title":"Welch","author":"Attiya Hagit","year":"2004","unstructured":"Hagit Attiya and Jennifer L . Welch . 2004 . Distributed computing - fundamentals, simulations, and advanced topics (2. ed.). Wiley . Hagit Attiya and Jennifer L. Welch. 2004. Distributed computing - fundamentals, simulations, and advanced topics (2. ed.). Wiley."},{"key":"e_1_3_2_2_4_1","volume-title":"Anisur Rahaman Molla, and Gopal Pandurangan","author":"Augustine John","year":"2018","unstructured":"John Augustine , Anisur Rahaman Molla, and Gopal Pandurangan . 2018 . Sublinear Message Bounds for Randomized Agreement. In PODC. ACM , 315--324. John Augustine, Anisur Rahaman Molla, and Gopal Pandurangan. 2018. Sublinear Message Bounds for Randomized Agreement. In PODC. ACM, 315--324."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281103"},{"key":"e_1_3_2_2_6_1","volume-title":"Kowalski","author":"Chlebus Bogdan S.","year":"2002","unstructured":"Bogdan S. Chlebus and Dariusz R . Kowalski . 2002 . Gossiping to reach consensus. In SPAA. 220--229. Bogdan S. Chlebus and Dariusz R. Kowalski. 2002. Gossiping to reach consensus. In SPAA. 220--229."},{"key":"e_1_3_2_2_7_1","volume-title":"Kowalski","author":"Chlebus Bogdan S.","year":"2006","unstructured":"Bogdan S. Chlebus and Dariusz R . Kowalski . 2006 . Robust gossiping with an application to consensus. J. Comput. Syst. Sci . (2006), 1262--1281. Bogdan S. Chlebus and Dariusz R. Kowalski. 2006. Robust gossiping with an application to consensus. J. Comput. Syst. Sci. (2006), 1262--1281."},{"key":"e_1_3_2_2_8_1","volume-title":"SPAA","author":"Bogdan","year":"2009","unstructured":"Bogdan S. Chlebus and Dariusz R. Kowalski. 2009. Locally scalable randomized consensus for synchronous crash failures . In SPAA 2009 . ACM, 290--299. Bogdan S. Chlebus and Dariusz R. Kowalski. 2009. Locally scalable randomized consensus for synchronous crash failures. In SPAA 2009. ACM, 290--299."},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"crossref","unstructured":"Bogdan S. Chlebus Dariusz R. Kowalski and Michal Strojnowski. 2009. Fast scalable deterministic consensus for crash failures. In PODC. ACM 111--120.  Bogdan S. Chlebus Dariusz R. Kowalski and Michal Strojnowski. 2009. Fast scalable deterministic consensus for crash failures. In PODC. ACM 111--120.","DOI":"10.1145\/1582716.1582738"},{"key":"e_1_3_2_2_10_1","volume-title":"Shmoys","author":"Chor Benny","year":"1989","unstructured":"Benny Chor , Michael Merritt , and David B . Shmoys . 1989 . Simple constant-time consensus protocols in realistic failure models. J. ACM ( 1989), 591--614. Benny Chor, Michael Merritt, and David B. Shmoys. 1989. Simple constant-time consensus protocols in realistic failure models. J. ACM (1989), 591--614."},{"key":"e_1_3_2_2_11_1","volume-title":"Kowalski","author":"Gilbert Seth","year":"2010","unstructured":"Seth Gilbert and Dariusz R . Kowalski . 2010 . Distributed Agreement with Optimal Communication Complexity. In SODA. 965--977. Seth Gilbert and Dariusz R. Kowalski. 2010. Distributed Agreement with Optimal Communication Complexity. In SODA. 965--977."},{"key":"e_1_3_2_2_12_1","volume-title":"SIROCCO","volume":"12156","author":"Gupta Diksha","year":"2020","unstructured":"Diksha Gupta , Jared Saia , and Maxwell Young . 2020 . Resource Burning for Permissionless Systems . In SIROCCO , Vol. 12156 . Springer, 19--44. Diksha Gupta, Jared Saia, and Maxwell Young. 2020. Resource Burning for Permissionless Systems. In SIROCCO, Vol. 12156. Springer, 19--44."},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"crossref","unstructured":"P. Humblet. 1984. Electing a leader in a clique in O(n log n) messages. (1984).  P. Humblet. 1984. Electing a leader in a clique in O(n log n) messages. (1984).","DOI":"10.21236\/ADA146581"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/77606.77610"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216019"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(89)90103-5"},{"key":"e_1_3_2_2_17_1","unstructured":"Manish Kumar and Anisur Rahaman Molla. 2021. On the Message Complexity of Fault-Tolerant Computation: Leader Election and Agreement. https:\/\/drive.google.com\/file\/d\/1OVEF-OWxUp0Z_PoW7zcmxEIWLp599RVj\/view?usp=sharing. It will also be available in the arXiv (CoRR arXiv.org > cs > cs.DC).  Manish Kumar and Anisur Rahaman Molla. 2021. On the Message Complexity of Fault-Tolerant Computation: Leader Election and Agreement. https:\/\/drive.google.com\/file\/d\/1OVEF-OWxUp0Z_PoW7zcmxEIWLp599RVj\/view?usp=sharing. It will also be available in the arXiv (CoRR arXiv.org > cs > cs.DC)."},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699440"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.02.009"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15763-9_45"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_3_2_2_22_1","volume-title":"Proceedings of the 7th IFIP Congress","author":"Le Lann G\u00e9","year":"1977","unstructured":"G\u00e9 rard Le Lann . 1977 . Distributed Systems - Towards a Formal Approach. In Information Processing , Proceedings of the 7th IFIP Congress 1977. North-Holland, 155--160. G\u00e9 rard Le Lann. 1977. Distributed Systems - Towards a Formal Approach. In Information Processing, Proceedings of the 7th IFIP Congress 1977. North-Holland, 155--160."},{"key":"e_1_3_2_2_23_1","unstructured":"Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann.  Nancy A. Lynch. 1996. Distributed Algorithms. Morgan Kaufmann."},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Michael Mitzenmacher and Eli Upfal. 2004. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. (2004).  Michael Mitzenmacher and Eli Upfal. 2004. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. (2004).","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1842733.1842736"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_2_28_1","volume-title":"Leader Election in the Internet of Things: Challenges and Opportunities. CoRR","author":"Rahman Mohsin Ur","year":"2019","unstructured":"Mohsin Ur Rahman . 2019. Leader Election in the Internet of Things: Challenges and Opportunities. CoRR , Vol. abs\/ 1911 .00759 ( 2019 ). arxiv: 1911.00759 http:\/\/arxiv.org\/abs\/1911.00759 Mohsin Ur Rahman. 2019. Leader Election in the Internet of Things: Challenges and Opportunities. CoRR, Vol. abs\/1911.00759 (2019). arxiv: 1911.00759 http:\/\/arxiv.org\/abs\/1911.00759"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"crossref","unstructured":"Sylvia Ratnasamy Paul Francis Mark Handley Richard M. Karp and Scott Shenker. 2001. A scalable content-addressable network. In SIGCOMM. ACM 161--172.  Sylvia Ratnasamy Paul Francis Mark Handley Richard M. Karp and Scott Shenker. 2001. A scalable content-addressable network. In SIGCOMM. ACM 161--172.","DOI":"10.1145\/964723.383072"},{"key":"e_1_3_2_2_30_1","volume-title":"Pond: The OceanStore Prototype. In FAST. USENIX.","author":"Rhea Sean C.","year":"2003","unstructured":"Sean C. Rhea , Patrick R. Eaton , Dennis Geels , Hakim Weatherspoon , Ben Y. Zhao , and John Kubiatowicz . 2003 . Pond: The OceanStore Prototype. In FAST. USENIX. Sean C. Rhea, Patrick R. Eaton, Dennis Geels, Hakim Weatherspoon, Ben Y. Zhao, and John Kubiatowicz. 2003. Pond: The OceanStore Prototype. In FAST. USENIX."},{"key":"e_1_3_2_2_31_1","volume-title":"Rowstron and Peter Druschel","author":"Antony I.","year":"2001","unstructured":"Antony I. T. Rowstron and Peter Druschel . 2001 . Pastry : Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems. In IFIP\/ACM International Conference on Distributed Systems Platforms (Lecture Notes in Computer Science), Vol. 2218 . Springer , 329--350. Antony I. T. Rowstron and Peter Druschel. 2001. Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems. In IFIP\/ACM International Conference on Distributed Systems Platforms (Lecture Notes in Computer Science), Vol. 2218. Springer, 329--350."},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/MWC.2004.1368895"},{"volume-title":"Efficient distributed algorithms for leader election in complete networks","author":"Singh Gurdip","key":"e_1_3_2_2_33_1","unstructured":"Gurdip Singh . 1991. Efficient distributed algorithms for leader election in complete networks . In ICDCS. IEEE Computer Society , 472--479. Gurdip Singh. 1991. Efficient distributed algorithms for leader election in complete networks. In ICDCS. IEEE Computer Society, 472--479."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1538788.1538794"}],"event":{"name":"PODC '21: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Event Italy","acronym":"PODC '21"},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467949","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467949","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:11Z","timestamp":1750191431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467949"}},"subtitle":["On the Message Complexity of Fault-Tolerant Computation: Leader Election and Agreement"],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":34,"alternative-id":["10.1145\/3465084.3467949","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467949","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}