{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:15Z","timestamp":1740109275073,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2022,3,24]],"date-time":"2022-03-24T00:00:00Z","timestamp":1648080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,3,24]],"date-time":"2022-03-24T00:00:00Z","timestamp":1648080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"ISF","award":["724\/15"],"award-info":[{"award-number":["724\/15"]}]},{"name":"Open University of Israel\u2019s Research Fund"},{"name":"Lynn and William Frankel Center for Computer Science"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00446-022-00423-z","type":"journal-article","created":{"date-parts":[[2022,3,25]],"date-time":"2022-03-25T05:03:08Z","timestamp":1648184588000},"page":"455-473","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Distributed backup placement"],"prefix":"10.1007","volume":"35","author":[{"given":"Leonid","family":"Barenboim","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8831-5423","authenticated-orcid":false,"given":"Gal","family":"Oren","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,3,24]]},"reference":[{"key":"423_CR1","unstructured":"Assadi, S., Solomon, S.: When algorithms for maximal independent set and maximal matching run in sublinear time. In: 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)"},{"issue":"5\u20136","key":"423_CR2","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s00446-009-0088-2","volume":"22","author":"L Barenboim","year":"2010","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash\u2013Williams decomposition. Distrib. Comput. 22(5\u20136), 363\u2013379 (2010)","journal-title":"Distrib. Comput."},{"issue":"5","key":"423_CR3","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1145\/2027216.2027221","volume":"58","author":"L Barenboim","year":"2011","unstructured":"Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. JACM 58(5), 23 (2011)","journal-title":"JACM"},{"issue":"1","key":"423_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-031-02009-4","volume":"4","author":"L Barenboim","year":"2013","unstructured":"Barenboim, L., Elkin, M.: Distributed graph coloring: fundamentals and recent developments. Synth. Lect. Distrib. Comput. Theory 4(1), 1\u2013171 (2013)","journal-title":"Synth. Lect. Distrib. Comput. Theory"},{"key":"423_CR5","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M., Maimon, T.: Deterministic distributed ($$\\text{Delta}$$ + $$o(\\text{ Delta})$$)-edge-coloring, and vertex-coloring of graphs with bounded diversity. In: Proceedings of the ACM Symposium on Principles of Distributed Computing. ACM, pp. 175\u2013184 (2017)","DOI":"10.1145\/3087801.3087812"},{"key":"423_CR6","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Maimon, T.: Distributed symmetry breaking in graphs with bounded diversity. In: 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS). IEEE, pp. 723\u2013732 (2018)","DOI":"10.1109\/IPDPS.2018.00082"},{"key":"423_CR7","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Oren, G.: Distributed backup placement in one round and its applications to maximum matching approximation and self-stabilization. In: Symposium on Simplicity in Algorithms, the Symposium on Discrete Algorithms. ACM-SIAM, pp. 99\u2013105 (2020)","DOI":"10.1137\/1.9781611976014.14"},{"key":"423_CR8","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Oren, G.: Fast distributed backup placement in sparse and dense networks. In: Symposium on Algorithmic Principles of Computer Systems (APoCS), ACM-SIAM Symposium on Discrete Algorithms. ACM-SIAM (2020)","DOI":"10.1137\/1.9781611976021.7"},{"key":"423_CR9","doi-asserted-by":"crossref","unstructured":"Brandt, S., Keller, B., Rybicki, J., Suomela, J., Uitto, J.: Efficient load-balancing through distributed token dropping. arXiv preprint arXiv:2005.07761 (2020)","DOI":"10.1145\/3409964.3461785"},{"key":"423_CR10","doi-asserted-by":"crossref","unstructured":"Czygrinow, A., Han\u0107kowiak, M., Szyma\u0144ska, E., Wawrzyniak, W.: Distributed 2-approximation algorithm for the semi-matching problem. In: International Symposium on Distributed Computing. Springer, pp. 210\u2013222 (2012)","DOI":"10.1007\/978-3-642-33651-5_15"},{"key":"423_CR11","doi-asserted-by":"crossref","unstructured":"Dijkstra, E.W.: Self-stabilizing systems in spite of distributed control. Association for Computing Machinery. Commun. ACM 17(11), 643\u2013644 (1974)","DOI":"10.1145\/361179.361202"},{"key":"423_CR12","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/6156.001.0001","volume-title":"Self-Stabilization","author":"S Dolev","year":"2000","unstructured":"Dolev, S.: Self-Stabilization. MIT Press, Cambridge (2000)"},{"key":"423_CR13","unstructured":"Fischer, M.: Improved deterministic distributed matching via rounding. In: 31st International Symposium on Distributed Computing (DISC 2017), vol.\u00a091. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, p.\u00a017 (2017)"},{"key":"423_CR14","doi-asserted-by":"crossref","unstructured":"Fischer, M., Ghaffari, M., Kuhn, F.: Deterministic distributed edge-coloring via hypergraph maximal matching. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, pp. 180\u2013191 (2017)","DOI":"10.1109\/FOCS.2017.25"},{"key":"423_CR15","doi-asserted-by":"crossref","unstructured":"Gfeller, B., Vicari, E.: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing. ACM, pp. 53\u201360 (2007)","DOI":"10.1145\/1281100.1281111"},{"key":"423_CR16","doi-asserted-by":"crossref","unstructured":"Halld\u00f3rsson, M.M., K\u00f6hler, S., Patt-Shamir, B., Rawitz, D.: Distributed backup placement in networks. In: Proceedings of the 27th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, pp. 274\u2013283 (2015)","DOI":"10.1145\/2755573.2755583"},{"issue":"2","key":"423_CR17","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s00446-017-0299-x","volume":"31","author":"MM Halld\u00f3rsson","year":"2018","unstructured":"Halld\u00f3rsson, M.M., K\u00f6hler, S., Patt-Shamir, B., Rawitz, D.: Distributed backup placement in networks. Distrib. Comput. 31(2), 83\u201398 (2018)","journal-title":"Distrib. Comput."},{"key":"423_CR18","doi-asserted-by":"crossref","unstructured":"Kuhn, F.: Faster deterministic distributed coloring through recursive list coloring. arXiv preprint arXiv:1907.03797 (2019)","DOI":"10.1137\/1.9781611975994.76"},{"key":"423_CR19","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing. ACM, pp. 300\u2013309 (2004)","DOI":"10.1145\/1011767.1011811"},{"key":"423_CR20","doi-asserted-by":"crossref","unstructured":"Kunne, S., Cohen, J., Pilard, L.: Self-stabilization and byzantine tolerance for maximal matching. In: International Symposium on Stabilizing, Safety, and Security of Distributed Systems. Springer, pp. 80\u201395 (2018)","DOI":"10.1007\/978-3-030-03232-6_6"},{"key":"423_CR21","unstructured":"Langley, Z., Bernstein, A., Assadi, S.: Improved bounds for distributed load balancing. In: 34th International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2020)"},{"key":"423_CR22","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Oswald, Y.A., Wattenhofer, R.: What can be approximated locally?: case study: dominating sets in planar graphs. In: Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures. ACM, pp. 46\u201354 (2008)","DOI":"10.1145\/1378533.1378540"},{"issue":"1","key":"423_CR23","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)","journal-title":"SIAM J. Comput."},{"key":"423_CR24","doi-asserted-by":"crossref","unstructured":"Milenkovi\u0107, L., Solomon, S.: A unified sparsification approach for matching problems in graphs of bounded neighborhood independence. In: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, pp. 395\u2013406 (2020)","DOI":"10.1145\/3350755.3400248"},{"issue":"1","key":"423_CR25","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"1","author":"CSJ Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.J.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 1(1), 445\u2013450 (1961)","journal-title":"J. Lond. Math. Soc."},{"issue":"1","key":"423_CR26","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","volume":"1","author":"CSJ Nash-Williams","year":"1964","unstructured":"Nash-Williams, C.S.J.: Decomposition of finite graphs into forests. J. Lond. Math. Soc. 1(1), 12 (1964)","journal-title":"J. Lond. Math. Soc."},{"key":"423_CR27","unstructured":"Oren, G.: Distributed management algorithms for heterogeneous computing systems and networks (2020)"},{"key":"423_CR28","doi-asserted-by":"crossref","unstructured":"Oren, G., Barenboim, L.: Backup placement in wsns in the network management distributed setting. In: 2021 IEEE 41st International Conference on Distributed Computing Systems Workshops (ICDCSW), pp. 49\u201354 (2021)","DOI":"10.1109\/ICDCSW53096.2021.00015"},{"key":"423_CR29","doi-asserted-by":"crossref","unstructured":"Oren, G., Barenboim, L.: Distributed backup k-placement and applications to virtual memory in wireless networks. In: Adjunct Proceedings of the 2021 International Conference on Distributed Computing and Networking, pp. 139\u2013144 (2021)","DOI":"10.1145\/3427477.3429466"},{"key":"423_CR30","doi-asserted-by":"crossref","unstructured":"Oren, G., Barenboim, L., Levin, H.: Adaptive distributed hierarchical sensing algorithm for reduction of wireless sensor network cluster-heads energy consumption. In: 2017 13th International Wireless Communications and Mobile Computing Conference (IWCMC). IEEE, pp. 980\u2013986 (2017)","DOI":"10.1109\/IWCMC.2017.7986419"},{"key":"423_CR31","doi-asserted-by":"crossref","unstructured":"Oren, G., Barenboim, L., Levin, H.: Load-balancing adaptive clustering refinement algorithm for wireless sensor network clusters. In: International Conference on Wired\/Wireless Internet Communication. Springer, pp. 157\u2013173 (2017)","DOI":"10.1007\/978-3-319-61382-6_13"},{"key":"423_CR32","doi-asserted-by":"crossref","unstructured":"Oren, G., Barenboim, L., Levin, H.: Distributed fault-tolerant backup-placement in overloaded wireless sensor networks. In: International Conference on Broadband Communications, Networks and Systems. Springer, pp. 212\u2013224 (2018)","DOI":"10.1007\/978-3-030-05195-2_21"},{"issue":"2","key":"423_CR33","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/PL00008932","volume":"14","author":"A Panconesi","year":"2001","unstructured":"Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14(2), 97\u2013100 (2001)","journal-title":"Distrib. Comput."},{"issue":"2","key":"423_CR34","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/jagm.1996.0017","volume":"20","author":"A Panconesi","year":"1996","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 356\u2013374 (1996)","journal-title":"J. Algorithms"},{"key":"423_CR35","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1002\/9780470396360.ch4","volume":"62","author":"S Schmid","year":"2008","unstructured":"Schmid, S., Wattenhofer, R., Boukerche, A.: Modeling sensor networks. Algorithms Protoc. Wirel. Sens. Netw. 62, 77 (2008)","journal-title":"Algorithms Protoc. Wirel. Sens. Netw."},{"key":"423_CR36","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A log-star distributed maximal independent set algorithm for growth-bounded graphs. In: Proceedings of the Twenty-Seventh ACM Symposium on Principles of Distributed Computing. ACM, pp. 35\u201344 (2008)","DOI":"10.1145\/1400751.1400758"},{"key":"423_CR37","doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: Coloring unstructured wireless multi-hop networks. In: Proceedings of the 28th ACM Symposium on Principles of Distributed Computing. ACM, pp. 210\u2013219 (2009)","DOI":"10.1145\/1582716.1582751"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00423-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-022-00423-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00423-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,9]],"date-time":"2022-09-09T07:11:39Z","timestamp":1662707499000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-022-00423-z"}},"subtitle":["for networks of bounded neighborhood independence and networks of bounded arboricity"],"short-title":[],"issued":{"date-parts":[[2022,3,24]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["423"],"URL":"https:\/\/doi.org\/10.1007\/s00446-022-00423-z","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2022,3,24]]},"assertion":[{"value":"9 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}