{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T17:25:49Z","timestamp":1792171549489,"version":"4.4.0"},"publisher-location":"Berlin, Heidelberg","reference-count":30,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662451731","type":"print"},{"value":"9783662451748","type":"electronic"}],"license":[{"start":{"date-parts":[[2014,1,1]],"date-time":"2014-01-01T00:00:00Z","timestamp":1388534400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-45174-8_5","type":"book-chapter","created":{"date-parts":[[2014,9,29]],"date-time":"2014-09-29T15:28:20Z","timestamp":1412004500000},"page":"61-75","source":"Crossref","is-referenced-by-count":5,"title":["Communication-Efficient Randomized Consensus"],"prefix":"10.1007","author":[{"given":"Dan","family":"Alistarh","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"James","family":"Aspnes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Valerie","family":"King","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jared","family":"Saia","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"5_CR1","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1145\/62546.62594","volume-title":"Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 1988","author":"K. Abrahamson","year":"1988","unstructured":"Abrahamson, K.: On achieving consensus using a shared memory. In: Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC 1988, pp. 291\u2013302. ACM, New York (1988)"},{"issue":"5","key":"5_CR2","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s00446-012-0162-z","volume":"25","author":"M.K. Aguilera","year":"2012","unstructured":"Aguilera, M.K., Toueg, S.: The correctness proof of Ben-Or\u2019s randomized consensus algorithm. Distributed Computing\u00a025(5), 371\u2013381 (2012)","journal-title":"Distributed Computing"},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Alistarh, D., Aspnes, J., King, V., Saia, J.: Communication-efficient randomized consensus (2014), Full version available at http:\/\/www.cs.yale.edu\/homes\/aspnes\/papers\/disc2014-submission.pdf","DOI":"10.1007\/978-3-662-45174-8_5"},{"issue":"3","key":"5_CR4","doi-asserted-by":"publisher","first-page":"415","DOI":"10.1145\/278298.278304","volume":"45","author":"J. Aspnes","year":"1998","unstructured":"Aspnes, J.: Lower bounds for distributed coin-flipping and randomized consensus. J. ACM\u00a045(3), 415\u2013450 (1998)","journal-title":"J. ACM"},{"key":"5_CR5","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Attiya, H., Censor, K.: Randomized consensus in expected O(n logn) individual work. In: PODC 2008: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, pp. 325\u2013334 (August 2008)","DOI":"10.1145\/1400751.1400794"},{"issue":"1","key":"5_CR6","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/2108242.2108244","volume":"59","author":"J. Aspnes","year":"2012","unstructured":"Aspnes, J., Attiya, H., Censor-Hillel, K.: Polylogarithmic concurrent data structures from monotone circuits. J. ACM\u00a059(1), 2 (2012)","journal-title":"J. ACM"},{"issue":"2","key":"5_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1721837.1721841","volume":"6","author":"J. Aspnes","year":"2010","unstructured":"Aspnes, J., Censor, K.: Approximate shared-memory counting despite a strong adversary. ACM Transactions on Algorithms\u00a06(2), 1\u201323 (2010)","journal-title":"ACM Transactions on Algorithms"},{"key":"5_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/978-3-642-41527-2_18","volume-title":"Distributed Computing","author":"J. Aspnes","year":"2013","unstructured":"Aspnes, J., Censor-Hillel, K.: Atomic snapshots in O(log3 n) steps using randomized helping. In: Afek, Y. (ed.) DISC 2013. LNCS, vol.\u00a08205, pp. 254\u2013268. Springer, Heidelberg (2013)"},{"issue":"3","key":"5_CR9","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1016\/0196-6774(90)90021-6","volume":"11","author":"J. Aspnes","year":"1990","unstructured":"Aspnes, J., Herlihy, M.: Fast randomized consensus using shared memory. Journal of Algorithms\u00a011(3), 441\u2013461 (1990)","journal-title":"Journal of Algorithms"},{"issue":"5","key":"5_CR10","doi-asserted-by":"publisher","first-page":"1024","DOI":"10.1137\/S0097539792240881","volume":"25","author":"J. Aspnes","year":"1996","unstructured":"Aspnes, J., Waarts, O.: Randomized consensus in expected O(n log2 n) operations per processor. SIAM J. Comput.\u00a025(5), 1024\u20131044 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"5_CR11","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/200836.200869","volume":"42","author":"H. Attiya","year":"1995","unstructured":"Attiya, H., Bar-Noy, A., Dolev, D.: Sharing memory robustly in message-passing systems. J. ACM\u00a042(1), 124\u2013142 (1995)","journal-title":"J. ACM"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Attiya, H., Censor, K.: Tight bounds for asynchronous randomized consensus. J. ACM\u00a055(5), 20:1\u201320:26 (2008)","DOI":"10.1145\/1411509.1411510"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/800221.806707","volume-title":"Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC 1983","author":"M. Ben-Or","year":"1983","unstructured":"Ben-Or, M.: Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols. In: Proceedings of the Second Annual ACM Symposium on Principles of Distributed Computing, PODC 1983, pp. 27\u201330. ACM, New York (1983)"},{"key":"5_CR14","doi-asserted-by":"crossref","first-page":"154","DOI":"10.1145\/800222.806743","volume-title":"PODC 1984: Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing","author":"G. Bracha","year":"1984","unstructured":"Bracha, G.: An asynchronous [(n - 1)\/3]-resilient consensus protocol. In: PODC 1984: Proceedings of the Third Annual ACM Symposium on Principles of Distributed Computing, pp. 154\u2013162. ACM, New York (1984)"},{"key":"5_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/BFb0022443","volume-title":"Distributed Algorithms","author":"G. Bracha","year":"1992","unstructured":"Bracha, G., Rachman, O.: Randomized consensus in expected O(n2log n) operations. In: Toueg, S., Spirakis, P.G., Kirousis, L.M. (eds.) WDAG 1991. LNCS, vol.\u00a0579, pp. 143\u2013150. Springer, Heidelberg (1992)"},{"key":"5_CR16","doi-asserted-by":"crossref","unstructured":"Chandra, T.D.: Polylog randomized wait-free consensus. In: Proceedings of the Fifteenth Annual ACM Symposium on Principles of Distributed Computing, Philadelphia, Pennsylvania, USA, May 23-26, pp. 166-175 (1996)","DOI":"10.1145\/248052.248083"},{"issue":"2","key":"5_CR17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1145\/226643.226647","volume":"43","author":"T.D. Chandra","year":"1996","unstructured":"Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM\u00a043(2), 225\u2013267 (1996)","journal-title":"J. ACM"},{"key":"5_CR18","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1145\/41840.41848","volume-title":"Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 1987","author":"B. Chor","year":"1987","unstructured":"Chor, B., Israeli, A., Li, M.: On processor coordination using asynchronous hardware. In: Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing, PODC 1987, pp. 86\u201397. ACM, New York (1987)"},{"issue":"2","key":"5_CR19","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/42282.42283","volume":"35","author":"C. Dwork","year":"1988","unstructured":"Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM\u00a035(2), 288\u2013323 (1988)","journal-title":"J. ACM"},{"issue":"5","key":"5_CR20","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1145\/290179.290183","volume":"45","author":"F. Fich","year":"1998","unstructured":"Fich, F., Herlihy, M., Shavit, N.: On the space complexity of randomized synchronization. J. ACM\u00a045(5), 843\u2013862 (1998)","journal-title":"J. ACM"},{"issue":"2","key":"5_CR21","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1145\/3149.214121","volume":"32","author":"M.J. Fischer","year":"1985","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM\u00a032(2), 374\u2013382 (1985)","journal-title":"J. ACM"},{"key":"5_CR22","doi-asserted-by":"crossref","unstructured":"Grimmett, G.R., Stirzaker, D.R.: Probability and Random Processes. Oxford University Press (2001)","DOI":"10.1093\/oso\/9780198572237.001.0001"},{"key":"5_CR23","unstructured":"Hall, P., Heyde, C.: Martingale Limit Theory and Its Application. Academic Press (1980)"},{"key":"5_CR24","unstructured":"Karlin, A., Yao, A.: Probabilistic lower bounds for byzantine agreement and clock synchronization. Unpublished manuscript"},{"key":"5_CR25","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1145\/1142473.1142507","volume-title":"Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, SIGMOD 2006","author":"R. Keralapura","year":"2006","unstructured":"Keralapura, R., Cormode, G., Ramamirtham, J.: Communication-efficient distributed monitoring of thresholded counts. In: Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data, SIGMOD 2006, pp. 289\u2013300. ACM, New York (2006)"},{"key":"5_CR26","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J.: Byzantine agreement in polynomial expected time. In: Proceedings of the ACM Symposium on Theory of Computing, STOC (2013)","DOI":"10.1145\/2488608.2488658"},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J.: Faster agreement via a spectral method for detecting malicious behavior. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA) (2014)","DOI":"10.1137\/1.9781611973402.58"},{"issue":"3","key":"5_CR28","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L. Lamport","year":"1982","unstructured":"Lamport, L., Shostak, R., Pease, M.: The byzantine generals problem. ACM Trans. Program. Lang. Syst.\u00a04(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"2","key":"5_CR29","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"M. Pease","year":"1980","unstructured":"Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J. ACM\u00a027(2), 228\u2013234 (1980)","journal-title":"J. ACM"},{"key":"5_CR30","unstructured":"Saks, M., Shavit, N., Woll, H.: Optimal time randomized consensus - making resilient algorithms fast in practice. In: Proc. of the 2nd ACM Symposium on Discrete Algorithms (SODA), pp. 351\u2013362 (1991)"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-45174-8_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,4]],"date-time":"2025-05-04T22:11:28Z","timestamp":1746396688000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-45174-8_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662451731","9783662451748"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-45174-8_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}