{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:27Z","timestamp":1740109287265,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T00:00:00Z","timestamp":1521763200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T00:00:00Z","timestamp":1521763200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"National Science Foundation","award":["CCF-1217921","CCF-1301926"],"award-info":[{"award-number":["CCF-1217921","CCF-1301926"]}]},{"name":"National Science Foundation","award":["IIS-1447786"],"award-info":[{"award-number":["IIS-1447786"]}]},{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"crossref","award":["ER26116\/DE-SC0008923"],"award-info":[{"award-number":["ER26116\/DE-SC0008923"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,8]]},"DOI":"10.1007\/s00446-018-0331-9","type":"journal-article","created":{"date-parts":[[2018,3,23]],"date-time":"2018-03-23T09:28:28Z","timestamp":1521797308000},"page":"317-326","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the optimal space complexity of consensus for anonymous processes"],"prefix":"10.1007","volume":"31","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6151-1061","authenticated-orcid":false,"given":"Rati","family":"Gelashvili","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,23]]},"reference":[{"key":"331_CR1","doi-asserted-by":"crossref","unstructured":"Abrahamson, K.: On achieving consensus using a shared memory. In: Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing, pp. 291\u2013302. ACM (1988)","DOI":"10.1145\/62546.62594"},{"issue":"3","key":"331_CR2","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"},{"key":"331_CR3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-02010-0","volume-title":"Impossibility Results for Distributed Computing","author":"H Attiya","year":"2014","unstructured":"Attiya, H., Ellen, F.: Impossibility Results for Distributed Computing, vol. 5. Morgan & Claypool Publishers, San Rafael (2014)"},{"key":"331_CR4","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Another advantage of free choice (extended abstract): completely asynchronous agreement protocols. In: Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing, pp. 27\u201330. ACM (1983)","DOI":"10.1145\/800221.806707"},{"key":"331_CR5","unstructured":"Bouzid, Z., Raynal, M., Sutra, P.: Brief announcement: Anonymous obstruction-free $$(n, k)$$-set agreement with $$n- k+ 1$$ atomic read\/write registers. In: Proceedings of the 29th International Symposium on Distributed Computing, p. 669. Springer (2015)"},{"key":"331_CR6","unstructured":"Bowman, J.: Obstruction-free snapshot, obstruction-free consensus, and fetch-and-add modulo k. Tech. Rep. TR2011-681, Dartmouth College, Computer Science, Hanover, NH (2011)"},{"key":"331_CR7","doi-asserted-by":"crossref","unstructured":"Ellen, F., Gelashvili, R., Zhu, L.: Revisionist simulations: a new approach to proving space lower bounds. ArXiv preprint arXiv:1711.02455 (2018)","DOI":"10.1145\/3212734.3212749"},{"issue":"5","key":"331_CR8","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 (JACM) 45(5), 843\u2013862 (1998)","journal-title":"J. ACM (JACM)"},{"issue":"2","key":"331_CR9","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 (JACM) 32(2), 374\u2013382 (1985)","journal-title":"J. ACM (JACM)"},{"key":"331_CR10","doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Helmi, M., Higham, L., Woelfel, P.: An $${\\cal O\\it }(\\sqrt{n})$$ space bound for obstruction-free leader election. In: Proceedings of the 27th International Symposium on Distributed Computing, pp. 46\u201360. Springer (2013)","DOI":"10.1007\/978-3-642-41527-2_4"},{"key":"331_CR11","doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Helmi, M., Higham, L., Woelfel, P.: Test-and-set in optimal space. In: Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, pp. 615\u2013623. ACM (2015)","DOI":"10.1145\/2746539.2746627"},{"key":"331_CR12","doi-asserted-by":"crossref","unstructured":"Guerraoui, R., Ruppert, E.: What can be implemented anonymously? In: Proceedings of the 19th International Symposium on Distributed Computing, pp. 244\u2013259. Springer (2005)","DOI":"10.1007\/11561927_19"},{"key":"331_CR13","unstructured":"Saks, M., Shavit, N., Woll, H.: Optimal time randomized consensus\u2014making resilient algorithms fast in practice. In: Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 351\u2013362. Society for Industrial and Applied Mathematics (1991)"},{"key":"331_CR14","doi-asserted-by":"crossref","unstructured":"Styer, E., Peterson, G.L.: Tight bounds for shared memory symmetric mutual exclusion problems. In: Proceedings of the 8th Annual ACM Symposium on Principles of Distributed Computing, pp. 177\u2013191. ACM (1989)","DOI":"10.1145\/72981.72993"},{"key":"331_CR15","doi-asserted-by":"crossref","unstructured":"Zhu, L.: Brief announcement: Tight space bounds for memoryless anonymous consensus. In: Proceedings of the 29th International Symposium on Distributed Computing, p. 665. Springer (2015)","DOI":"10.1145\/2933057.2933078"},{"key":"331_CR16","doi-asserted-by":"crossref","unstructured":"Zhu, L.: A tight space bound for consensus. In: Proceedings of the 48th Annual ACM Symposium on Theory of Computing, pp. 345\u2013350. ACM (2016)","DOI":"10.1145\/2897518.2897565"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-018-0331-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-018-0331-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-018-0331-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,16]],"date-time":"2022-08-16T20:07:18Z","timestamp":1660680438000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-018-0331-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,23]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,8]]}},"alternative-id":["331"],"URL":"https:\/\/doi.org\/10.1007\/s00446-018-0331-9","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2018,3,23]]},"assertion":[{"value":"29 February 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 March 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}