{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T11:31:49Z","timestamp":1768908709408,"version":"3.49.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,5,3]],"date-time":"2017-05-03T00:00:00Z","timestamp":1493769600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00446-017-0301-7","type":"journal-article","created":{"date-parts":[[2017,5,3]],"date-time":"2017-05-03T11:29:19Z","timestamp":1493810959000},"page":"99-117","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Anonymous obstruction-free (n,\u00a0k)-set agreement with $$n-k+1$$ n - k + 1 atomic read\/write registers"],"prefix":"10.1007","volume":"31","author":[{"given":"Zohir","family":"Bouzid","sequence":"first","affiliation":[]},{"given":"Michel","family":"Raynal","sequence":"additional","affiliation":[]},{"given":"Pierre","family":"Sutra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,3]]},"reference":[{"issue":"4","key":"301_CR1","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1145\/153724.153741","volume":"40","author":"Y Afek","year":"1993","unstructured":"Afek, Y., Attiya, H., Dolev, D., Gafni, E., Merritt, M., Shavit, N.: Atomic snapshots of shared memory. J. ACM 40(4), 873\u2013890 (1993)","journal-title":"J. ACM"},{"issue":"2","key":"301_CR2","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1145\/992287.992298","volume":"35","author":"M Aguilera","year":"2004","unstructured":"Aguilera, M.: A pleasant stroll through the land of infinitely many creatures. ACM SIGACT News DC Column 35(2), 36\u201359 (2004)","journal-title":"ACM SIGACT News DC Column"},{"issue":"2","key":"301_CR3","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1006\/inco.2001.3119","volume":"173","author":"H Attiya","year":"2002","unstructured":"Attiya, H., Gorbach, A., Moran, S.: Computing in totally anonymous asynchronous shared memory systems. Inf. Comput. 173(2), 162\u2013183 (2002)","journal-title":"Inf. Comput."},{"key":"301_CR4","doi-asserted-by":"crossref","unstructured":"Attiya, H., Guerraoui, R., Hendler, D., Kuznetsov, P.: The complexity of obstruction-free implementations. J. ACM 56(4), 24:1\u201324:33 (2009)","DOI":"10.1145\/1538902.1538908"},{"key":"301_CR5","doi-asserted-by":"crossref","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, 441\u2013461 (1990)","journal-title":"J. Algorithms"},{"issue":"3","key":"301_CR6","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/s00446-012-0169-5","volume":"26","author":"F Bonnet","year":"2013","unstructured":"Bonnet, F., Raynal, M.: Anonymous asynchronous systems: the case of failure detectors. Distrib. Comput. 26(3), 141\u2013158 (2013)","journal-title":"Distrib. Comput."},{"key":"301_CR7","doi-asserted-by":"crossref","unstructured":"Borowsky, E., Gafni, E.: Generalized FLP impossibility result for $$t$$ t -resilient asynchronous computations. In: Proceedings of 25-th nnual ACM Symposium on Theory of Computing (STOC\u201993), ACM Press, pp. 91\u2013100 (1993)","DOI":"10.1145\/167088.167119"},{"issue":"3","key":"301_CR8","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/PL00008933","volume":"14","author":"E Borowsky","year":"2001","unstructured":"Borowsky, E., Gafni, E., Lynch, N., Rajsbaum, S.: The BG distributed simulation algorithm. Distrib. Comput. 14(3), 127\u2013146 (2001)","journal-title":"Distrib. Comput."},{"key":"301_CR9","unstructured":"Bouzid, Z., Raynal, M., Sutra, P.: Anonymous obstruction-free $$(n,k)$$ ( n , k ) -set agreement with $$n-k+1$$ n - k + 1 atomic read\/write registers. In: Proceedings of 19th International Conference on Principles of Distributed Systems (OPODIS\u201915), Leibnitz International Proceedings in Informatics (LIPIcs), vol. 46, Article 18:1\u201317 (2015)"},{"key":"301_CR10","doi-asserted-by":"crossref","unstructured":"Casta\u00f1eda, A., Rajsbaum, S., Raynal, M.: Specifying concurrent problems: beyond linearizability and up to tasks. In: Proceedings of 29th Symposium on Distributed Computing (DISC\u201915), Springer LNCS 9363, pp. 420\u2013435 (2015)","DOI":"10.1007\/978-3-662-48653-5_28"},{"issue":"4","key":"301_CR11","doi-asserted-by":"crossref","first-page":"685","DOI":"10.1145\/234533.234549","volume":"43","author":"T Chandra","year":"1996","unstructured":"Chandra, T., Hadzilacos, V., Toueg, S.: The weakest failure detector for solving consensus. J. ACM 43(4), 685\u2013722 (1996)","journal-title":"J. ACM"},{"key":"301_CR12","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, 132\u2013158 (1993)","journal-title":"Inf. Comput."},{"key":"301_CR13","doi-asserted-by":"crossref","unstructured":"Delporte, C, Fauconnier, H, Gafni, E., Rajsbaum, S.: Black art: obstruction-free $$k$$ k -set agreement with $$|$$ | MWMR registers $$| < |$$ | < | processes $$|$$ | . In: Proceedings of First International Conference on Networked Systems (NETYS\u201913), Springer LNCS 7853, pp. 28\u201341 (2013)","DOI":"10.1007\/978-3-642-40148-0_3"},{"key":"301_CR14","doi-asserted-by":"crossref","unstructured":"Delporte-Gallet, C., Fauconnier, H.: Two consensus algorithms with atomic registers and failure detector $$\\Omega $$ \u03a9 . In: Proceedings of 10th International Conference on Distributed Computing and Networking (ICDCN\u201909), Springer LNCS 5408, pp. 251\u2013262 (2009)","DOI":"10.1007\/978-3-540-92295-7_31"},{"key":"301_CR15","doi-asserted-by":"crossref","unstructured":"Delporte, C., Fauconnier, H., Kuznetsov, P., Ruppert, E.: On the space complexity of set agreement. In: Proceedings of 34th International Symposium on Principles of Distributed Computing (PODC\u201915), ACM Press, pp. 271\u2013280 (2015)","DOI":"10.1145\/2767386.2767406"},{"key":"301_CR16","doi-asserted-by":"crossref","unstructured":"Ellen Fich, F., Luchangco, V., Moir, M., Shavit, N.: Obstruction-free algorithms can be practically wait-free. In: Proceedings of 19th International Symposium on Distributed Computing (DISC\u201905), Springer LNCS 3724, pp. 78\u201392 (2005)","DOI":"10.1007\/11561927_8"},{"issue":"2","key":"301_CR17","doi-asserted-by":"crossref","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":"301_CR18","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Hard tasks for weak robots: the role of common knowledge in pattern formation by autonomous mobile robots. In: Proceedings of 10th International Symposium on Algorithms and Computation (ISAAC\u201999), Springer LNCS 1741, pp. 93\u2013102 (1999)","DOI":"10.1007\/3-540-46632-0_10"},{"issue":"7","key":"301_CR19","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1109\/TC.2007.1043","volume":"56","author":"R Friedman","year":"2007","unstructured":"Friedman, R., Mostefaoui, A., Rajsbaum, S., Raynal, M.: Distributed agreement problems and their connection with error-correcting codes. IEEE Trans. Comput. 56(7), 865\u2013875 (2007)","journal-title":"IEEE Trans. Comput."},{"key":"301_CR20","doi-asserted-by":"crossref","unstructured":"Gelashvili, R.: Optimal space complexity of consensus for anonymous processes. In: Proceedings of 29th Int\u2019l Symposium on Distributed Computing (DISC\u201915), Springer LNCS 9363, pp. 452\u2013466 (2015)","DOI":"10.1007\/978-3-662-48653-5_30"},{"key":"301_CR21","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 computations. Distrib. Comput. 20, 165\u2013177 (2007)","journal-title":"Distrib. Comput."},{"issue":"1","key":"301_CR22","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"MP Herlihy","year":"1991","unstructured":"Herlihy, M.P.: Wait-free synchronization. ACM Trans. Program. Lang. Syst. 13(1), 124\u2013149 (1991)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"301_CR23","doi-asserted-by":"crossref","unstructured":"Herlihy, M.P., Luchangco, V., Moir, M.: Obstruction-free synchronization: double-ended queues as an example. In: Proceedings of 23th International IEEE Conference on Distributed Computing Systems (ICDCS\u201903), IEEE Press, pp. 522\u2013529 (2003)","DOI":"10.1109\/ICDCS.2003.1203503"},{"issue":"6","key":"301_CR24","doi-asserted-by":"crossref","first-page":"858","DOI":"10.1145\/331524.331529","volume":"46","author":"MP Herlihy","year":"1999","unstructured":"Herlihy, M.P., Shavit, N.: The topological structure of asynchronous computability. J. ACM 46(6), 858\u2013923 (1999)","journal-title":"J. ACM"},{"key":"301_CR25","volume-title":"The Art of Multiprocessor Programming","author":"MP Herlihy","year":"2008","unstructured":"Herlihy, M.P., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann, Burlington (2008). ISBN 978-0-12-370591-4"},{"issue":"3","key":"301_CR26","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"MP Herlihy","year":"1990","unstructured":"Herlihy, M.P., 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":"11","key":"301_CR27","doi-asserted-by":"crossref","first-page":"806","DOI":"10.1145\/359863.359878","volume":"20","author":"L Lamport","year":"1977","unstructured":"Lamport, L.: Concurrent reading and writing. Commun. ACM 20(11), 806\u2013811 (1977)","journal-title":"Commun. ACM"},{"issue":"2","key":"301_CR28","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1007\/BF01786227","volume":"1","author":"L Lamport","year":"1986","unstructured":"Lamport, L.: On interprocess communication, part I: basic formalism. Distrib. Comput. 1(2), 77\u201385 (1986)","journal-title":"Distrib. Comput."},{"key":"301_CR29","unstructured":"Loui, M.C., Abu-Amara, H.H.: Memory requirements for agreement among unreliable asynchronous processes. Parallel and Distributed Computing: Vol.\u00a04 of Advances in Computing Research, JAI Press, 4:163\u2013183 (1987)"},{"key":"301_CR30","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1016\/j.ic.2013.11.007","volume":"233","author":"M Merritt","year":"2013","unstructured":"Merritt, M., Taubenfeld, G.: Computing with infinitely many processes. Inf. Comput. 233, 12\u201331 (2013)","journal-title":"Inf. Comput."},{"key":"301_CR31","doi-asserted-by":"crossref","first-page":"46","DOI":"10.1145\/357195.357198","volume":"5","author":"GL Peterson","year":"1983","unstructured":"Peterson, G.L.: Concurrent reading while writing. ACM Trans. Program. Lang. Syst. 5, 46\u201355 (1983)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"301_CR32","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-32027-9","volume-title":"Concurrent Programming: Algorithms, Principles, and Foundations","author":"M Raynal","year":"2013","unstructured":"Raynal, M.: Concurrent Programming: Algorithms, Principles, and Foundations. Springer, Berlin (2013). ISBN 978-3-642-32026-2"},{"key":"301_CR33","doi-asserted-by":"crossref","unstructured":"Raynal, M., Stainer, J.: From the $$\\Omega $$ \u03a9 and store-collect building blocks to efficient asynchronous consensus. In: Proceedings of 18th Interenational European Parallel Computing Conference (EUROPAR\u201912), Springer LNCS 7484, pp. 427\u2013438 (2012)","DOI":"10.1007\/978-3-642-32820-6_43"},{"key":"301_CR34","unstructured":"Saks, M., Shavit, N., Woll, H.: Optimal time randomized consensus\u2014making resilient algorithms fast in practice. In: Proceedings of 2nd ACM\/SIAM Symposium on Discrete Algorithms (SODA\u201990), ACM Press, pp. 351\u2013362 (1991)"},{"issue":"5","key":"301_CR35","doi-asserted-by":"crossref","first-page":"1449","DOI":"10.1137\/S0097539796307698","volume":"29","author":"M Saks","year":"2000","unstructured":"Saks, M., 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."},{"key":"301_CR36","unstructured":"Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots. In: Proceedings of 3rd International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201996), Carleton University Press, pp. 313\u2013330 (1996)"},{"key":"301_CR37","volume-title":"Synchronization Algorithms and Concurrent Programming","author":"G Taubenfeld","year":"2006","unstructured":"Taubenfeld, G.: Synchronization Algorithms and Concurrent Programming. Pearson Education\/Prentice Hall, Upper Saddle River (2006). ISBN 0-131-97259-6"},{"key":"301_CR38","doi-asserted-by":"crossref","unstructured":"Taubenfeld, G.: Contention-sensitive data structure and algorithms. In: Proceedings of 23th International Symposium on Distributed Computing (DISC\u201909), Springer LNCS 5805, pp. 157\u2013171 (2009)","DOI":"10.1007\/978-3-642-04355-0_17"},{"issue":"1","key":"301_CR39","doi-asserted-by":"crossref","first-page":"90","DOI":"10.1109\/71.481600","volume":"7","author":"M Yamashita","year":"1996","unstructured":"Yamashita, M., Kameda, T.: Computing on anonymous networks: part II-decision and membership problems. IEEE Trans. Parallel Distrib. Syst. 7(1), 90\u201396 (1996)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"301_CR40","doi-asserted-by":"crossref","unstructured":"Yanagisawa, N.: Wait-free solvability of colorless takss in anonymous shared-memory model. In: Proc. 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS\u201916), Springer LNCS 10083, pp.\u00a0415\u2013429 (2016)","DOI":"10.1007\/978-3-319-49259-9_32"},{"key":"301_CR41","unstructured":"Zhu, L.: Brief announcement: tight space bounds for memoryless anonymous consensus. In: Proceedings of 29th Symposium on Distributed Computing (DISC\u201915), Springer LNCS 9363, pp. 665\u2013666 (2015)"},{"key":"301_CR42","doi-asserted-by":"crossref","unstructured":"Zhu, L.: A tight space bound for consensus. In: Proc. 48th ACM Symposium on Theory of Computing (STOC\u201916), ACM Press, pp. 345\u2013350 (2016)","DOI":"10.1145\/2897518.2897565"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0301-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0301-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0301-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,6]],"date-time":"2020-10-06T21:12:17Z","timestamp":1602018737000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0301-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,5,3]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["301"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0301-7","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,5,3]]}}}