{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,29]],"date-time":"2026-05-29T16:55:05Z","timestamp":1780073705510,"version":"3.54.0"},"reference-count":53,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,2,13]],"date-time":"2018-02-13T00:00:00Z","timestamp":1518480000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["PBEZP2-134424 \/ 1"],"award-info":[{"award-number":["PBEZP2-134424 \/ 1"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Swiss Society of Friends of the Weizmann Institute of Science"},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["Le 3107\/1- 1"],"award-info":[{"award-number":["Le 3107\/1- 1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["894\/09"],"award-info":[{"award-number":["894\/09"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100006245","name":"Ministry of Science and Technology, Israel","doi-asserted-by":"publisher","award":["infrastructure grant"],"award-info":[{"award-number":["infrastructure grant"]}],"id":[{"id":"10.13039\/501100006245","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006461","name":"Citi Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006461","id-type":"DOI","asserted-by":"publisher"}]},{"name":"I-CORE program of the Israel PBC and ISF","award":["4\/11"],"award-info":[{"award-number":["4\/11"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1444\/14"],"award-info":[{"award-number":["1444\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00446-018-0326-6","type":"journal-article","created":{"date-parts":[[2018,2,13]],"date-time":"2018-02-13T11:21:03Z","timestamp":1518520863000},"page":"133-157","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Distributed distance computation and routing with small messages"],"prefix":"10.1007","volume":"32","author":[{"given":"Christoph","family":"Lenzen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2018,2,13]]},"reference":[{"key":"326_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Censor-Hillel, K., Khoury, S.: Near-linear lower bounds for distributed distance computations, even in sparse networks. In: Proceedings of the International Symposium on Distributed Computing (DISC), pp. 29\u201342 (2016). https:\/\/doi.org\/10.1007\/978-3-662-53426-7_3","DOI":"10.1007\/978-3-662-53426-7_3"},{"key":"326_CR2","doi-asserted-by":"publisher","first-page":"710","DOI":"10.1109\/12.144623","volume":"41","author":"J Antonio","year":"1992","unstructured":"Antonio, J., Huang, G., Tsai, W.: A fast distributed shortest path algorithm for a class of hierarchically clustered data networks. IEEE Trans. Comput. 41, 710\u2013724 (1992)","journal-title":"IEEE Trans. Comput."},{"key":"326_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Bar-Noy, A., Linial, N., Peleg, D.: Compact distributed data structures for adaptive network routing. In: Proceedings of the 21st ACM Symposium on Theory of Computing, pp. 230\u2013240 (1989)","DOI":"10.1145\/73007.73053"},{"issue":"3","key":"326_CR4","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1016\/0196-6774(90)90017-9","volume":"11","author":"B Awerbuch","year":"1990","unstructured":"Awerbuch, B., Bar-Noy, A., Linial, N., Peleg, D.: Improved routing strategies with succinct tables. J. Algorithms 11(3), 307\u2013341 (1990)","journal-title":"J. Algorithms"},{"key":"326_CR5","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Berger, B., Cowen, L., Peleg, D.: Near-linear cost sequential and distribured constructions of sparse neighborhood covers. In: Proceedings 34th Symposium on Foundations of Computer Science (FOCS), pp. 638\u2013647 (1993)","DOI":"10.1109\/SFCS.1993.366823"},{"key":"326_CR6","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1137\/0405013","volume":"5","author":"B Awerbuch","year":"1992","unstructured":"Awerbuch, B., Peleg, D.: Routing with polynomial communication-space trade-off. SIAM J. Discr. Math. 5, 151\u2013162 (1992)","journal-title":"SIAM J. Discr. Math."},{"key":"326_CR7","doi-asserted-by":"crossref","unstructured":"Baswana, S., Kavitha, T.: Faster algorithms for approximate distance oracles and all-pairs small stretch paths. In: Proceedings of the 47th Symposium on Foundations of Computer Science (FOCS), pp. 591\u2013602 (2006)","DOI":"10.1109\/FOCS.2006.29"},{"key":"326_CR8","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1145\/1198513.1198518","volume":"2","author":"S Baswana","year":"2006","unstructured":"Baswana, S., Sen, S.: Approximate distance oracles for unweighted graphs in expected $$O(n^2)$$ O ( n 2 ) time. ACM Trans. Algorithms 2, 557\u2013577 (2006)","journal-title":"ACM Trans. Algorithms"},{"issue":"4","key":"326_CR9","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1002\/rsa.20130","volume":"30","author":"S Baswana","year":"2007","unstructured":"Baswana, S., Sen, S.: A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Struct. Algorithms 30(4), 532\u2013563 (2007)","journal-title":"Random Struct. Algorithms"},{"key":"326_CR10","unstructured":"Becker, R., Karrenbauer, A., Krinninger, S., Lenzen, C.: Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In: 31st Symposium on Distributed Computing (DISC) (2017)"},{"key":"326_CR11","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1090\/qam\/102435","volume":"16","author":"RE Bellman","year":"1958","unstructured":"Bellman, R.E.: On a routing problem. Quart. Appl. Math. 16, 87\u201390 (1958)","journal-title":"Quart. Appl. Math."},{"key":"326_CR12","doi-asserted-by":"crossref","unstructured":"Bernstein, A.: Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract]. In: Proceedings of the 45th Symposium Theory of Computing (STOC), pp. 725\u2013734 (2013)","DOI":"10.1145\/2488608.2488701"},{"key":"326_CR13","doi-asserted-by":"publisher","first-page":"16","DOI":"10.4304\/jcp.2.9.16-26","volume":"2","author":"S Cicerone","year":"2007","unstructured":"Cicerone, S., D\u2019Angelo, G., Di Stefano, G., Frigioni, D., Petricola, A.: Partially dynamic algorithms for distributed shortest paths and their experimental evaluation. J. Comput. 2, 16\u201326 (2007)","journal-title":"J. Comput."},{"key":"326_CR14","doi-asserted-by":"crossref","unstructured":"Das Sarma, A., Dinitz, M., Pandurangan, G.: Efficient computation of distance sketches in distributed networks. In: Proceedings of the 24th ACM Symposium on Parallelism in Algorithms and Architectures (2012)","DOI":"10.1145\/2312005.2312060"},{"key":"326_CR15","doi-asserted-by":"crossref","unstructured":"Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. In: Proceedings of the 43th ACM Symposium on Theory of Computing, pp. 363\u2013372 (2011)","DOI":"10.1145\/1993636.1993686"},{"key":"326_CR16","doi-asserted-by":"crossref","unstructured":"Derbel, B., Gavoille, C., Peleg, D., Viennot, L.: On the locality of distributed sparse spanner construction. In: Proceedings of the 27th Symposium on Principles of Distributed Computing (PODC), pp. 273\u2013282 (2008)","DOI":"10.1145\/1400751.1400788"},{"key":"326_CR17","doi-asserted-by":"crossref","unstructured":"Elkin, M., Neiman, O.: On efficient distributed construction of near optimal routing schemes: Extended abstract. In: Proceedings 34th Symposium on Principles of Distributed Computing (PODC), pp. 235\u2013244 (2016)","DOI":"10.1145\/2933057.2933098"},{"key":"326_CR18","unstructured":"Ford, L.R.: Network flow theory. Techical Report P-923, The Rand Corporation (1956)"},{"key":"326_CR19","doi-asserted-by":"crossref","unstructured":"Frischknecht, S., Holzer, S., Wattenhofer, R.: Networks cannot compute their diameter in sublinear time. In: Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms, pp. 1150\u20131162 (2012)","DOI":"10.1137\/1.9781611973099.91"},{"key":"326_CR20","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s00446-002-0073-5","volume":"16","author":"C Gavoille","year":"2003","unstructured":"Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distrib. Comput. 16, 111\u2013120 (2003)","journal-title":"Distrib. Comput."},{"key":"326_CR21","unstructured":"Gavoille, C., Peleg, D., P\u00e9rennes, S., Raz, R.: Distance labeling in graphs. In: Proceedings of the 12th ACM Symposium on Discrete Algorithms, pp. 210\u2013219 (2001)"},{"key":"326_CR22","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Lenzen, C.: Near-optimal distributed tree embedding. In: 28th Symposium on Distributed Computing (DISC), pp. 197\u2013211 (2014)","DOI":"10.1007\/978-3-662-45174-8_14"},{"issue":"1","key":"326_CR23","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jagm.1996.0842","volume":"24","author":"S Haldar","year":"1997","unstructured":"Haldar, S.: An \u2018all pairs shortest paths\u2019 distributed algorithm using $$2n^2$$ 2 n 2 messages. J. Algorithms 24(1), 20\u201336 (1997)","journal-title":"J. Algorithms"},{"key":"326_CR24","doi-asserted-by":"crossref","unstructured":"Henzinger, M., Krinninger, S., Nanongkai, D.: An Almost-Tight Distributed Algorithm for Computing Single-Source Shortest Paths. CoRR abs\/1504.07056 (2015)","DOI":"10.1145\/2897518.2897638"},{"key":"326_CR25","unstructured":"Holzer, S., Pinsker, N.: Approximation of Distances and Shortest Paths in the Broadcast Congest Clique. CoRR abs\/1412.3445 (2014)"},{"key":"326_CR26","doi-asserted-by":"crossref","unstructured":"Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: Proceedings of the 31st ACM Symposium on Principles of Distributed Computing (2012)","DOI":"10.1145\/2332432.2332504"},{"key":"326_CR27","doi-asserted-by":"crossref","unstructured":"Hua, Q.S., Fan, H., Qian, L., Ai, M., Li, Y., Shi, X., Jin, H.: Brief Announcement: A Tight Distributed Algorithm for All Pairs Shortest Paths and Applications. In: 28th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 439\u2013441 (2016)","DOI":"10.1145\/2935764.2935812"},{"key":"326_CR28","doi-asserted-by":"publisher","unstructured":"Izumi, T., Wattenhofer, R.: Time lower bounds for distributed distance oracles. In: Proceedings of the 18th International Conference on Principles of Distributed Systems (OPODIS), pp. 60\u201375. Springer International Publishing (2014). https:\/\/doi.org\/10.1007\/978-3-319-14472-6_5","DOI":"10.1007\/978-3-319-14472-6_5"},{"issue":"2","key":"326_CR29","first-page":"141","volume":"11","author":"S Kanchi","year":"2004","unstructured":"Kanchi, S., Vineyard, D.: An optimal distributed algorithm for all-pairs shortest-path. Int. J. Inf. Theories Appl. 11(2), 141\u2013146 (2004)","journal-title":"Int. J. Inf. Theories Appl."},{"key":"326_CR30","doi-asserted-by":"crossref","unstructured":"Kavitha, T.: Faster algorithms for all-pairs small stretch distances in weighted graphs. In: Proceedings of the FSTTCS, pp. 328\u2013339 (2007)","DOI":"10.1007\/978-3-540-77050-3_27"},{"key":"326_CR31","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/PL00009223","volume":"22","author":"PN Klein","year":"1998","unstructured":"Klein, P.N., Subramanian, S.: A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica 22, 235\u2013249 (1998)","journal-title":"Algorithmica"},{"key":"326_CR32","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast routing table construction using small messages [Extended Abstract]. In: Proceedings of the 45th Symposium on the Theory of Computing (STOC) (2013). Full version at http:\/\/arxiv.org\/abs\/1210.5774"},{"key":"326_CR33","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Improved distributed steiner forest construction. In: Proceedings of the 32nd Symposium on Principles of Distributed Computing (PODC), pp. 262\u2013271 (2014)","DOI":"10.1145\/2611462.2611464"},{"key":"326_CR34","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Patt-Shamir, B.: Fast partial distance estimation and applications. In: Proceedings of the 33rd Symposium on Principles of Distributed Computing (PODC) (2015)","DOI":"10.1145\/2767386.2767398"},{"key":"326_CR35","doi-asserted-by":"crossref","unstructured":"Lenzen, C., Peleg, D.: Efficient distributed source detection with limited bandwidth. In: Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing (2013)","DOI":"10.1145\/2484239.2484262"},{"key":"326_CR36","doi-asserted-by":"crossref","unstructured":"Madry, A.: Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. In: Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5\u20138 June 2010, pp. 121\u2013130 (2010)","DOI":"10.1145\/1806689.1806708"},{"issue":"5","key":"326_CR37","doi-asserted-by":"publisher","first-page":"711","DOI":"10.1109\/TCOM.1980.1094721","volume":"COM\u201328","author":"J McQuillan","year":"1980","unstructured":"McQuillan, J., Richer, I., Rosen, E.: The new routing algorithm for the arpanet. IEEE Trans. Commun. COM\u201328(5), 711\u2013719 (1980)","journal-title":"IEEE Trans. Commun."},{"key":"326_CR38","doi-asserted-by":"crossref","unstructured":"Moy, J.: OSPF version 2. RFC 2328, Network Working Group (1998)","DOI":"10.17487\/rfc2328"},{"key":"326_CR39","doi-asserted-by":"crossref","unstructured":"Nanongkai, D.: Distributed approximation Algorithms for weighted shortest paths. In: Proceedings of the 46th Symposium on Theory of Computing (STOC), pp. 565\u2013573 (2014)","DOI":"10.1145\/2591796.2591850"},{"key":"326_CR40","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Proximity-preserving labeling schemes and their applications. In: Proceedings of the 25th International Workshop on Graph-Theoretic Concepts in Computer Science, pp. 30\u201341 (1999)","DOI":"10.1007\/3-540-46784-X_5"},{"key":"326_CR41","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. SIAM, Philadelphia, PA (2000)"},{"key":"326_CR42","doi-asserted-by":"crossref","unstructured":"Peleg, D., Roditty, L., Tal, E.: Distributed algorithms for network diameter and girth. In: Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (2012)","DOI":"10.1007\/978-3-642-31585-5_58"},{"key":"326_CR43","doi-asserted-by":"publisher","first-page":"1427","DOI":"10.1137\/S0097539700369740","volume":"30","author":"D Peleg","year":"2000","unstructured":"Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30, 1427\u20131442 (2000)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"326_CR44","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/jgt.3190130114","volume":"13","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Sch\u00e4ffer, A.A.: Graph spanners. J. Graph Theory 13(1), 99\u2013116 (1989)","journal-title":"J. Graph Theory"},{"issue":"2","key":"326_CR45","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1137\/0218050","volume":"18","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18(2), 740\u2013747 (1989)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"326_CR46","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1145\/65950.65953","volume":"36","author":"D Peleg","year":"1989","unstructured":"Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM 36(3), 510\u2013530 (1989)","journal-title":"J. ACM"},{"key":"326_CR47","volume-title":"Computer Networks: A Systems Approach","author":"LL Peterson","year":"2011","unstructured":"Peterson, L.L., Davie, B.S.: Computer Networks: A Systems Approach, 5th edn. Morgan Kaufmann, Burlington (2011)","edition":"5"},{"key":"326_CR48","doi-asserted-by":"crossref","unstructured":"Raghavan, P., Thompson, C.D.: Provably good routing in graphs: Regular arrays. In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing, STOC \u201985, pp. 79\u201387 (1985)","DOI":"10.1145\/22145.22154"},{"key":"326_CR49","doi-asserted-by":"crossref","unstructured":"Roditty, L., Thorup, M., Zwick, U.: Deterministic constructions of approximate distance oracles and spanners. In: Proceedings of the 32nd Colloquium on Automata, Languages, and Programming (ICALP), pp. 261\u2013272 (2005)","DOI":"10.1007\/11523468_22"},{"key":"326_CR50","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1093\/comjnl\/28.1.5","volume":"28","author":"N Santoro","year":"1985","unstructured":"Santoro, N., Khatib, R.: Labelling and implicit routing in networks. Comput. J. 28, 5\u20138 (1985)","journal-title":"Comput. J."},{"key":"326_CR51","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1109\/TIT.1983.1056620","volume":"29","author":"A Segall","year":"1983","unstructured":"Segall, A.: Distributed network protocols. IEEE Trans. Inf. Theory 29, 23\u201335 (1983)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"326_CR52","doi-asserted-by":"crossref","unstructured":"Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the 13th ACM Symposium on Parallel Algorithms and Architectures (2001)","DOI":"10.1145\/378580.378581"},{"issue":"1","key":"326_CR53","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1044731.1044732","volume":"52","author":"M Thorup","year":"2005","unstructured":"Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1\u201324 (2005)","journal-title":"J. ACM"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-018-0326-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-018-0326-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-018-0326-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,1]],"date-time":"2025-07-01T19:55:47Z","timestamp":1751399747000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-018-0326-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,13]]},"references-count":53,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["326"],"URL":"https:\/\/doi.org\/10.1007\/s00446-018-0326-6","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,13]]},"assertion":[{"value":"7 February 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}