{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:46:21Z","timestamp":1782971181511,"version":"3.54.5"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2020,4,18]],"date-time":"2020-04-18T00:00:00Z","timestamp":1587168000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,4,18]],"date-time":"2020-04-18T00:00:00Z","timestamp":1587168000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"publisher","award":["285721"],"award-info":[{"award-number":["285721"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2021,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The landscape of the distributed time complexity is nowadays well-understood for subpolynomial complexities. When we look at deterministic algorithms in the <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {LOCAL}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>LOCAL<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> model and locally checkable problems (<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {LCL}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>LCL<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>s) in bounded-degree graphs, the following picture emerges:<jats:list list-type=\"bullet\">\n                <jats:list-item>\n                  <jats:p>There are lots of problems with time complexities of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varTheta (\\log ^* n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>\u0398<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:msup>\n                          <mml:mo>log<\/mml:mo>\n                          <mml:mo>\u2217<\/mml:mo>\n                        <\/mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula> or <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varTheta (\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>\u0398<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>\n                <\/jats:list-item>\n                <jats:list-item>\n                  <jats:p>It is not possible to have a problem with complexity between <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega (\\log ^* n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>\u03c9<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:msup>\n                          <mml:mo>log<\/mml:mo>\n                          <mml:mo>\u2217<\/mml:mo>\n                        <\/mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$o(\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>o<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>\n                <\/jats:list-item>\n                <jats:list-item>\n                  <jats:p>In <jats:italic>general graphs<\/jats:italic>, we can construct <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {LCL}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>LCL<\/mml:mi>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula> problems with infinitely many complexities between <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega (\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>\u03c9<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:mo>log<\/mml:mo>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$n^{o(1)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:msup>\n                        <mml:mi>n<\/mml:mi>\n                        <mml:mrow>\n                          <mml:mi>o<\/mml:mi>\n                          <mml:mo>(<\/mml:mo>\n                          <mml:mn>1<\/mml:mn>\n                          <mml:mo>)<\/mml:mo>\n                        <\/mml:mrow>\n                      <\/mml:msup>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>\n                <\/jats:list-item>\n                <jats:list-item>\n                  <jats:p>In <jats:italic>trees<\/jats:italic>, problems with such complexities do not exist.<\/jats:p>\n                <\/jats:list-item>\n              <\/jats:list> However, the high end of the complexity spectrum was left open by prior work. In general graphs there are <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {LCL}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>LCL<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> problems with complexities of the form <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varTheta (n^\\alpha )$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mi>\u03b1<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> for any rational <jats:inline-formula><jats:alternatives><jats:tex-math>$$0 &lt; \\alpha \\le 1\/2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mn>0<\/mml:mn>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mi>\u03b1<\/mml:mi>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                    <mml:mo>\/<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, while for trees only complexities of the form <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varTheta (n^{1\/k})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0398<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mn>1<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mi>k<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are known. No <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {LCL}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>LCL<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> problem with complexity between <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega (\\sqrt{n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:italic>o<\/jats:italic>(<jats:italic>n<\/jats:italic>) is known, and neither are there results that would show that such problems do not exist. We show that:<jats:list list-type=\"bullet\">\n                <jats:list-item>\n                  <jats:p>In <jats:italic>general graphs<\/jats:italic>, we can construct <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {LCL}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mi>LCL<\/mml:mi>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula> problems with infinitely many complexities between <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\omega (\\sqrt{n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                      <mml:mrow>\n                        <mml:mi>\u03c9<\/mml:mi>\n                        <mml:mo>(<\/mml:mo>\n                        <mml:msqrt>\n                          <mml:mi>n<\/mml:mi>\n                        <\/mml:msqrt>\n                        <mml:mo>)<\/mml:mo>\n                      <\/mml:mrow>\n                    <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:italic>o<\/jats:italic>(<jats:italic>n<\/jats:italic>).<\/jats:p>\n                <\/jats:list-item>\n                <jats:list-item>\n                  <jats:p>In <jats:italic>trees<\/jats:italic>, problems with such complexities do not exist.<\/jats:p>\n                <\/jats:list-item>\n              <\/jats:list> Put otherwise, we show that any <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathsf {LCL}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>LCL<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with a complexity <jats:italic>o<\/jats:italic>(<jats:italic>n<\/jats:italic>) can be solved in time <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in trees, while the same is not true in general graphs.<\/jats:p>","DOI":"10.1007\/s00446-020-00375-2","type":"journal-article","created":{"date-parts":[[2020,4,18]],"date-time":"2020-04-18T09:02:29Z","timestamp":1587200549000},"page":"259-281","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Almost global problems in the LOCAL model"],"prefix":"10.1007","volume":"34","author":[{"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Brandt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,4,18]]},"reference":[{"key":"375_CR1","doi-asserted-by":"publisher","unstructured":"Balliu, A., Brandt, S., Olivetti, D., Suomela, J.: Almost global problems in the LOCAL model. In: Proceedings 32nd International Symposium on Distributed Computing (DISC 2018), Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl\u2013Leibniz\u2013Zentrum f\u00fcr Informatik (2018). https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.9","DOI":"10.4230\/LIPIcs.DISC.2018.9"},{"key":"375_CR2","doi-asserted-by":"publisher","unstructured":"Balliu, A., Hirvonen, J., Korhonen, J.H., Lempi\u00e4inen, T., Olivetti, D., Suomela, J.: New classes of distributed time complexity. In: Proceedings 50th ACM Symposium on Theory of Computing (STOC 2018), pp. 1307\u20131318. ACM Press (2018). https:\/\/doi.org\/10.1145\/3188745.3188860","DOI":"10.1145\/3188745.3188860"},{"issue":"5","key":"375_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2979675","volume":"63","author":"L Barenboim","year":"2016","unstructured":"Barenboim, L.: Deterministic ($$\\varDelta $$+1)-coloring in sublinear (in $$\\varDelta $$) time in static, dynamic, and faulty networks. J. ACM 63(5), 1\u201322 (2016). https:\/\/doi.org\/10.1145\/2979675","journal-title":"J. ACM"},{"issue":"1","key":"375_CR4","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1137\/12088848X","volume":"43","author":"L Barenboim","year":"2014","unstructured":"Barenboim, L., Elkin, M., Kuhn, F.: Distributed ($$\\varDelta $$+1)-coloring in linear (in $$\\varDelta $$) time. SIAM J. Comput. 43(1), 72\u201395 (2014). https:\/\/doi.org\/10.1137\/12088848X","journal-title":"SIAM J. Comput."},{"key":"375_CR5","doi-asserted-by":"publisher","unstructured":"Brandt, S., Fischer, O., Hirvonen, J., Keller, B., Lempi\u00e4inen, T., Rybicki, J., Suomela, J., Uitto, J.: A lower bound for the distributed Lov\u00e1sz local lemma. In: Proceedings 48th ACM Symposium on Theory of Computing (STOC 2016), pp. 479\u2013488. ACM Press (2016). https:\/\/doi.org\/10.1145\/2897518.2897570","DOI":"10.1145\/2897518.2897570"},{"key":"375_CR6","doi-asserted-by":"publisher","unstructured":"Brandt, S., Hirvonen, J., Korhonen, J.H., Lempi\u00e4inen, T., \u00d6sterg\u00e5rd, P.R.J., Purcell, C., Rybicki, J., Suomela, J., Uzna\u0144ski, P.: LCL problems on grids. In: Proceedings 36th ACM Symposium on Principles of Distributed Computing (PODC 2017), pp. 101\u2013110. ACM Press (2017). https:\/\/doi.org\/10.1145\/3087801.3087833","DOI":"10.1145\/3087801.3087833"},{"issue":"1","key":"375_CR7","doi-asserted-by":"publisher","first-page":"8:1","DOI":"10.1145\/3365004","volume":"16","author":"YJ Chang","year":"2020","unstructured":"Chang, Y.J., He, Q., Li, W., Pettie, S., Uitto, J.: Distributed edge coloring and a special case of the constructive Lov\u00e1sz local lemma. ACM Trans. Algorithms 16(1), 8:1\u20138:51 (2020). https:\/\/doi.org\/10.1145\/3365004","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"375_CR8","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/17M1117537","volume":"48","author":"YJ Chang","year":"2019","unstructured":"Chang, Y.J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the LOCAL model. SIAM J. Comput. 48(1), 122\u2013143 (2019). https:\/\/doi.org\/10.1137\/17M1117537","journal-title":"SIAM J. Comput."},{"issue":"1","key":"375_CR9","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1137\/17M1157957","volume":"48","author":"YJ Chang","year":"2019","unstructured":"Chang, Y.J., Pettie, S.: A time hierarchy theorem for the LOCAL model. SIAM J. Comput. 48(1), 33\u201369 (2019). https:\/\/doi.org\/10.1137\/17M1157957","journal-title":"SIAM J. Comput."},{"issue":"1","key":"375_CR10","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inf. Control 70(1), 32\u201353 (1986). https:\/\/doi.org\/10.1016\/S0019-9958(86)80023-7","journal-title":"Inf. Control"},{"key":"375_CR11","doi-asserted-by":"publisher","unstructured":"Fraigniaud, P., Heinrich, M., Kosowski, A.: Local conflict coloring. In: Proceedings 57th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2016), pp. 625\u2013634. IEEE (2016). https:\/\/doi.org\/10.1109\/FOCS.2016.73","DOI":"10.1109\/FOCS.2016.73"},{"key":"375_CR12","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Harris, D.G., Kuhn, F.: On derandomizing local distributed algorithms. In: Proceedings 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2018), pp. 662\u2013673. IEEE (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00069","DOI":"10.1109\/FOCS.2018.00069"},{"key":"375_CR13","doi-asserted-by":"publisher","unstructured":"Ghaffari, M., Su, H.H.: Distributed Degree Splitting, Edge Coloring, and Orientations. In: Proceedings 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp. 2505\u20132523. Society for Industrial and Applied Mathematics (2017). https:\/\/doi.org\/10.1137\/1.9781611974782.166","DOI":"10.1137\/1.9781611974782.166"},{"key":"375_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2016.v012a019","volume":"12","author":"M G\u00f6\u00f6s","year":"2016","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs in distributed computing. Theory Comput. 12, 1\u201333 (2016). https:\/\/doi.org\/10.4086\/toc.2016.v012a019","journal-title":"Theory Comput."},{"issue":"117","key":"375_CR15","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","volume":"117","author":"J Hartmanis","year":"1965","unstructured":"Hartmanis, J., Stearns, R.E.: On the computational complexity of algorithms. Trans. Am. Math. Soc. 117(117), 285\u2013285 (1965). https:\/\/doi.org\/10.1090\/S0002-9947-1965-0170805-7","journal-title":"Trans. Am. Math. Soc."},{"key":"375_CR16","volume-title":"Introduction to Automata Theory, Languages and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages and Computation. Addison-Wesley, Boston (1979)"},{"issue":"1","key":"375_CR17","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":"375_CR18","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995). https:\/\/doi.org\/10.1137\/S0097539793254571","journal-title":"SIAM J. Comput."},{"issue":"2","key":"375_CR19","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. Distributed Comput. 14(2), 97\u2013100 (2001). https:\/\/doi.org\/10.1007\/PL00008932","journal-title":"Distributed Comput."},{"issue":"2","key":"375_CR20","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01200759","volume":"15","author":"A Panconesi","year":"1995","unstructured":"Panconesi, A., Srinivasan, A.: The local nature of $$\\varDelta $$-coloring and its algorithmic applications. Combinatorica 15(2), 255\u2013280 (1995). https:\/\/doi.org\/10.1007\/BF01200759","journal-title":"Combinatorica"},{"key":"375_CR21","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000). https:\/\/doi.org\/10.1137\/1.9780898719772"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00375-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-020-00375-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00375-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T05:04:32Z","timestamp":1626843872000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-020-00375-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,18]]},"references-count":21,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["375"],"URL":"https:\/\/doi.org\/10.1007\/s00446-020-00375-2","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,18]]},"assertion":[{"value":"15 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 March 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}