{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T23:00:12Z","timestamp":1740178812266,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T00:00:00Z","timestamp":1719792000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,7,1]],"date-time":"2024-07-01T00:00:00Z","timestamp":1719792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"ANR","award":["20-CE48-0006"],"award-info":[{"award-number":["20-CE48-0006"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Appl. and Comput. Topology"],"published-print":{"date-parts":[[2024,9]]},"DOI":"10.1007\/s41468-024-00185-6","type":"journal-article","created":{"date-parts":[[2024,7,2]],"date-time":"2024-07-02T00:02:20Z","timestamp":1719878540000},"page":"1069-1098","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The topology of local computing in networks"],"prefix":"10.1007","volume":"8","author":[{"given":"Pierre","family":"Fraigniaud","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6629-8335","authenticated-orcid":false,"given":"Ami","family":"Paz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,1]]},"reference":[{"issue":"1","key":"185_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/16M1081439","volume":"48","author":"H Attiya","year":"2019","unstructured":"Attiya, H., Casta\u00f1eda, A., Herlihy, M., Paz, A.: Bounds on the step and namespace complexity of renaming. SIAM J. Comput. 48(1), 1\u201332 (2019). https:\/\/doi.org\/10.1137\/16M1081439","journal-title":"SIAM J. Comput."},{"key":"185_CR2","doi-asserted-by":"crossref","unstructured":"Balliu., A., Brandt., S., Hirvonen., J., Olivetti., D., Rabie., M., Suomela, J.: Lower bounds for maximal matchings and maximal independent sets. In: 60th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 481\u2013497 (2019)","DOI":"10.1109\/FOCS.2019.00037"},{"issue":"3","key":"185_CR3","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/PL00008933","volume":"14","author":"E Borowsky","year":"2001","unstructured":"Borowsky, E., Gafni, E., Lynch, N.A., Rajsbaum, S.: The BG distributed simulation algorithm. Distrib. Comput. 14(3), 127\u2013146 (2001). https:\/\/doi.org\/10.1007\/PL00008933","journal-title":"Distrib. Comput."},{"key":"185_CR4","doi-asserted-by":"publisher","unstructured":"Brandt, S.: An automatic speedup theorem for distributed problems. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 379\u2013388, (2019). https:\/\/doi.org\/10.1145\/3293611.3331611","DOI":"10.1145\/3293611.3331611"},{"issue":"5\u20136","key":"185_CR5","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/s00446-010-0108-2","volume":"22","author":"A Casta\u00f1eda","year":"2010","unstructured":"Casta\u00f1eda, A., Rajsbaum, S.: New combinatorial topology bounds for renaming: the lower bound. Distrib. Comput. 22(5\u20136), 287\u2013301 (2010). https:\/\/doi.org\/10.1007\/s00446-010-0108-2","journal-title":"Distrib. Comput."},{"issue":"1","key":"185_CR6","doi-asserted-by":"publisher","first-page":"3:1","DOI":"10.1145\/2108242.2108245","volume":"59","author":"A Casta\u00f1eda","year":"2012","unstructured":"Casta\u00f1eda, A., Rajsbaum, S.: New combinatorial topology bounds for renaming: the upper bound. J. ACM 59(1), 3:1-3:49 (2012). https:\/\/doi.org\/10.1145\/2108242.2108245","journal-title":"J. ACM"},{"key":"185_CR7","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/j.tcs.2020.10.012","volume":"849","author":"A Casta\u00f1eda","year":"2021","unstructured":"Casta\u00f1eda, A., Fraigniaud, P., Paz, A., Rajsbaum, S., Roy, M., Travers, C.: A topological perspective on distributed network algorithms. Theor. Comput. Sci. 849, 121\u2013137 (2021). https:\/\/doi.org\/10.1016\/j.tcs.2020.10.012","journal-title":"Theor. Comput. Sci."},{"key":"185_CR8","volume-title":"Eric Goubault","author":"L Fajstrup","year":"2016","unstructured":"Fajstrup, L.: Eric Goubault. Samuel Mimram, and Martin Raussen. Directed Algebraic Topology and Concurrency. Springer, Emmanuel Haucourt (2016)"},{"issue":"2","key":"185_CR9","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.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374\u2013382 (1985). https:\/\/doi.org\/10.1145\/3149.214121","journal-title":"J. ACM"},{"key":"185_CR10","doi-asserted-by":"publisher","unstructured":"Fraigniaud, P., Paz, A., Rajsbaum, S.: A speedup theorem for asynchronous computation with applications to consensus and approximate agreement. In: PODC, pp. 460\u2013470. ACM (2022). https:\/\/doi.org\/10.1145\/3519270.3538422","DOI":"10.1145\/3519270.3538422"},{"issue":"4","key":"185_CR11","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s00446-018-0328-4","volume":"31","author":"\u00c9 Goubault","year":"2018","unstructured":"Goubault, \u00c9., Mimram, S., Tasson, C.: Geometric and combinatorial views on asynchronous computability. Distrib. Comput. 31(4), 289\u2013316 (2018). https:\/\/doi.org\/10.1007\/s00446-018-0328-4","journal-title":"Distrib. Comput."},{"key":"185_CR12","unstructured":"Graham, R.L., Rothschild, B.L., Spencer, J.H., Solymosi, J.: Ramsey Theory. John Wiley and Sons (2015)"},{"key":"185_CR13","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Kozlov, D.N., Rajsbaum, S.: Distributed computing through combinatorial topology. Morgan Kaufmann (2013). URL: https:\/\/store.elsevier.com\/product.jsp?isbn=9780124045781","DOI":"10.1016\/B978-0-12-404578-1.00003-6"},{"key":"185_CR14","doi-asserted-by":"crossref","unstructured":"Herlihy, M., Rajsbaum, S., Tuttle, M.R.: Unifying synchronous and asynchronous message-passing models. In: PODC, pp. 133\u2013142. ACM (1998)","DOI":"10.1145\/277697.277722"},{"key":"185_CR15","doi-asserted-by":"publisher","unstructured":"Herlihy, M., Rajsbaum, S.: Simulations and reductions for colorless tasks. In: PODC, pp. 253\u2013260. ACM (2012). https:\/\/doi.org\/10.1145\/2332432.2332483","DOI":"10.1145\/2332432.2332483"},{"key":"185_CR16","doi-asserted-by":"publisher","unstructured":"Herlihy, M., Rajsbaum, S.: The decidability of distributed decision tasks. In: STOC, pp. 589\u2013598. ACM (1997). https:\/\/doi.org\/10.1145\/258533.258652","DOI":"10.1145\/258533.258652"},{"issue":"6","key":"185_CR17","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). https:\/\/doi.org\/10.1145\/331524.331529","journal-title":"J. ACM"},{"issue":"2","key":"185_CR18","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1137\/S0097539701397412","journal-title":"SIAM J. Comput."},{"key":"185_CR19","doi-asserted-by":"publisher","unstructured":"Laurinharju, J., Suomela, J.: Brief announcement: Linial\u2019s lower bound made easy. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 377\u2013378 (2014). https:\/\/doi.org\/10.1145\/2611462.2611505","DOI":"10.1145\/2611462.2611505"},{"issue":"1","key":"185_CR20","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992). https:\/\/doi.org\/10.1137\/0221015","journal-title":"SIAM J. Comput."},{"issue":"6","key":"185_CR21","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.J.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995). https:\/\/doi.org\/10.1137\/S0097539793254571","journal-title":"SIAM J. Comput."},{"key":"185_CR22","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM (2001)","DOI":"10.1137\/1.9780898719772"},{"issue":"5","key":"185_CR23","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1137\/S0097539796307698","journal-title":"SIAM J. Comput."},{"issue":"2","key":"185_CR24","doi-asserted-by":"publisher","first-page":"24:1","DOI":"10.1145\/2431211.2431223","volume":"45","author":"J Suomela","year":"2013","unstructured":"Suomela, J.: Survey of local algorithms. ACM Comput. Surv. 45(2), 24:1-24:40 (2013). https:\/\/doi.org\/10.1145\/2431211.2431223","journal-title":"ACM Comput. Surv."}],"container-title":["Journal of Applied and Computational Topology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-024-00185-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41468-024-00185-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41468-024-00185-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,8]],"date-time":"2024-10-08T12:08:34Z","timestamp":1728389314000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41468-024-00185-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,1]]},"references-count":24,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,9]]}},"alternative-id":["185"],"URL":"https:\/\/doi.org\/10.1007\/s41468-024-00185-6","relation":{},"ISSN":["2367-1726","2367-1734"],"issn-type":[{"type":"print","value":"2367-1726"},{"type":"electronic","value":"2367-1734"}],"subject":[],"published":{"date-parts":[[2024,7,1]]},"assertion":[{"value":"31 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 March 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 May 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no Conflict of interest to state.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"A preliminary version of this work was presented in ICALP 2020.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Related version"}}]}}