1 Introduction
1.1 Main contributions
1.1.1 Source detection
1.1.2 Approximate source detection
-
\(\mathrm {wd}'\) is not required to be a metric (just as \(\mathrm {wd}_h\) is not necessarily a metric);
-
\(\mathrm {wd}'\) is not required to be monotone in h (unlike \(\mathrm {wd}_h\));
-
\(\mathrm {wd}'\) is not required to be symmetric (also unlike \(\mathrm {wd}_h\)); and
-
the list \(\mathcal{L}_v^{(h,\varepsilon )}\) could contain entries \((\mathrm {wd}'(v,s),s)\) with \(\mathrm {wd}_h(v,s)=\infty \), i.e., \(\mathrm {hd}(v,s)>h\).
1.1.3 Skeleton spanners
-
\(E_{\mathcal{S},h}= \left\{ \{v,w\}\mid v,w\in \mathcal{S} \wedge v\ne w \wedge \mathrm {hd}(v,w)\le h \right\} \);
-
For \(\{v,w\}\in E_{\mathcal{S},h}\), \(W_{\mathcal{S},h}(v,w) = \mathrm {wd}_h(v,w)\).
-
\(p_e\) has at most \(\lceil \sqrt{n}\,\rceil \) hops;
-
each node \(v\in p_e\setminus \{s\}\) knows the next node \(u\in p_e\) in the direction of s; and
-
each node \(v\in p_e\setminus \{t\}\) knows the next node \(u\in p_e\) in the direction of t.
1.1.4 Further results
1.2 Organization of this paper
2 Related work
2.1 Distributed algorithms for exact all-pairs shortest-paths
2.1.1 Distributed construction of compact routing tables
2.1.2 Spanners
2.1.3 Distributed lower bounds
2.1.4 Leveraging the shortest-path-diameter
3 Preliminaries
3.1 The computational model
-
their own identifier;
-
the identifiers of the respective other endpoint of incident edges;5
-
the weight of incident edges (if the graph is weighted); and, in general,
-
possible further problem-specific input.
3.2 General concepts
-
\(f(n)\in {{\tilde{\varOmega }}}(g(n))\) iff \(g(n)\in {\tilde{\mathcal {O}}}(f(n))\),
-
\({\tilde{\varTheta }}(f(n))={{\tilde{\mathcal {O}}}}(f(n))\cap {\tilde{\varOmega }}(f(n))\),
-
\(f(n)\in {\tilde{o}}(g(n))\) iff for any \(c\in \mathbb {R}^+_0\) it holds that \(\lim \sup _{n\rightarrow \infty }f(n)\log ^c(n)/g(n)=0\), and
-
\(f(n)\in {\tilde{\omega }}(g(n))\) iff \(g(n)\in {\tilde{o}}(f(n))\).
3.3 Some graph-theoretic concepts
-
The hop-length of a path p, denoted \(\ell (p)\), is the number of edges in it.
-
A path \(p_0\) between v and u is a shortest unweighted path if its hop-length \(\ell (p_0)\) is minimum among all \(p\in \mathrm {paths}(v,u)\).
-
The hop distance\(\mathrm {hd}:V\times V\rightarrow \mathbb {N}_0\) is defined as the hop-length of a shortest unweighted path, \(\mathrm {hd}(v,u):=\min \{\ell (p)\,|\,{p\in \mathrm {paths}(v,u)}\}\).
-
The (hop-)diameter\(D=\max _{v,u\in V}\{\mathrm {hd}(v,u)\}\).
-
The weight of a path p, denoted W(p), is its total edge weight, i.e., \(W(p)=\sum _{i=1}^{\ell (p)} W(v_{i-1},v_i)\).
-
A path \(p_0\) between v and u is a shortest weighted path if its weight \(W(p_0)\) is minimum among all \(p\in \mathrm {paths}(v,u)\).
-
The weighted distance\(\mathrm {wd}:V\times V\rightarrow \mathbb {N}\) is defined as the weight of a shortest weighted path,$$\begin{aligned} \mathrm {wd}(v,u)=\min \{W(p)\,|\,{p\in \mathrm {paths}(v,u)}\}. \end{aligned}$$
-
The weighted diameter$$\begin{aligned} \mathrm {WD}=\max \{\mathrm {wd}(v,u)\,|\,{v,u\in V}\}. \end{aligned}$$
-
For \(h\in \mathbb {N}\),is the h-hop distance. Note that \(\mathrm {wd}_h(v,u)=\infty \) iff \(\mathrm {hd}(v,u)>h\).$$\begin{aligned} \mathrm {wd}_h(v,u)=\inf \{W(p)\,|\,{p\in \mathrm {paths}(v,u)\wedge \ell (p)\le h}\} \end{aligned}$$
-
The shortest path diameter isi.e., the minimum hop distance h so that for each \(u,v\in V\) there is a shortest weighted path of at most h hops.$$\begin{aligned} \mathrm {SPD}=\min \{h\in \mathbb {N}\,|\,\mathrm {wd}_h=\mathrm {wd}\}, \end{aligned}$$
3.4 Basic primitives
-
The number of nodes n.
-
The maximum edge weight \(\max _{e\in E}\{W(e)\}\).
-
The minimum edge weight \(\min _{e\in E}\{W(e)\}\).
-
|S| for any \({ S}\subseteq V\) given locally, i.e., when each \(v\in V\) knows whether \(v\in { S}\) or not.
4 Source detection in unweighted graphs
4.1 Pipelined Bellman–Ford algorithm
4.2 Analysis
4.3 Additional properties
4.4 Source detection in unweighted directed graphs
5 Approximate source detection
5.1 Reduction to the unweighted case
1. For all \(i\in \left\{ 0,\ldots ,i_{\max } \right\} \), solve unweighted \((S,h',\sigma )\)-detection on \(G_i\) by \(\mathcal A\). Let \(L_{v,i}\) denote the output for \(G_i\) at node v. | |
2. For each source \(s\in S\), each node v computes \(\begin{aligned} {\tilde{\mathrm {wd}}}(v,s)=\inf \{&\mathrm {hd}_i(v,s)b(i)\mid (\mathrm {hd}_i(v,s),s)\in L_{v,i}\\&\text { for some } 0\le i\le i_{\max } \}. \end{aligned}\) | |
3. Let \(L'_v\) be the list \(\{({\tilde{\mathrm {wd}}}(v,s),s)\mid s\in S\text { and }{\tilde{\mathrm {wd}}}(v,s)<\infty \},\) ordered in increasing lexicographical order. Node v outputs \(L_v=\mathrm {top}_\sigma (L'_v)\). |
5.2 Additional properties
-
The parent of v in each of the induced trees (rooted at sources).
-
The round in which the message establishing the parent-child relation was received.
-
The (weighted) distance in the tree to the source at which the tree is rooted.
5.3 Approximate source detection in directed graphs
6 Skeletons and skeleton spanners
-
\(E_{\mathcal{S},h}= \left\{ \{v,w\}\mid v,w\in \mathcal{S} \wedge v\ne w \wedge \mathrm {hd}(v,w)\le h \right\} \);
-
For \(\{v,w\}\in E_{\mathcal{S},h}\), \(W_{\mathcal{S},h}(v,w) = \mathrm {wd}_h(v,w)\).
6.1 The Baswana–Sen construction
1. Initially, each node is a singleton cluster: \(R_1:=\left\{ \left\{ v \right\} \mid v\in V_H \right\} \). | |
2. For \(i=1,\ldots ,k-1\) do (the \(i^{th}\) iteration is called “phase i”): | |
(a) Each cluster from \(R_i\) is marked independently with probability \(|V_H|^{-1/k}\). \(R_{i+1}\) is defined to be the set of clusters marked in phase i. | |
(b) If v is a node in an unmarked cluster: | |
(i) Define \(Q_v\) to be the set of edges that consists of the lightest edge from v to each cluster in \(R_i\) it is adjacent to. | |
(ii) If v is not adjacent to any marked cluster, all edges in \(Q_v\) are added to the spanner. | |
(iii) Otherwise, let u be the closest neighbor of v in a marked cluster. In this case v adds to the spanner the edge \(\{v,u\}\), and also all edges \(\{v,w\}\in Q_v\) with \((W_H(v,w),w)<(W_H(v,u),u)\) (i.e., ordered by weight, breaking ties by identifiers). Also, let X be the cluster of u. Then \(X:=X\cup \{v\}\). (I.e., vjoins the cluster of u.) | |
3. Each node v adds, for each cluster \(X\in R_k\) it is adjacent to, the lightest edge connecting it to X. |
6.2 Constructing the skeleton spanner
6.3 Routing on the skeleton spanner
6.4 Approximate skeleton and skeleton spanner
-
\(E_{\mathcal{S},h}= \left\{ \{v,w\}\mid v,w\in \mathcal{S} \wedge v\ne w \wedge \mathrm {hd}(v,w)\le h \right\} \);
-
For \(\{v,w\}\in E_{\mathcal{S},h}\), \(\mathrm {wd}_h(v,w)\le {\tilde{W}}_{\mathcal{S},h}(v,w) \le (1+\varepsilon )\mathrm {wd}_h(v,w)\).
7 Table construction in unweighted graphs
7.1 Exact tables
7.2 Tables of Size \({\tilde{\mathcal {O}}}(n^{1/k})\) and Stretch \(4k-3\)
7.2.1 Algorithm
1. Define \(S_0=V\). Given \(S_{i-1}\), construct \(S_i\), for \(i\in \left\{ 1,\ldots ,k-1 \right\} \), by independently including each member of \(S_{i-1}\) in \(S_i\) with probability \(n^{-1/k}\). Set \(S_k=\emptyset \). | |
2. For \(i=0,\ldots ,k-1\), run \((S_i,D,\sigma )\)-detection, where \(\sigma :=c n^{1/k}\log n\) for a sufficiently large constant c. Let \(T_{s,i}\) denote the induced tree for source \(s\in S_i\). | |
3. For each tree \(T_{s,i}\), construct a tree labeling scheme as in Theorem 6.14. The result, for each \(v\in T_{s,i}\), is a label \(\lambda _i(v)\) and a routing table \(R_{s,i}(v)\) of \(\mathcal {O}(\log n)\) bits, facilitating routing in \(T_{s,i}\). | |
4. Let \(s_{v,i}\) be the node in \(S_i\) minimizing \(\mathrm {hd}(v,s_{v,i})\). The output of a node \(v\in V\) consists of (i) its label \(\lambda (v)\) constructed from the ID of v and the list of pairs \(\left\{ (s_{v,i},\lambda _i(v)) \right\} _{i=1}^{k-1}\), and (ii) a table containing the lists \(L_{v,i}\) constructed by source detection\(^{10}\) and the routing table \(R_{s,i}(v)\) for each s, i for which \((\mathrm {hd}(v,s),s)\in L_{v,i}\). |
7.2.2 Analysis
8 Table construction in weighted graphs
8.1 Small shortest-path diameter
8.2 The general case
8.2.1 Algorithm
1. Construct an (approximate) skeleton spanner \(G_\mathcal{S}=(\mathcal{S},E_\mathcal{S},W_\mathcal{S})\) and make it known to all nodes (Corollary 6.12). Node \(v\in V\) also stores the solution \(L_v(\mathcal{S})\) to \((1+\varepsilon )\)-approximate \((\mathcal{S},h,|\mathcal{S}|)\)-detection, where \(h= n^{\frac{2k+1}{4k}}\), which is computed during the construction, as well as the routing information for \((1+\varepsilon )\)-stretch routing to the detected nodes (computed using Corollary 5.6). | |
4. For each \(v\in V\), let \(s'_v\) be the closest node of \(\mathcal{S}\) w.r.t. \(\mathrm {wd}'\), i.e., \((\mathrm {wd}'(v,s_v'),s_v')\) is the first entry of \(L_v(V)\) with \(s_v'\in \mathcal{S}\).\(^{11}\) For each \(s\in \mathcal{S}\), let \(T_s\) be the tree defined by the union of all routing paths from nodes v with \(s_v'=s\). Using Corollary 4.7 and Theorem 6.14, compute tree labels \(\lambda _{v,s}\) as in [52] in each such tree \(T_s\) for each \(v\in T_s\). The label of node v is \(\lambda _v:=(v,s_v',\mathrm {wd}'(v,s_v'),\lambda _{v,s_v'})\) and its routing table contains all that was computed in the previous steps. |
8.2.2 Analysis
8.2.3 From stateful to stateless routing
9 Lower bounds
9.1 Approximating the diameter in weighted graphs
-
Nodes \(v_{i,j}\) for \(1\le i,j\le m\). These nodes are connected as m paths of length \(m-1\) (horizontal paths in the figure). All path edges are of weight 1.
-
A star rooted at an Alice node, whose the children are \(v_{1,1},\ldots ,v_{m,1}\), and similarly, a star rooted at a Bob node, whose leaves are \(v_{1,m},\ldots ,v_{m,m}\). The weights of these edges may be either 1 or \(\omega _{\max }\) (that’s the only difference between graphs in \({\mathcal {G}}_n\)).
-
For each \(1\le j\le m\) there is a node \(u_j\) connected to all nodes \(v_{i,j}\), \(1\le i\le m\) in “column” j, with edges of weight \(\omega _{\max }\). In addition, there is a binary tree whose leaves are the nodes \(u_j\). All tree edges have weight 1. Finally, Alice and Bob are connected to \(u_1\) and \(u_m\), respectively, by edges of weight 1.
9.2 Hardness of name-dependent distributed table construction
-
All edges incident to a node in the binary tree have weight \(\omega _{\max }\).
-
For each \(i\in \{1,\ldots ,m\}\), the edge from Alice to \(v_{i,1}\) has weight 1 if \(i\in A\) and weight \(\omega _{\max }\) else. Likewise, the edge from Bob to \(v_{i,m}\) has weight 1 if \(i\in B\) and otherwise weight \(\omega _{\max }\).
-
The remaining edges (on the m paths from \(v_{i,1}\) to \(v_{i,m}\)) have weight 1.