{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T21:56:51Z","timestamp":1773093411134,"version":"3.50.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"5-6","license":[{"start":{"date-parts":[[2010,6,9]],"date-time":"2010-06-09T00:00:00Z","timestamp":1276041600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2010,8]]},"DOI":"10.1007\/s00446-010-0108-2","type":"journal-article","created":{"date-parts":[[2010,6,8]],"date-time":"2010-06-08T16:29:55Z","timestamp":1276014595000},"page":"287-301","source":"Crossref","is-referenced-by-count":37,"title":["New combinatorial topology bounds for renaming: the lower bound"],"prefix":"10.1007","volume":"22","author":[{"given":"Armando","family":"Casta\u00f1eda","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergio","family":"Rajsbaum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,6,9]]},"reference":[{"issue":"4","key":"108_CR1","doi-asserted-by":"crossref","first-page":"1286","DOI":"10.1137\/S0097539797330689","volume":"31","author":"H. Attiya","year":"2002","unstructured":"Attiya H., Rajsbaum S.: The combinatorial structure of wait-free solvable tasks. SIAM J. Comput. 31(4), 1286\u20131313 (2002)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"108_CR2","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1145\/200836.200869","volume":"42","author":"H. Attiya","year":"1995","unstructured":"Attiya H., Bar-Noy A., Dolev D.: Sharing memory robustly in message-passage systems. J. ACM 42(1), 124\u2013142 (1995)","journal-title":"J. ACM"},{"issue":"3","key":"108_CR3","doi-asserted-by":"crossref","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., Reischuck R.: Renaming in asynchronous environment. J. ACM 37(3), 524\u2013548 (1990)","journal-title":"J. ACM"},{"key":"108_CR4","volume-title":"Distributed Computing: Fundamentals, Simulations and Advanced Topics","author":"H. Attiya","year":"1998","unstructured":"Attiya H., Welch J.: Distributed Computing: Fundamentals, Simulations and Advanced Topics. McGraw-Hill, NY (1998)"},{"key":"108_CR5","doi-asserted-by":"crossref","unstructured":"Borowsky, E., Gafni, E.: Generalized FLP impossibility result for t-resilient asynchronous computations. Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pp. 91\u2013100 (1993)","DOI":"10.1145\/167088.167119"},{"key":"108_CR6","doi-asserted-by":"crossref","unstructured":"Borowsky, E., Gafni, E.: Immediate atomic snapshots and fast renaming. Proceedings of the 12th Annual ACM Symposium on Principles on Distributed Computing, pp. 41\u201351 (1993)","DOI":"10.1145\/164051.164056"},{"key":"108_CR7","doi-asserted-by":"crossref","unstructured":"Borowsky, E., Gafni, E.: A simple algorithmically reasoned characterization of wait-free computations. Proceedings of the 16th Annual ACM Symposium on Principles on Distributed Computing, pp. 189\u2013198 (1997)","DOI":"10.1145\/259380.259439"},{"issue":"3","key":"108_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":"108_CR9","doi-asserted-by":"crossref","unstructured":"Casta\u00f1eda, A., Rajsbaum, S.: New combinatorial topology upper and lower bounds for renaming. Proceedings of the 27th Annual ACM Symposium on Principles on Distributed Computing, pp. 295\u2013304 (2008)","DOI":"10.1145\/1400751.1400791"},{"key":"108_CR10","doi-asserted-by":"crossref","unstructured":"Casta\u00f1eda, A., Rajsbaum, S.: New combinatorial topology upper and lower bounds for renaming: the upper bound. Publicaci\u00f3n Preliminar No. 872 del Instituto de Matem\u00e1ticas, Universidad Nacional Aut\u00f3noma de M\u00e9xico, December 2009. http:\/\/texedores.matem.unam.mx\/publicaciones\/index.php?option=com_remository&Itemid=57&func=fileinfo&id=163 . Preliminary version is in [9]. Submitted for publication","DOI":"10.1145\/1400751.1400791"},{"key":"108_CR11","unstructured":"Casta\u00f1eda, A., Rajsbaum, S.: New combinatorial topology upper and lower bounds for renaming: the lower bound. Publicaci\u00f3n Preliminar No. 873 del Instituto de Matem\u00e1ticas, Universidad Nacional Aut\u00f3noma de M\u00e9xico, April 2010. http:\/\/texedores.matem.unam.mx\/publicaciones\/index.php?option=com_remository&Itemid=57&func=fileinfo&id=167 . Preliminary version is in [9]"},{"issue":"1","key":"108_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(1), 132\u2013158 (1993)","journal-title":"Inf. Comput."},{"key":"108_CR13","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1016\/S0021-9800(67)80063-2","volume":"2","author":"K. Fan","year":"1967","unstructured":"Fan K.: Simplicial maps from an orientable n-pseudomanifold into S m with the octahedral triangulation. J. Combin. Theor. 2, 588\u2013602 (1967)","journal-title":"J. Combin. Theor."},{"key":"108_CR14","doi-asserted-by":"crossref","unstructured":"Gafni, E.: The extended BG-simulation and the characterization of t-resiliency. Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pp. 85\u201392 (2009)","DOI":"10.1145\/1536414.1536428"},{"issue":"14","key":"108_CR15","doi-asserted-by":"crossref","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. 410(14), 1328\u20131335 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"108_CR16","doi-asserted-by":"crossref","unstructured":"Gafni E., Rajsbaum S., Herlihy M.: Subconsensus tasks: renaming is weaker than set agreement. Proceedings of the 20th International Symposium on Distributed Computing, pp. 329\u2013338 (2006)","DOI":"10.1007\/11864219_23"},{"key":"108_CR17","doi-asserted-by":"crossref","unstructured":"Gafni, E., Rajsbaum, S.: Musical benches. Proceedings of the 19th International Symposium on Distributed Computing, pp. 63\u201377 (2005)","DOI":"10.1007\/11561927_7"},{"issue":"3","key":"108_CR18","doi-asserted-by":"crossref","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."},{"key":"108_CR19","doi-asserted-by":"crossref","unstructured":"Goubault, E.: Proceedings of the Workshops on Geometric and Topological Methods in Concurrency Theory (GETCO 2004, 2005, 2006). Electronic Notes in Theoretical Computer Science 230, pp. 1\u20132 (2009)","DOI":"10.1016\/j.entcs.2009.02.013"},{"issue":"6\u20137","key":"108_CR20","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1016\/j.tcs.2008.10.002","volume":"410","author":"R. Guerraoui","year":"2009","unstructured":"Guerraoui R., Herlihy M., Pochon B.: A topological treatment of early-deciding set-agreement. Theor. Comput. Sci. 410(6\u20137), 570\u2013580 (2009)","journal-title":"Theor. Comput. Sci."},{"issue":"5","key":"108_CR21","doi-asserted-by":"crossref","first-page":"1215","DOI":"10.1137\/S0097539798337224","volume":"33","author":"J. Havlicek","year":"2004","unstructured":"Havlicek J.: A note on the homotopy type of wait-free atomic snapshot protocol complexes. SIAM J. Comput. 33(5), 1215\u20131222 (2004)","journal-title":"SIAM J. Comput."},{"key":"108_CR22","unstructured":"Henle, M.: A combinatorial introduction to topology. Dover 1994"},{"issue":"1","key":"108_CR23","doi-asserted-by":"crossref","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."},{"issue":"4","key":"108_CR24","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1017\/S0960129500003170","volume":"10","author":"M. Herlihy","year":"2000","unstructured":"Herlihy M., Rajsbaum S.: Algebraic spans. Math. Struct. Comput. Sci. 10(4), 549\u2013573 (2000)","journal-title":"Math. Struct. Comput. Sci."},{"issue":"6","key":"108_CR25","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"},{"key":"108_CR26","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks (extended abstract). Proceedings of the 29th ACM Symposium on the Theory of Computing, pp. 589\u2013598 (1997)","DOI":"10.1145\/258533.258652"},{"key":"108_CR27","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Shavit, N.: The asynchronous computability theorem for t-resilient Tasks. Proceedings of the 25th ACM Symposium on the Theory of Computing, pp. 111\u2013120 (1993)","DOI":"10.1145\/167088.167125"},{"issue":"2","key":"108_CR28","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1137\/S0097539701397412","volume":"36","author":"G. Hoest","year":"2006","unstructured":"Hoest G., Shavit N.: Toward a topological characterization of asynchronous complexity. SIAM J. Comput. 36(2), 457\u2013497 (2006)","journal-title":"SIAM J. Comput."},{"key":"108_CR29","doi-asserted-by":"crossref","unstructured":"Most\u00e9faoui, A., Rajsbaum, S., Raynal. M., Roy, M.: Condition-based protocols for set agreement problems. Proceedings of the 16th International Symposium on Distributed Computing, pp. 48\u201362 (2002)","DOI":"10.1007\/3-540-36108-1_4"},{"key":"108_CR30","volume-title":"Number Theory. An Introduction","author":"D. Redmond","year":"1996","unstructured":"Redmond D.: Number Theory. An Introduction. Mercel Dekker, New York (1996)"},{"issue":"5","key":"108_CR31","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":"108_CR32","unstructured":"Workshop on Algebraic Topological Methods in Computer Science, Paris, France 7\u201311 2008. http:\/\/www.lix.polytechnique.fr\/~sanjeevi\/atmcs\/"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0108-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-010-0108-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0108-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,27]],"date-time":"2024-03-27T11:45:48Z","timestamp":1711539948000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-010-0108-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,9]]},"references-count":32,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2010,8]]}},"alternative-id":["108"],"URL":"https:\/\/doi.org\/10.1007\/s00446-010-0108-2","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,9]]}}}