{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:22Z","timestamp":1759638322064,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2017,3,18]],"date-time":"2017-03-18T00:00:00Z","timestamp":1489795200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-11-BS02-014"],"award-info":[{"award-number":["ANR-11-BS02-014"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Agence Nationale de la Recherche (FR)","award":["ANR-14-CE35-0010-01"],"award-info":[{"award-number":["ANR-14-CE35-0010-01"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2017,12]]},"DOI":"10.1007\/s00446-017-0297-z","type":"journal-article","created":{"date-parts":[[2017,3,18]],"date-time":"2017-03-18T07:39:44Z","timestamp":1489822784000},"page":"459-468","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the uncontended complexity of anonymous agreement"],"prefix":"10.1007","volume":"30","author":[{"given":"Claire","family":"Capdevielle","sequence":"first","affiliation":[]},{"given":"Colette","family":"Johnen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1148-1228","authenticated-orcid":false,"given":"Petr","family":"Kuznetsov","sequence":"additional","affiliation":[]},{"given":"Alessia","family":"Milani","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,3,18]]},"reference":[{"issue":"3","key":"297_CR1","doi-asserted-by":"crossref","first-page":"451","DOI":"10.1007\/s00224-013-9448-1","volume":"55","author":"J Aspnes","year":"2014","unstructured":"Aspnes, J., Ellen, F.: Tight bounds for adopt-commit objects. Theory Comput. Syst. 55(3), 451\u2013474 (2014)","journal-title":"Theory Comput. Syst."},{"doi-asserted-by":"crossref","unstructured":"Attiya, H., Guerraoui, R., Hendler, D., Kuznetsov, P.: The complexity of obstruction-free implementations. J. ACM. 56(4), 1\u201324 (2009)","key":"297_CR2","DOI":"10.1145\/1538902.1538908"},{"doi-asserted-by":"crossref","unstructured":"Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing, STOC 1993, pp. 91\u2013100. (1993)","key":"297_CR3","DOI":"10.1145\/167088.167119"},{"unstructured":"Bouzid, Z., Raynal, M., Sutra, P.: Anonymous obstruction-free (n, k)-set agreement with n $$-$$ - k + 1 atomic read\/write registers. In: Proceedings of the 19th International Conference on Principles of Distributed Systems, OPODIS 2015, pp. 18:1\u201318:17. (2015)","key":"297_CR4"},{"doi-asserted-by":"crossref","unstructured":"Buhrman, H., Garay, J.A., Hoepman, J., Moir, M.: Long-lived renaming made fast. In: Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing, PODC 1995, pp. 194\u2013203. (1995)","key":"297_CR5","DOI":"10.1145\/224964.224986"},{"unstructured":"Capdevielle, C., Johnen, C., Kuznetsov, P., Milani, A.: On the uncontended complexity of anonymous consensus. In: Proceedings of the 19th International Conference on Principles of Distributed Systems, OPODIS 2015, pp. 12:1\u201312:16. (2015)","key":"297_CR6"},{"issue":"1","key":"297_CR7","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1006\/inco.1993.1043","volume":"105","author":"S Chaudhuri","year":"1993","unstructured":"Chaudhuri, S.: More choices allow more faults: set consensus problems in totally asynchronous systems. Inf. Comput. 105(1), 132\u2013158 (1993)","journal-title":"Inf. Comput."},{"doi-asserted-by":"crossref","unstructured":"Delporte-Gallet, C., Fauconnier, H., Kuznetsov, P., Ruppert, E.: On the space complexity of set agreement. In: Proceedings of the 34th ACM Symposium on Principles of Distributed Computing, PODC 2015, pp. 271\u2013280. (2015)","key":"297_CR8","DOI":"10.1145\/2767386.2767406"},{"issue":"5","key":"297_CR9","doi-asserted-by":"crossref","first-page":"843","DOI":"10.1145\/290179.290183","volume":"45","author":"FE Fich","year":"1998","unstructured":"Fich, F.E., Herlihy, M., Shavit, N.: On the space complexity of randomized synchronization. J. ACM 45(5), 843\u2013862 (1998)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374\u2013382 (1985)","key":"297_CR10","DOI":"10.1145\/3149.214121"},{"doi-asserted-by":"crossref","unstructured":"Gafni, E., Guerraoui, R.: Generalized universality. In: Proceedings of the 22nd International Conference on Concurrency Theory, CONCUR 2011, pp. 17\u201327. (2011)","key":"297_CR11","DOI":"10.1007\/978-3-642-23217-6_2"},{"doi-asserted-by":"crossref","unstructured":"Gelashvili, R.: On the optimal space complexity of consensus for anonymous processes. In: Proceedings of the 29th International Symposium on Distributed Computing, DISC 2015, pp. 452\u2013466. (2015)","key":"297_CR12","DOI":"10.1007\/978-3-662-48653-5_30"},{"doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Helmi, M., Higham, L., Woelfel, P.: An $$O(\\sqrt{n})$$ O ( n ) space bound for obstruction-free leader election. In: Proceedings of the 27th International Symposium on Distributed Computing, DISC 2013, pp. 46\u201360. (2013)","key":"297_CR13","DOI":"10.1007\/978-3-642-41527-2_4"},{"issue":"3","key":"297_CR14","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s00446-007-0042-0","volume":"20","author":"R Guerraoui","year":"2007","unstructured":"Guerraoui, R., Ruppert, E.: Anonymous and fault-tolerant shared-memory computing. Distrib. Comput. 20(3), 165\u2013177 (2007)","journal-title":"Distrib. Comput."},{"doi-asserted-by":"crossref","unstructured":"Hadzilacos, V., Toueg, S.: On deterministic abortable objects. In: Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing, PODC 2013, pp. 4\u201312. (2013)","key":"297_CR15","DOI":"10.1145\/2484239.2484241"},{"issue":"1","key":"297_CR16","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"M Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124\u2013149 (1991)","journal-title":"ACM Trans. Program. Lang. Syst."},{"doi-asserted-by":"crossref","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: double-ended queues as an example. In: Proceedings of the 23rd International Conference on Distributed Computing Systems, ICDCS 2003, pp. 522\u2013529. (2003)","key":"297_CR17","DOI":"10.1109\/ICDCS.2003.1203503"},{"issue":"6","key":"297_CR18","doi-asserted-by":"crossref","first-page":"858","DOI":"10.1145\/331524.331529","volume":"46","author":"M Herlihy","year":"1999","unstructured":"Herlihy, M., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858\u2013923 (1999)","journal-title":"J. ACM"},{"issue":"3","key":"297_CR19","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"M Herlihy","year":"1990","unstructured":"Herlihy, M., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Program. Lang. Syst. 12(3), 463\u2013492 (1990)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"1","key":"297_CR20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/7351.7352","volume":"5","author":"L Lamport","year":"1987","unstructured":"Lamport, L.: A fast mutual exclusion algorithm. ACM Trans. Comput. Syst. 5(1), 1\u201311 (1987)","journal-title":"ACM Trans. Comput. Syst."},{"unstructured":"Loui, M.C., Abu-Amara, H.H.: Memory requirements for agreement among unreliable asynchronous processes. Adv. Comput. Res. 4, 163\u2013183 (1987)","key":"297_CR21"},{"doi-asserted-by":"crossref","unstructured":"Luchangco, V., Moir, M., Shavit, N.: On the uncontended complexity of consensus. In: Proceedings of the 17th International Conference on Distributed Computing, DISC 2003, pp. 45\u201359. (2003)","key":"297_CR22","DOI":"10.1007\/978-3-540-39989-6_4"},{"issue":"1","key":"297_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0167-6423(95)00009-H","volume":"25","author":"M Moir","year":"1995","unstructured":"Moir, M., Anderson, J.H.: Wait-free algorithms for fast, long-lived renaming. Sci. Comput. Program. 25(1), 1\u201339 (1995)","journal-title":"Sci. Comput. Program."},{"issue":"5","key":"297_CR24","doi-asserted-by":"crossref","first-page":"1449","DOI":"10.1137\/S0097539796307698","volume":"29","author":"ME Saks","year":"2000","unstructured":"Saks, M.E., Zaharoglou, F.: Wait-free k-set agreement is impossible: the topology of public knowledge. SIAM J. Comput. 29(5), 1449\u20131483 (2000)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Yang, J., Neiger, G., Gafni, E.: Structured derivations of consensus algorithms for failure detectors. In: Proceedings of the 17th Annual ACM Symposium on Principles of Distributed Computing, PODC 1998, pp. 297\u2013306. (1998)","key":"297_CR25","DOI":"10.1145\/277697.277755"},{"doi-asserted-by":"crossref","unstructured":"Zhu, L.: A tight space bound for consensus. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, pp. 345\u2013350. (2016)","key":"297_CR26","DOI":"10.1145\/2897518.2897565"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0297-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0297-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0297-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,19]],"date-time":"2019-09-19T18:40:51Z","timestamp":1568918451000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0297-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,18]]},"references-count":26,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,12]]}},"alternative-id":["297"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0297-z","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2017,3,18]]}}}