Abstract
Given a distributed network represented by a weighted undirected graph \(G=(V,E)\) on n vertices, and a parameter k, we devise a randomized distributed algorithm that whp computes a routing scheme in \(O(n^{1/2+1/k}+D)\cdot n^{o(1)}\) rounds, where D is the hop-diameter of the network. Moreover, for odd k, the running time of our algorithm is \(O(n^{1/2 + 1/(2k)} + D) \cdot n^{o(1)}\). Our running time nearly matches the lower bound of \(\tilde{\Omega }(n^{1/2}+D)\) rounds (which holds for any scheme with polynomial stretch). The routing tables are of size \(\tilde{O}(n^{1/k})\), the labels are of size \(O(k\log ^2n)\), and every packet is routed on a path suffering stretch at most \(4k-5+o(1)\). Our construction nearly matches the state-of-the-art for routing schemes built in a centralized sequential manner. The previous best algorithms for building routing tables in a distributed small messages model were by Lenzen and Patt-Shamir (In: Symposium on theory of computing conference, STOC’13, Palo Alto, CA, USA, 2013) and Lenzen and Patt-Shamir (In: Proceedings of the 2015 ACM symposium on principles of distributed computing, PODC 2015, Donostia-San Sebastián, Spain, 2015). The former has similar properties but suffers from substantially larger routing tables of size \(O(n^{1/2+1/k})\), while the latter has sub-optimal running time of \(\tilde{O}(\min \{(nD)^{1/2}\cdot n^{1/k},n^{2/3+2/(3k)}+D\})\).
Similar content being viewed by others
Notes
The \(\tilde{O}\) hides \(\log ^{O(1)}n\) factors.
They also presented stretch \(2k-1\), assuming “handshaking”: allowing the source and destination to communicate before the routing phase begins, but it is often desirable to avoid handshaking. Henceforth, we discuss only routing schemes that do not allow handshaking.
We remark that for the class of k-chordal graphs, [26] showed a construction of a routing scheme that could be computed efficiently in a distributed manner.
In fact, they showed a scheme in which it suffices to have a sketch of one vertex, and a \(O(k\log n)\) size label of the other vertex, to derive the distance estimation. Our result has a similar property.
By “high probability” we mean with probability at least \(1-n^{-c}\), for any desired constant c.
By a virtual tree we mean a tree whose edges are not present in the network.
The computed values are symmetric, that is, \(d_{uv}=d_{vu}\) whenever \(u,v\in V'\).
For odd k the number of rounds becomes \((n^{1/2+1/(2k)}+D)\cdot \min \{(\log n)^{O(k)},2^{\tilde{O}(\sqrt{\log n})}\}\).
The claim guarantees the existence of \(u_1\), but we may apply it on the pair \(u_1,v\) as well (since the shortest-path between them is a subset of the u to v shortest-path) to obtain \(u_2\), and so on.
See (14) below for the required condition on depth.
References
Awerbuch, B., Bar-Noy, A., Linial, N., Peleg, D.: Improved routing strategies with succinct tables. J. Algorithms 11(3), 307–341 (1990)
Abraham, I., Gavoille, C., Malkhi, D.: Routing with improved communication-space trade-off. In: Distributed Computing, 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4–7, 2004, Proceedings, pp. 305–319 (2004)
Bernstein, A.: Fully dynamic (2 + epsilon) approximate all-pairs shortest paths with fast query and close to linear update time. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25–27, 2009, Atlanta, Georgia, USA, pp. 693–702 (2009)
Chechik, S.: Compact routing schemes with improved stretch. In: ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22–24, 2013, pp. 33–41 (2013)
Cohen, E.: Polylog-time and near-linear work approximation scheme for undirected shortest paths. J. ACM 47(1), 132–166 (2000)
Cowen, L.: Compact routing with minimum stretch. J. Algorithms 38(1), 170–183 (2001)
Eilam, T., Gavoille, C., Peleg, D.: Compact routing schemes with low stretch factor. J. Algorithms 46(2), 97–114 (2003)
Elkin, M.: A faster distributed protocol for constructing a minimum spanning tree. J. Comput. Syst. Sci. 72(8), 1282–1308 (2006)
Elkin, M.: An unconditional lower bound on the time-approximation trade-off for the distributed minimum spanning tree problem. SIAM J. Comput. 36(2), 433–456 (2006)
Elkin, M., Neiman, O.: Hopsets with constant hopbound, and applications to approximate shortest paths. In: 57th IEEE Annual Symposium on Foundations of Computer Science, FOCS (2016)
Elkin, M., Neiman, O.: On efficient distributed construction of near optimal routing schemes: Extended abstract. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25–28, 2016, pp. 235–244 (2016)
Ghaffari, M.: Near-optimal scheduling of distributed algorithms. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC ’15, ACM, New York, NY, USA, pp. 3–12 (2015)
Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. In: Distributed Computing—27th International Symposium, DISC 2013, Jerusalem, Israel, October 14–18, 2013. Proceedings, pp. 1–15 (2013)
Garay, J.A., Kutten, S., Peleg, D.: A sublinear time distributed algorithm for minimum-weight spanning trees. SIAM J. Comput. 27(1), 302–316 (1998)
Gavoille, C., Peleg, D.: Compact and localized distributed data structures. Distrib. Comput. 16(2–3), 111–120 (2003)
Henzinger, M., Krinninger, S., Nanongkai, D.: Decremental single-source shortest paths on undirected graphs in near-linear total update time. In: 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18–21, 2014, pp. 146–155 (2014)
Henzinger, M., Krinninger, S., Nanongkai, D.: A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18–21, 2016, pp. 489–498 (2016)
Izumi, T., Wattenhofer, R.: Time lower bounds for distributed distance oracles. In: Principles of Distributed Systems—18th International Conference, OPODIS 2014, Cortina d’Ampezzo, Italy, December 16–19, 2014. Proceedings, pp. 60–75 (2014)
Kutten, S., Peleg, D.: Fast distributed construction of small k-dominating sets and applications. J. Algorithms 28(1), 40–66 (1998)
Lenzen, C., Patt-Shamir, B.: Fast routing table construction using small messages. In: Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1–4, 2013, pp. 381–390 (2013)
Lenzen, C., Peleg, D.: Efficient distributed source detection with limited bandwidth. In: ACM Symposium on Principles of Distributed Computing, PODC ’13, Montreal, QC, Canada, July 22–24, 2013, pp. 375–382 (2013)
Lenzen, C., Patt-Shamir, B.: Fast partial distance estimation and applications. In: Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21–23, 2015, pp. 153–162 (2015)
Lenzen, C., Patt-Shamir, B.: Private communication (2016)
Lenzen, C., Patt-Shamir, B., Peleg, D.: Distributed distance computation and routing with small messages (2016) (Unpublished)
Nanongkai, D.: Distributed approximation algorithms for weighted shortest paths. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31–June 03, 2014, pp. 565–573 (2014)
Nisse, N., Rapaport, I., Suchan, K.: Distributed computing of efficient routing schemes in generalized chordal graphs. Theor. Comput. Sci. 444, 17–27 (2012)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA (2000)
Peleg, D.: Proximity-preserving labeling schemes. J. Graph Theory 33(3), 167–176 (2000)
Peleg, D., Rubinovich, V.: A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction. SIAM J. Comput. 30(5), 1427–1442 (2000)
Peleg, D., Upfal, E.: A trade-off between space and efficiency for routing tables. J. ACM 36(3), 510–530 (1989)
Sarma, A.D., Dinitz, M., Pandurangan, G.: Efficient distributed computation of distance sketches in networks. Distrib. Comput. 28(5), 309–320 (2015)
Sarma, A.D., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. Comput. 41(5), 1235–1265 (2012)
Thorup, M., Zwick, U.: Compact routing schemes. In: Proceedings of the Thirteenth Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA ’01, pp. 1–10, New York, NY, USA, ACM (2001)
Thorup, M., Zwick, U.: Approximate distance oracles. J. ACM 52(1), 1–24 (2005)
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version [11] of this paper was published in PODC’16.
Michael Elkin: This research was supported by the ISF Grant No. (724/15). Ofer Neiman: Supported in part by ISF Grant No. (523/12) and by BSF Grant No. 2015813.
Appendix: Proof of Theorem 3
Appendix: Proof of Theorem 3
Let \(X\subseteq V\) be a set of vertices so that each \(v\in V\) is sampled to X independently with probability \(1/\sqrt{n}\). Define \(V'=A\cup X\), and note that with high probability \( B=4\sqrt{n}\ln n\ge |V'|\) (since it is given that \(|A|\le 2\sqrt{n}\ln n\)). Apply the same preprocessing steps as in Sect. 3.3.1 with \(V'\) as defined here, to obtain a graph \(G''\) on \(V'\) satisfying (13).
Computing approximate SPT for \(V'\) The first step is to compute the values \((\hat{d}(v),\hat{z}(v))\) for vertices \(v\in V'\). Every vertex in \(v\in A\) initializes its values as (0, v), while \(v\notin A\) sets \((\infty ,\bot )\). Conduct \(\beta =\min \{2^{\tilde{O}(\sqrt{\log n})},(\log n)^{O(k)}\}\) iterations of Bellman–Ford rooted at A: at every iteration, every vertex \(v\in V'\) broadcasts its pair \((\hat{d}(v),\hat{z}(v))\) to the entire graph, and if \(u\in V'\) has \(w''(u,v)+\hat{d}(v)<\hat{d}(u)\), then u updates its pair to be \((w''(u,v)+\hat{d}(v),\hat{z}(v))\). (Recall that \(w''\) is the edge weight function of \(G''\), where the latter is the virtual graph given by Theorem 1 augmented with the hopset edges of Theorem 2.)
The number of rounds required to construct \(G''\) is \((n^{1/2+1/(2k)}+D)\cdot \min \{2^{\tilde{O}(\sqrt{\log n})},(\log n)^{O(k)}\}\), and by Lemma 1 this term also bounds the number of rounds it takes to broadcast the \(O(|V'|\cdot \beta )\) messages for the Bellman–Ford iterations.
Extending the SPT to V At the end of the \(\beta \) iterations of Bellman–Ford, every vertex \(u\in V\) knows \((\hat{d}(v),\hat{z}(v))\) for every \(v\in V'\). Every vertex \(u\in V\) computes
and sets \(\hat{z}(u)=\hat{z}(v)\), where \(v\in V'\) is the minimizer of (40). (Recall that \(d_{uv}\) is the value computed in Theorem 1.)
Analysis We assume all the events of Claim 3 hold (which happens with high probability). For \(u\in V\) let \(z_u\in A\) be a vertex satisfying \(d_G(u,z_u)=d_G(u,A)\). Since we performed \(\beta \) iterations of Bellman–Ford, using (13) with \(v\in V'\) and \(z_v\in A\subseteq V'\) we have that \(v'\) satisfies (5).
Consider now some \(u\in V\), and let \(v\in V'\) be the minimizer in (40). The left hand side of (5) holds, as the fact that \(v\in V'\) satisfies (5) implies
For the right hand side of (5): in the case that \(h(u,z_u)\le B\), by (2) we get that
Otherwise \(h(u,z_u)> B\), and by Claim 3 there exists \(v\in X\subseteq V'\) on the shortest path in G from u to \(z_u\) with \(h(u,v)\le B\). Since (5) holds for v,
Rights and permissions
About this article
Cite this article
Elkin, M., Neiman, O. On efficient distributed construction of near optimal routing schemes. Distrib. Comput. 31, 119–137 (2018). https://doi.org/10.1007/s00446-017-0304-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00446-017-0304-4