{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T16:29:29Z","timestamp":1722616169921},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,11,13]],"date-time":"2017-11-13T00:00:00Z","timestamp":1510531200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s00224-017-9819-0","type":"journal-article","created":{"date-parts":[[2017,11,12]],"date-time":"2017-11-12T21:29:22Z","timestamp":1510522162000},"page":"219-236","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Wait-free Solvability of Colorless Tasks in Anonymous Shared-memory Model"],"prefix":"10.1007","volume":"63","author":[{"given":"Nayuta","family":"Yanagisawa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,13]]},"reference":[{"issue":"4","key":"9819_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. J. ACM 40(4), 873\u2013890 (1993)","journal-title":"J. ACM"},{"key":"9819_CR2","doi-asserted-by":"crossref","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proceedings of the 12th Annual ACM Symposium on Theory of Computing (STOC), pp. 82\u201393 (1980)","DOI":"10.1145\/800141.804655"},{"issue":"4","key":"9819_CR3","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/s00446-005-0138-3","volume":"18","author":"D Angluin","year":"2006","unstructured":"Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235\u2013253 (2006)","journal-title":"Distrib. Comput."},{"key":"9819_CR4","unstructured":"Aspnes, J.: Slightly smaller splitter networks. Tech. Rep. YALEU\/DCS\/TR-1438 Yale University Department of Computer Science (2010)"},{"issue":"3","key":"9819_CR5","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s00446-005-0145-4","volume":"18","author":"J Aspnes","year":"2006","unstructured":"Aspnes, J., Fich, F.E., Ruppert, E.: Relationships between broadcast and shared memory in reliable anonymous distributed systems. Distrib. Comput. 18(3), 209\u2013219 (2006)","journal-title":"Distrib. Comput."},{"issue":"3","key":"9819_CR6","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. J. ACM 37(3), 524\u2013548 (1990)","journal-title":"J. ACM"},{"issue":"2","key":"9819_CR7","doi-asserted-by":"publisher","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":"9819_CR8","doi-asserted-by":"crossref","unstructured":"Baldoni, R., Bonomi, S., Raynal, M.: Value-based sequential consistency for set objects in dynamic distributed systems. In: Proceedings of the 16th International Euro-Par Conference (Euro-Par), pp. 523\u2013534 (2010)","DOI":"10.1007\/978-3-642-15277-1_50"},{"issue":"5","key":"9819_CR9","doi-asserted-by":"publisher","first-page":"654","DOI":"10.1016\/j.jcss.2015.11.002","volume":"82","author":"R Baldoni","year":"2016","unstructured":"Baldoni, R., Bonomi, S., Raynal, M.: Implementing set objects in dynamic distributed systems. J. Comput. Syst. Sci. 82(5), 654\u2013689 (2016)","journal-title":"J. Comput. Syst. Sci."},{"key":"9819_CR10","doi-asserted-by":"crossref","unstructured":"Borowsky, E., Gafni, E.: Immediate atomic snapshots and fast renaming. In: Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 41\u201351 (1993)","DOI":"10.1145\/164051.164056"},{"key":"9819_CR11","unstructured":"Capdevielle, C., Johnen, C., Kuznetsov, P., Milani, A.: On the Uncontended Complexity of Anonymous Consensus. In: Anceaume, E., Cachin, C., Potop-Butucaru, M. (eds.) 19th International Conference on Principles of Distributed Systems (OPODIS 2015), Leibniz International Proceedings in Informatics (LIPIcs), vol. 46, pp 1\u201316. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl (2016)"},{"issue":"1","key":"9819_CR12","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. Inf. Comput. 105(1), 132\u2013158 (1993)","journal-title":"Inf. Comput."},{"key":"9819_CR13","doi-asserted-by":"crossref","unstructured":"Chothia, T., Chatzikokolakis, K.: A survey of anonymous peer-to-peer file-sharing. In: Proceedings of Satellite Workshop of the International Conference on Embedded and Ubiquitous Systems (EUS), pp. 744\u2013755 (2005)","DOI":"10.1007\/11596042_77"},{"key":"9819_CR14","doi-asserted-by":"crossref","unstructured":"Delporte-Gallet, C., Fauconnier, H.: Two consensus algorithms with atomic registers and failure detector \u03c9. In: Proceedings of the 10th International Conference on Distributed Computing and Networking (ICDCN), pp. 251\u2013262 (2009)","DOI":"10.1007\/978-3-540-92295-7_31"},{"key":"9819_CR15","doi-asserted-by":"crossref","unstructured":"Delporte-Gallet, C., Fauconnier, H., Guerraoui, R., Kermarrec, A.M., Ruppert, E., Tran-The, H.: Byzantine agreement with homonyms. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 21\u201330 (2011)","DOI":"10.1145\/1993806.1993810"},{"issue":"3","key":"9819_CR16","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1145\/5925.5931","volume":"33","author":"D Dolev","year":"1986","unstructured":"Dolev, D., Lynch, N.A., Pinter, S.S., Stark, E.W., Weihl, W.E.: Reaching approximate agreement in the presence of faults. J. ACM 33(3), 499\u2013516 (1986)","journal-title":"J. ACM"},{"issue":"2","key":"9819_CR17","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/s00446-003-0091-y","volume":"16","author":"F Fich","year":"2003","unstructured":"Fich, F., Ruppert, E.: Hundreds of impossibility results for distributed computing. Distrib. Comput. 16(2), 121\u2013163 (2003)","journal-title":"Distrib. Comput."},{"issue":"2","key":"9819_CR18","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"},{"issue":"3","key":"9819_CR19","doi-asserted-by":"publisher","first-page":"970","DOI":"10.1137\/S0097539796305766","volume":"28","author":"E Gafni","year":"1999","unstructured":"Gafni, E., Koutsoupias, E.: Three-processor tasks are undecidable. SIAM J. Comput. 28(3), 970\u2013983 (1999)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9819_CR20","doi-asserted-by":"publisher","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."},{"key":"9819_CR21","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Kozlov, D., Rajsbaum, S.: Distributed Computing Through Combinatorial Topology. Morgan Kaufmann (2013)","DOI":"10.1016\/B978-0-12-404578-1.00003-6"},{"key":"9819_CR22","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks (extended abstract). In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC), pp. 589\u2013598 (1997)","DOI":"10.1145\/258533.258652"},{"issue":"1","key":"9819_CR23","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0304-3975(01)00396-6","volume":"291","author":"M Herlihy","year":"2003","unstructured":"Herlihy, M., Rajsbaum, S.: A classification of wait-free loop agreement tasks. Theor. Comput. Sci. 291(1), 55\u201377 (2003)","journal-title":"Theor. Comput. Sci."},{"key":"9819_CR24","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Rajsbaum, S.: The topology of shared-memory adversaries. In: Proceedings of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), pp. 105\u2013113 (2010)","DOI":"10.1145\/1835698.1835724"},{"key":"9819_CR25","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Rajsbaum, S.: Simulations and reductions for colorless tasks. In: Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing (PODC), pp. 253\u2013260 (2012)","DOI":"10.1145\/2332432.2332483"},{"key":"9819_CR26","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/j.tcs.2013.03.002","volume":"509","author":"M Herlihy","year":"2013","unstructured":"Herlihy, M., Rajsbaum, S., Raynal, M.: Power and limits of distributed computing shared memory models. Theor. Comput. Sci. 509, 3\u201324 (2013)","journal-title":"Theor. Comput. Sci."},{"key":"9819_CR27","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Rajsbaum, S., Raynal, M., Stainer, J.: Computing in the presence of concurrent solo executions. In: Proceedings of the 11th Latin American Theoretical Informatics Symposium (LATIN), pp. 214\u2013225 (2014)","DOI":"10.1007\/978-3-642-54423-1_19"},{"issue":"6","key":"9819_CR28","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. J. ACM 46(6), 858\u2013923 (1999)","journal-title":"J. ACM"},{"issue":"3","key":"9819_CR29","doi-asserted-by":"publisher","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."},{"key":"9819_CR30","doi-asserted-by":"crossref","unstructured":"Jayanti, P., Toueg, S.: Wakeup under read\/write atomicity. In: Proceedings of the 4th International Workshop on Distributed Algorithms, pp. 277\u2013288 (1991)","DOI":"10.1007\/3-540-54099-7_19"},{"key":"9819_CR31","doi-asserted-by":"crossref","unstructured":"Junqueira, F.P., Marzullo, K.: Synchronous consensus for dependent process failures. In: Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS), pp. 274\u2013283 (2003)","DOI":"10.1109\/ICDCS.2003.1203476"},{"key":"9819_CR32","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann (1996)"},{"key":"9819_CR33","doi-asserted-by":"crossref","unstructured":"Mendes, H., Tasson, C., Herlihy, M.: Distributed computability in byzantine asynchronous systems. In: Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC), pp. 704\u2013713 (2014)","DOI":"10.1145\/2591796.2591853"},{"issue":"1","key":"9819_CR34","doi-asserted-by":"publisher","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."},{"key":"9819_CR35","doi-asserted-by":"crossref","unstructured":"Ruppert, E.: The anonymous consensus hierarchy and naming problems. In: Proceedings of the 11th International Conference on Principles of Distributed Systems (OPODIS), pp. 386\u2013400 (2007)","DOI":"10.1007\/978-3-540-77096-1_28"},{"key":"9819_CR36","doi-asserted-by":"crossref","unstructured":"Spanier, E.: Algebraic Topology, vol. 55. McGraw-Hill. (1966). (reprinted by Springer-Verlag)","DOI":"10.1007\/978-1-4684-9322-1_5"},{"key":"9819_CR37","doi-asserted-by":"crossref","unstructured":"Yanagisawa, N.: Wait-free solvability of colorless tasks in anonymous shared-memory model. In: Proceedings of the 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 415\u2013429 (2016)","DOI":"10.1007\/978-3-319-49259-9_32"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9819-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9819-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9819-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,5]],"date-time":"2019-10-05T22:01:17Z","timestamp":1570312877000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9819-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,13]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["9819"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9819-0","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,13]]},"assertion":[{"value":"13 November 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}