{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,7]],"date-time":"2024-09-07T21:14:16Z","timestamp":1725743656230},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642401473"},{"type":"electronic","value":"9783642401480"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-40148-0_3","type":"book-chapter","created":{"date-parts":[[2013,8,2]],"date-time":"2013-08-02T01:02:49Z","timestamp":1375405369000},"page":"28-41","source":"Crossref","is-referenced-by-count":4,"title":["Black Art: Obstruction-Free k-set Agreement with |MWMR\u00a0registers|\u2009<\u00a0|proccesses|"],"prefix":"10.1007","author":[{"given":"Carole","family":"Delporte-Gallet","sequence":"first","affiliation":[]},{"given":"Hugues","family":"Fauconnier","sequence":"additional","affiliation":[]},{"given":"Eli","family":"Gafni","sequence":"additional","affiliation":[]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"3_CR1","doi-asserted-by":"publisher","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. Journal of the ACM\u00a040(4), 873\u2013890 (1993)","journal-title":"Journal of the ACM"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Ellen, F.: Tight bounds for anonymous adopt-commit objects. In: Rajaraman, R., auf der Heide, F.M. (eds.) Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 2011(Co-located with FCRC 2011), San Jose, CA, USA, June 4-6, pp. 317\u2013324. ACM (2011)","DOI":"10.1145\/1989493.1989548"},{"issue":"3","key":"3_CR3","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1145\/79147.79158","volume":"37","author":"H. Attiya","year":"1990","unstructured":"Attiya, H., Bar-Noy, A., Dolev, D., Peleg, D., Reischuk, R.: Renaming in an asynchronous environment. Journal of the ACM\u00a037(3), 524\u2013548 (1990)","journal-title":"Journal of the ACM"},{"issue":"2","key":"3_CR4","doi-asserted-by":"publisher","first-page":"642","DOI":"10.1137\/S0097539700366000","volume":"31","author":"H. Attiya","year":"2002","unstructured":"Attiya, H., Fouren, A.: Adaptive and efficient algorithms for lattice agreement and renaming. SIAM J. Comput.\u00a031(2), 642\u2013664 (2002)","journal-title":"SIAM J. Comput."},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Attiya, H., Guerraoui, R., Hendler, D., Kuznetsov, P.: The complexity of obstruction-free implementations. J. ACM\u00a056(4) (2009)","DOI":"10.1145\/1538902.1538908"},{"key":"3_CR6","doi-asserted-by":"crossref","unstructured":"Attiya, H., Welch, J.: Distributed Computing. Fundamentals, Simulations, and Advanced Topics. John Wiley & Sons (2004)","DOI":"10.1002\/0471478210"},{"key":"3_CR7","doi-asserted-by":"crossref","unstructured":"Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. In: STOC, pp. 91\u2013100. ACM Press (1993)","DOI":"10.1145\/167088.167119"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Borowsky, E., Gafni, E.: Immediate atomic snapshots and fast renaming. In: PODC, pp. 41\u201351. ACM Press (1993)","DOI":"10.1145\/164051.164056"},{"key":"3_CR9","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1145\/259380.259439","volume-title":"Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, PODC 1997","author":"E. Borowsky","year":"1997","unstructured":"Borowsky, E., Gafni, E.: A simple algorithmically reasoned characterization of wait-free computation (extended abstract). In: Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, PODC 1997, pp. 189\u2013198. ACM Press, New York (1997)"},{"issue":"2","key":"3_CR10","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1006\/inco.1993.1065","volume":"107","author":"J.E. Burns","year":"1993","unstructured":"Burns, J.E., Lynch, N.A.: Bounds on shared memory for mutual exclusion. Inf. Comput.\u00a0107(2), 171\u2013184 (1993)","journal-title":"Inf. Comput."},{"issue":"1","key":"3_CR11","doi-asserted-by":"publisher","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. Information and Computation\u00a0105(1), 132\u2013158 (1993)","journal-title":"Information and Computation"},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1007\/978-3-540-92295-7_31","volume-title":"Distributed Computing and Networking","author":"C. Delporte-Gallet","year":"2008","unstructured":"Delporte-Gallet, C., Fauconnier, H.: Two Consensus Algorithms with Atomic Registers and Failure Detector \u03a9. In: Garg, V., Wattenhofer, R., Kothapalli, K. (eds.) ICDCN 2009. LNCS, vol.\u00a05408, pp. 251\u2013262. Springer, Heidelberg (2008)"},{"key":"3_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/978-3-642-35668-1_25","volume-title":"Distributed Computing and Networking","author":"C. Delporte-Gallet","year":"2013","unstructured":"Delporte-Gallet, C., Fauconnier, H., Gafni, E., Rajsbaum, S.: Linear space bootstrap communication schemes. In: Frey, D., Raynal, M., Sarkar, S., Shyamasundar, R.K., Sinha, P. (eds.) ICDCN 2013. LNCS, vol.\u00a07730, pp. 363\u2013377. Springer, Heidelberg (2013)"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Delporte-Gallet, C., Fauconnier, H., Gafni, E., Rajsbaum, S.: Linear space bootstrap communication scheme. Technical report (2013)","DOI":"10.1007\/978-3-642-35668-1_25"},{"issue":"2","key":"3_CR15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1007\/s00446-008-0060-6","volume":"21","author":"F. Ellen","year":"2008","unstructured":"Ellen, F., Fatourou, P., Ruppert, E.: The space complexity of unbounded timestamps. Distributed Computing\u00a021(2), 103\u2013115 (2008)","journal-title":"Distributed Computing"},{"issue":"5","key":"3_CR16","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1145\/290179.290183","volume":"45","author":"F.E. Fich","year":"1998","unstructured":"Fich, F.E., 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":"3_CR17","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. Journal of the ACM\u00a032(2), 374\u2013382 (1985)","journal-title":"Journal of the ACM"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Gafni, E.: Round-by-round fault detectors (extended abstract): Unifying synchrony and asynchrony. In: Proceedings of the 17th Symposium on Principles of Distributed Computing (1998)","DOI":"10.1145\/277697.277724"},{"issue":"14","key":"3_CR19","doi-asserted-by":"publisher","first-page":"1328","DOI":"10.1016\/j.tcs.2008.05.016","volume":"410","author":"E. Gafni","year":"2009","unstructured":"Gafni, E., Most\u00e9faoui, A., Raynal, M., Travers, C.: From adaptive renaming to set agreement. Theor. Comput. Sci.\u00a0410(14), 1328\u20131335 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR20","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1145\/1993806.1993826","volume-title":"Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2011","author":"M. Helmi","year":"2011","unstructured":"Helmi, M., Higham, L., Pacheco, E., Woelfel, P.: The space complexity of long-lived and one-shot timestamp implementations. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2011, pp. 139\u2013148. ACM, New York (2011)"},{"issue":"1","key":"3_CR21","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1145\/114005.102808","volume":"13","author":"M. Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. ACM Transactions on Programming Languages and Systems\u00a013(1), 123\u2013149 (1991)","journal-title":"ACM Transactions on Programming Languages and Systems"},{"key":"3_CR22","unstructured":"Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example. In: 23rd International Conference on Distributed Computing Systems, ICDCS 2003, Providence, RI, USA, May 19-22, pp. 522\u2013529. IEEE Computer Society (2003)"},{"issue":"2","key":"3_CR23","doi-asserted-by":"publisher","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. Journal of the ACM\u00a046(2), 858\u2013923 (1999)","journal-title":"Journal of the ACM"},{"key":"3_CR24","unstructured":"Herlihy, M., Shavit, N.: The Art of Multiprocessor Programming. Morgan Kaufmann (2008)"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Saks, M., Zaharoglou, F.: Wait-free k-set agreement is impossible: The topology of public knowledge. In: Proceedings of the 25th ACM Symposium on Theory of Computing, pp. 101\u2013110. ACM Press (May 1993)","DOI":"10.1145\/167088.167122"},{"key":"3_CR26","doi-asserted-by":"publisher","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. on Computing\u00a029, 1449\u20131483 (2000)","journal-title":"SIAM J. on Computing"},{"key":"3_CR27","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1145\/72981.72993","volume-title":"Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, PODC 1989","author":"E. Styer","year":"1989","unstructured":"Styer, E., Peterson, G.L.: Tight bounds for shared memory symmetric mutual exclusion problems. In: Proceedings of the Eighth Annual ACM Symposium on Principles of Distributed Computing, PODC 1989, pp. 177\u2013191. ACM, New York (1989)"},{"key":"3_CR28","doi-asserted-by":"crossref","unstructured":"Yang, J., Neiger, G., Gafni, E.: Structured derivations of consensus algorithms for failure detectors. In: Proceedings of the 17th ACM Symposium on Principles of Distributed Computing, pp. 297\u2013306 (1998)","DOI":"10.1145\/277697.277755"}],"container-title":["Lecture Notes in Computer Science","Networked Systems"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-40148-0_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T04:54:57Z","timestamp":1557982497000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-40148-0_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642401473","9783642401480"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-40148-0_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}