{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T12:56:19Z","timestamp":1765976179245,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,10,14]],"date-time":"2017-10-14T00:00:00Z","timestamp":1507939200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2017,10,14]],"date-time":"2017-10-14T00:00:00Z","timestamp":1507939200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-0916389","CAREER Award 0644058"],"award-info":[{"award-number":["CCF-0916389","CAREER Award 0644058"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["Ambizione"],"award-info":[{"award-number":["Ambizione"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,11]]},"DOI":"10.1007\/s00446-017-0315-1","type":"journal-article","created":{"date-parts":[[2017,10,14]],"date-time":"2017-10-14T10:50:37Z","timestamp":1507978237000},"page":"489-501","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["Communication-efficient randomized consensus"],"prefix":"10.1007","volume":"31","author":[{"given":"Dan","family":"Alistarh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"James","family":"Aspnes","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Valerie","family":"King","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jared","family":"Saia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,14]]},"reference":[{"key":"315_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamson, K.: On achieving consensus using a shared memory. In: Proceedings of the Seventh Annual ACM Symposium on Principles of Distributed Computing, PODC \u201988, pp. 291\u2013302, New York, NY, USA. ACM (1988)","DOI":"10.1145\/62546.62594"},{"issue":"5","key":"315_CR2","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/s00446-012-0162-z","volume":"25","author":"MK Aguilera","year":"2012","unstructured":"Aguilera, M.K., Toueg, S.: The correctness proof of Ben-Or\u2019s randomized consensus algorithm. Distrib. Comput. 25(5), 371\u2013381 (2012)","journal-title":"Distrib. Comput."},{"issue":"3","key":"315_CR3","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 45(3), 415\u2013450 (1998)","journal-title":"J. ACM"},{"issue":"2\u20133","key":"315_CR4","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/s00446-002-0081-5","volume":"16","author":"J Aspnes","year":"2003","unstructured":"Aspnes, J.: Randomized protocols for asynchronous consensus. Distrib. Comput. 16(2\u20133), 165\u2013175 (2003)","journal-title":"Distrib. Comput."},{"key":"315_CR5","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Attiya, H., Censor, K.: Randomized consensus in expected $$O(n \\log n)$$ individual work. In: PODC \u201908: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing, pp. 325\u2013334 (2008)","DOI":"10.1145\/1400751.1400794"},{"issue":"1","key":"315_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 59(1), 2 (2012)","journal-title":"J. ACM"},{"issue":"2","key":"315_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 Trans. Algorithms 6(2), 1\u201323 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"315_CR8","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Censor-Hillel, K.: Atomic snapshots in $$O(\\log ^3 n)$$ steps using randomized helping. In: Proceedings of the 27th International Symposium on Distributed Computing (DISC 2013), pp. 254\u2013268 (2013)","DOI":"10.1007\/978-3-642-41527-2_18"},{"issue":"3","key":"315_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. J. Algorithms 11(3), 441\u2013461 (1990)","journal-title":"J. Algorithms"},{"issue":"5","key":"315_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 \\log ^2 n)$$ operations per processor. SIAM J. Comput. 25(5), 1024\u20131044 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"315_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 42(1), 124\u2013142 (1995)","journal-title":"J. ACM"},{"issue":"5","key":"315_CR12","doi-asserted-by":"publisher","first-page":"20:1","DOI":"10.1145\/1411509.1411510","volume":"55","author":"H Attiya","year":"2008","unstructured":"Attiya, H., Censor, K.: Tight bounds for asynchronous randomized consensus. J. ACM 55(5), 20:1\u201320:26 (2008)","journal-title":"J. ACM"},{"key":"315_CR13","doi-asserted-by":"crossref","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 \u201983, pp. 27\u201330, New York, NY, USA. ACM (1983)","DOI":"10.1145\/800221.806707"},{"key":"315_CR14","doi-asserted-by":"crossref","unstructured":"Bracha, G., Rachman, O.: Randomized consensus in expected O(n$$^2$$log n) operations. In: Toueg, S., Spirakis, P.G., Kirousis, L.M. (eds.) WDAG, volume 579 of Lecture Notes in Computer Science, pp. 143\u2013150. Springer (1991)","DOI":"10.1007\/BFb0022443"},{"key":"315_CR15","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, pp. 166\u2013175, Philadelphia, Pennsylvania, USA, 23\u201326 May 1996","DOI":"10.1145\/248052.248083"},{"issue":"2","key":"315_CR16","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1145\/226643.226647","volume":"43","author":"TD Chandra","year":"1996","unstructured":"Chandra, T.D., Toueg, S.: Unreliable failure detectors for reliable distributed systems. J. ACM 43(2), 225\u2013267 (1996)","journal-title":"J. ACM"},{"issue":"8","key":"315_CR17","doi-asserted-by":"publisher","first-page":"1262","DOI":"10.1016\/j.jcss.2006.08.001","volume":"72","author":"BS Chlebus","year":"2006","unstructured":"Chlebus, B.S., Kowalski, D.R.: Robust gossiping with an application to consensus. J. Comput. Syst. Sci. 72(8), 1262\u20131281 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"315_CR18","doi-asserted-by":"crossref","unstructured":"Chlebus, B.S., Kowalski, D.R.: Time and communication efficient consensus for crash failures. In: Dolev, S. (ed.) Distributed Computing, pp. 314\u2013328. Springer, Berlin (2006)","DOI":"10.1007\/11864219_22"},{"key":"315_CR19","doi-asserted-by":"crossref","unstructured":"Chlebus, B.S., Kowalski, D.R., Strojnowski, M.: Fast scalable deterministic consensus for crash failures. In: Proceedings of the 28th ACM symposium on Principles of distributed computing, pp. 111\u2013120. ACM (2009)","DOI":"10.1145\/1582716.1582738"},{"key":"315_CR20","doi-asserted-by":"crossref","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 \u201987, pp. 86\u201397, New York, NY, USA. ACM (1987)","DOI":"10.1145\/41840.41848"},{"issue":"2","key":"315_CR21","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 35(2), 288\u2013323 (1988)","journal-title":"J. ACM"},{"issue":"5","key":"315_CR22","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 45(5), 843\u2013862 (1998)","journal-title":"J. ACM"},{"issue":"2","key":"315_CR23","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"},{"key":"315_CR24","volume-title":"Martingale Limit Theory and Its Application","author":"P Hall","year":"1980","unstructured":"Hall, P., Heyde, C.C.: Martingale Limit Theory and Its Application. Academic Press, Cambridge (1980)"},{"issue":"3","key":"315_CR25","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. 4(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"2","key":"315_CR26","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 27(2), 228\u2013234 (1980)","journal-title":"J. ACM"},{"key":"315_CR27","unstructured":"Saks, M., Shavit, N., Woll, H.: Optimal time randomized consensus\u2014making resilient algorithms fast in practice. In: Proceedings of the 2nd ACM Symposium on Discrete Algorithms (SODA), pp. 351\u2013362 (1991)"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0315-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0315-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0315-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,16]],"date-time":"2020-05-16T14:59:50Z","timestamp":1589641190000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0315-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,14]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,11]]}},"alternative-id":["315"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0315-1","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2017,10,14]]},"assertion":[{"value":"20 April 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 September 2017","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 October 2017","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}