Pith. sign in

REVIEW 3 major objections 4 minor 39 references

Shortest Paths in a Hybrid Network Model

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Adding a weak global layer makes shortest-path computation sublinear in the network size.

desk verdict The hybrid model and the APSP results are solid, but the exact SSSP algorithm has a correctness hole in Lemma 5.2 that I think is real. read the letter →

arxiv 1909.01597 v1 pith:LTAJ5FGD submitted 2019-09-04 cs.DC

John Augustine , Kristian Hinnenthal , Fabian Kuhn , Christian Scheideler , Philipp Schneider This is my paper · ORCID
classification cs.DC
keywords hybridnetworkmodelLOCALnode-capacitatedcliqueall-pairsshortestpathssingle-sourcetokendisseminationskeletonspannersdistributedgraphalgorithms
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper asks how much a cheap, severely bandwidth-limited global communication layer can speed up shortest-path computations on a local network where each node may send unbounded messages each round. In the proposed hybrid model—local edges as in the LOCAL model, global clique restricted to $O(\log n)$ messages of $O(\log n)$ bits per node per round—it establishes that exact all-pairs shortest paths can be solved in $\tilde O(n^{2/3})$ rounds, and approximate APSP in $\tilde\Theta(\sqrt{n})$ rounds. For single-source distances, it gives an exact $\tilde O(\sqrt{\mathsf{SPD}})$-round algorithm, a $(1+o(1))$-approximation in $\tilde O(n^{1/3})$ rounds, and an $O(1)$-approximation in $\tilde O(n^{\varepsilon})$ rounds for any constant $\varepsilon>0$. The running times beat what is possible with either network alone, where the local-only lower bound is $\Omega(n)$. A sympathetic reader should care because the model captures real device-to-device plus infrastructure communication, and the algorithms show that even a tiny global channel unlocks sublinear solutions to a canonical graph problem.

What carries the argument

The load-bearing objects are threefold. First, a token-dissemination protocol that balances tokens, multiplies copies, seeds them to random nodes, and spreads them through local neighborhoods, so all $k$ tokens reach all nodes in $\tilde O(\sqrt{k})$ rounds. Second, skeleton graphs, which are overlays on a random sample of marked nodes with edges for $h$-hop paths, used to compress distance information. Third, for exact SSSP, a recursion that splits each node's shortest-path tree at a centroid and forwards only the minimal distance label through global min-aggregations, so every phase takes $O(\log n)$ rounds. For the $\tilde O(n^{\varepsilon})$ SSSP approximation, the machinery is a recursive skeleton spanner: each level samples nodes and constructs a sparse spanner of the previous level entirely through global communication, producing a hierarchy whose union contains short approximating paths.

What would settle it

Run the token-dissemination and aggregation subroutines on an $n$-node path with $k=n$ tokens under the model's global capacity $\gamma=\Theta(\log n)$ and record whether completion time is $\tilde O(\sqrt{n})$ with high probability; a super-polylogarithmic slowdown would contradict Theorem 2.1. A more targeted check is to construct a graph with a single bottleneck node at distance $L$ and $H(X)=\Omega(n)$ bits of entropy, as in Lemma 4.12, and test whether any algorithm can inform the endpoint in $o(\min(L,H(X)/L))$ rounds; if it can, the entropy bottleneck is false.

Watch

Extended reading notes

Core claim

The central discovery is that in a hybrid network, shortest paths are governed by a skeleton: a random sample of marked nodes connected by virtual edges whose weights are $h$-limited distances. If every pair of marked nodes is within $h$ hops, then for pairs far apart, a shortest path contains marked nodes every $\tilde O(h)$ hops, so distance information can be compressed through the skeleton. The paper proves that this compression yields exact APSP in $\tilde O(n^{2/3})$ rounds and, by keeping only each non-marked node's closest marked node, a 3-approximation in $\tilde O(\sqrt{n})$ rounds, which is optimal up to polylog factors. For single-source distances, the paper introduces a divide-and-conquer dissemination over shortest-path trees that lets every node learn its $t(i)$-limited distance with $\tilde O(1)$ amortized rounds per phase, giving exact SSSP in $\tilde O(\sqrt{\mathsf{SPD}})$. It then builds a hierarchy of recursively sampled skeleton spanners, using only global edges above the first level, to obtain $O(1)$-approximate SSSP in $\tilde O(n^{\varepsilon})$ rounds for any constant $\varepsilon>0$.

Load-bearing premise

The whole runtime story depends on the cited node-capacitated clique protocol: that many concurrent min-aggregations, BFS trees, and multicasts can be executed in $O(\log n)$ rounds with high probability, and that the local network can carry the stated message loads. If that protocol is slower or requires stronger preconditions, the $\tilde O(\sqrt{\mathsf{SPD}})$ exact SSSP and $\tilde O(n^{\varepsilon})$ approximation bounds collapse.

Editorial extensions

If this is right

  • Every node can learn a set of $k$ $O(\log n)$-bit tokens in $\tilde O(\sqrt{k})$ rounds, so global broadcast tasks that previously needed $\Omega(k)$ rounds become quadratically cheaper when $k$ is moderate.
  • Exact APSP runs in $\tilde O(n^{2/3})$ rounds, compared with the $\Omega(n)$ rounds needed using only local or only global communication.
  • Approximate APSP is settled up to polylog factors: the 3-approximation in $\tilde O(\sqrt{n})$ matches the $\tilde\Omega(\sqrt{n})$ lower bound, even for approximation factors as large as $\tilde O(\sqrt{n})$.
  • Exact SSSP runs in $\tilde O(\sqrt{\mathsf{SPD}})$ rounds, so on graphs with small shortest-path diameter it is near-logarithmic, while the worst case is $\tilde O(\sqrt{n})$.
  • For any constant $\varepsilon>0$, a constant-factor SSSP approximation can be computed in $\tilde O(n^{\varepsilon})$ rounds, showing that approximate distances scale smoothly with the allowed global budget.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • This suggests that the exact-APSP bottleneck is information compression, not computation: the $\tilde O(n/\sqrt{x})$ cost of disseminating $h$-limited distances between skeleton and non-skeleton nodes is what forces $x=n^{2/3}$, so a better compression of that matrix would directly lower the exponent.
  • The recursive skeleton-spanner hierarchy needs the local network only for its first level, so the same recursion may be runnable in a pure node-capacitated clique model to produce sparse global spanners in $\tilde O(\alpha^3)$ rounds—a testable standalone subroutine.
  • The gap between exact APSP at $\tilde O(n^{2/3})$ and exact SSSP at $\tilde O(\sqrt{\mathsf{SPD}})$ hints that the all-pairs problem may admit a stronger lower bound near $n^{2/3}$; constructing an entropy argument for APSP analogous to the paper's lower-bound lemma would settle this.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper introduces a hybrid network model that combines LOCAL-model local edges with node-capacitated-clique global edges, and studies shortest-path problems in this setting. It presents a token dissemination protocol with runtime ~O(sqrt(k)+l), an exact APSP algorithm in ~O(n^{2/3}) rounds, a 3-approximate APSP algorithm in ~O(sqrt(n)) rounds, a (1+epsilon)-approximate APSP algorithm for unweighted graphs in ~O(sqrt(n)/epsilon) rounds, and an ~Omega(sqrt(n)/log n) lower bound for approximate APSP. For SSSP it claims an exact algorithm in ~O(sqrt(SPD)) rounds, a (1+o(1))-approximation in ~O(n^{1/3}) rounds, and a constant-factor approximation in ~O(n^epsilon) rounds for any constant epsilon>0 via a recursive skeleton-spanner construction. The paper also analyzes the local edge capacity required by each algorithm.

Significance. If the results are correct, the paper makes a strong contribution: it proposes a clean, well-motivated model for hybrid networks and demonstrates that combining unlimited local communication with a weak global mode yields substantial speedups over using either mode alone. The token-dissemination protocol, the skeleton-based APSP framework, the entropy-bottleneck lower-bound technique, and the recursive spanner construction are all interesting and potentially reusable ideas. The paper is also careful to analyze the local capacity needed, which adds practical value. However, the exact SSSP algorithm has a serious correctness gap in its central lemma, and the lower-bound proof for Theorem 2.5 contains an internal parameter inconsistency; these issues must be addressed before the claims can be accepted.

major comments (3)
  1. [Section 5.1, Lemma 5.2 and Algorithm 13] The correctness proof of the exact SSSP algorithm is invalid. Lemma 5.2 asserts that if u is the minimizing origin for a node v, then no node on the branch from u to v in T(u,i) will receive a recursion message with a smaller distance value, because such a value would correspond to an even shorter path from s to v. This fails because the smaller value received at a splitting node may come from an origin w whose i-hop ball contains the splitting node but not the descendants being informed; the i-hop-limited distance d_i does not satisfy the additivity needed to extend w's label to those descendants. Concretely, for phase i=2 (so t(2)=3), consider a graph with edges s-u, u-x, x-v of weight 100 and edges s-w, w-b, b-x of weight 1. The unique origin certifying d_3(s,v)=300 is u, and in T(u,2) the splitting node on the u-v branch is x. At x the aggregation receives u's label 200 (d_1(s,u)+d_2(u,x)=100+100) and w's label 3 (d_1(s,w)+d_2(w,x)=1+2); the algorithm keeps only w's label, and since v is not within 2 hops of w, no message is propagated to v. Thus v receives no finite candidate in this phase, contradicting Lemma 5.2's claim that v learns d_3(s,v). The inductive invariant used to justify the 2*sqrt(SPD) phase bound of Theorem 2.6 is therefore not established.
  2. [Section 4.3, proof of Theorem 2.5] The parameter choice in the lower-bound proof is inconsistent with the claimed approximation range. The proof sets L = floor(sqrt(n)/sqrt(c log n)) and later claims that x/L > sqrt(n) * c * log n / 2 for x = floor(n/2 + L). But with this choice, x/L is approximately (sqrt(n)/2)*sqrt(c log n), not sqrt(n)*c*log n/2, so the displayed inequality is false. The lower bound can be repaired by choosing L = Theta(sqrt(n)/log n), which gives both the ~Omega(sqrt(n)/log n) round bound and the stated range of alpha, but as written the proof does not establish Theorem 2.5.
  3. [Section 5.1, Lemma 5.4] The runtime analysis of the exact SSSP algorithm relies on the assertion that all aggregations of a single step can be performed in O(log n) rounds 'from the discussion of [4]'. Since each node may participate in O(log n) aggregations per step in Algorithm 13, the paper should either prove or precisely cite the concurrency guarantees of the [4] aggregation protocol when many simultaneous min-aggregations target the same or nearby nodes. This dependency is load-bearing for the running time of Theorem 2.6, although it is secondary to the correctness gap in Lemma 5.2.
minor comments (4)
  1. [Theorem 2.5 statement] The bound 'alpha <= sqrt(n)c * log n / 2' is ambiguous; it should be written as alpha <= sqrt(n) * c * log n / 2 to avoid confusion with sqrt(nc).
  2. [Section 5.1, opening paragraph] The phrase 'inform every node u within hop-distance i' should specify 'within hop-distance i of v', since the tree T(v,i) is rooted at v.
  3. [Lemma 5.16] In the last sentence of the proof, 'the hop-length of this G2-path is at most h' appears to refer to a path in G_{i-2}; the subscript is inconsistent.
  4. [References] References [6] and [7] appear to refer to the same paper (Becker et al., DISC 2017); please consolidate them into a single reference.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main algorithmic results are derived from definitions and standard external tools; the self-citation to the node-capacitated clique protocol is a subroutine dependency, not a circular reduction.

full rationale

The paper's derivations are self-contained at the level of the claimed theorems: Theorem 2.1 (token dissemination) is proven from Chernoff bounds and a scheduling lemma; Theorems 2.2--2.5 (APSP) are proven from the skeleton construction of Ullman--Yannakakis plus the token-dissemination protocol; Theorems 2.6--2.8 (SSSP) are proven via new divide-and-conquer, simulation of an external BCC algorithm, and a new recursive skeleton-spanner construction. The only substantial self-citation is to [4] for the min-aggregation primitive, the butterfly-based convergecast, and global-network BFS/multicast machinery. That citation is load-bearing in the sense that the exact SSSP and recursive-spanner algorithms call these primitives as subroutines, but [4] is a published, peer-reviewed protocol with its own stated assumptions and proofs that do not include the present paper's target results; it is therefore independent evidence rather than a circular reduction. No fitted parameter is renamed as a prediction, no theorem is obtained by definition, no uniqueness result is imported from the same authors to force a choice, and no known result is merely renamed. The skeptical concern about Lemma 5.2 concerns the validity of a monotonicity claim for hop-limited distances; that is an internal correctness risk, not an input-output circularity, and it does not affect the circularity score.

Assumptions & free parameters 5 free parameters · 7 assumptions · 0 invented entities

The central claims rest on algorithm design parameters (listed above) and on black-box theorems from prior work, most notably the aggregation and global communication machinery of [4], which shares authors with this paper. No hidden fitted constants or invented physical entities are introduced.

free parameters (5)
  • x (APSP exact) = n^{2/3}
    Skeleton sampling probability 1/x; balances local exploration O~(x) and token dissemination O~(n/√x) in Theorem 2.2.
  • x (APSP approximate) = √n
    Balances local exploration m=max(h,n/h) and closest-marked dissemination; gives 3-approximation in O~(√n) (Theorem 2.3).
  • x (SSSP approximate via BCC) = n^{1/3} ε^{-6}
    Balances local h-hop search O~(x) and BCC simulation O~(√(n/x) ε^{-9}); yields (1+ε)-SSSP in O~(n^{1/3} ε^{-6}) (Theorem 2.7).
  • α (recursive SSSP) = n^ε (ε>0 constant)
    Governs sampling in recursive skeleton spanners; gives (1/ε)^{O(1/ε)} approximation in O(n^{3ε}) (Theorem 2.8).
  • k (Baswana-Sen parameter) = log_α n
    Used in first spanner G1, gives (2k-1)-spanner; affects approximation factor (log_α n)^{O(log_α n)}.
assumptions (7)
  • standard math Chernoff bounds and union bound over polynomially many events
    Used throughout for high-probability claims (Appendix A).
  • domain assumption Node-capacitated clique global model: each node can send and receive O(log n) O(log n)-bit messages per round over a clique
    Defines the hybrid model (Section 1.1).
  • domain assumption Local edges follow the LOCAL model with unbounded message size per round
    Defines the hybrid model (Section 1.1).
  • domain assumption Uniform random sampling of node IDs via global edges is available
    Footnote 3; needed for token balancing, skeleton node sampling, and random target selection. The paper notes the assumption is strong but claims results can be adapted with a sampling service.
  • domain assumption The aggregation protocol and global-network BFS and spanner machinery of Augustine et al. [4] achieve O(log n) rounds for concurrent aggregations and O(log n)-oriented arboricity bounds
    Used as black boxes in exact SSSP (Section 5.1) and recursive spanners (Section 5.3). Not re-derived here; the authors of [4] overlap with the authors of this paper.
  • domain assumption Baswana-Sen [5] yields a (2k-1)-spanner in O(k^2) CONGEST rounds
    Used as black box for the first spanner in Section 5.3.
  • domain assumption Becker et al. [7] computes (1+ε)-SSSP in the broadcast congested clique in O~(ε^{-9}) rounds
    Used as black box in Section 5.2 (Lemma 5.9).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Shortest Paths in a Hybrid Network Model." pith.science (2026). https://pith.science/paper/LTAJ5FGD

@misc{pith2026190901597,
  author       = {Pith},
  title        = {Pith review of: Shortest Paths in a Hybrid Network Model},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LTAJ5FGD}},
  note         = {Machine review of arXiv:1909.01597}
}
abstract

We introduce a communication model for hybrid networks, where nodes have access to two different communication modes: a local mode where communication is only possible between specific pairs of nodes, and a global mode where communication between any pair of nodes is possible. This can be motivated, for instance, by wireless networks in which we combine direct device-to-device communication (e.g., using WiFi) with communication via a shared infrastructure (like base stations, the cellular network, or satellites). Typically, communication over short-range connections is cheaper and can be done at a much higher rate. Hence, we are focusing here on the LOCAL model (in which the nodes can exchange an unbounded amount of information in each round) for the local connections while for the global communication we assume the so-called node-capacitated clique model, where in each round every node can exchange only $O(\log n)$-bit messages with just $O(\log n)$ other nodes. In order to explore the power of combining local and global communication, we study the impact of hybrid communication on the complexity of computing shortest paths in the graph given by the local connections. Specifically, for the all-pairs shortest paths problem (APSP), we show that an exact solution can be computed in time $\tilde O\big(n^{2/3}\big)$ and that approximate solutions can be computed in time $\tilde \Theta\big(\!\sqrt{n}\big)$. For the single-source shortest paths problem (SSSP), we show that an exact solution can be computed in time $\tilde O\big(\!\sqrt{\mathsf{SPD}}\big)$, where $\mathsf{SPD}$ denotes the shortest path diameter. We further show that a $\big(1\!+\!o(1)\big)$-approximate solution can be computed in time $\tilde O\big(n^{1/3}\big)$. Additionally, we show that for every constant $\varepsilon>0$, it is possible to compute an $O(1)$-approximate solution in time $\tilde O(n^\varepsilon)$.

Figures

Figures reproduced from arXiv: 1909.01597 by the authors.

Figure 1
Figure 1. Construction of Lemma 4.12 (left) and of Theorem 2.5 (right). We use Lemma 4.12 to show a lower bound of Ωe √ n  for APSP that is robust even if we allow approxi￾mation factors up to some α ∈ Oe √ n  (c.f. Theorem 2.5, full proof in Section 4.3). The idea is to construct an unweighted graph consisting of a path of length Ω(n) and two node sets S1, S2 of size Ω(n) each. Let b be on one end of the path. Then we atta… view at source ↗
Figure 2
Figure 2. Illustration of the given notations. Lemma 4.8. Let u, v ∈ V such that all shortest u-v-paths have more than h hops and let path R be defined as above. Then w(R) = D˜ G uv w.h.p. Proof. From our definition of the shortest u-v 0 -path O we know that hop(u, u0 ) ≤ h w.h.p. Since u 0 , v0 ∈ M we have d(u 0 , v0 ) = DS u0v 0 w.h.p. due to Lemma 4.3. Therefore we find w(O) = d(u, u0 ) + d(u 0 , v0 ) = dh(u, u0 ) + DS u0v… view at source ↗
Figure 3
Figure 3. To learn the permutation of nodes farther than [PITH_FULL_IMAGE:figures/full_fig_p023_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

39 extracted references · 39 canonical work pages

  1. [4]

    Augustine, M

    J. Augustine, M. Ghaffari, R. Gmyr, K. Hinnenthal, F. Kuhn, J. Li, and C. Scheideler. Distributed com- putation in node-capacitated networks. In Proc. of 31st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2019

    work page 2019

  2. [1]

    Abboud, K

    A. Abboud, K. Censor-Hillel, and S. Khoury. Near-linear lower bounds for distributed distance compu- tations, even in sparse networks. In 30th International Symposium on Distributed Computing (DISC), pages 29–42, 2016

    work page 2016

  3. [2]

    Agarwal, V

    U. Agarwal, V . Ramachandran, V . King, and M. Pontecorvi. A deterministic distributed algorithm for exact weighted all-pairs shortest paths in ˜O(n3/2) rounds. In Proc. of the 2018 ACM Symposium on Principles of Distributed Computing (PODC), pages 199–205, 2018

    work page 2018

  4. [3]

    J. N. Al-Karaki, G. A. Al-Mashaqbeh, and S. M. Bataineh. Routing protocols in wireless mesh net- works: a survey. IJICT, 11(4):445–495, 2017

    work page 2017

  5. [5]

    Baswana and S

    S. Baswana and S. Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algorithms, 30(4):532–563, 2007

    work page 2007

  6. [6]

    Becker, A

    R. Becker, A. Karrenbauer, S. Krinninger, and C. Lenzen. Near-optimal approximate shortest paths and transshipment in distributed and streaming models. In 31st International Symposium on Distributed Computing (DISC), pages 7:1–7:16, 2017

    work page 2017

  7. [7]

    Becker, A

    R. Becker, A. Karrenbauer, S. Krinninger, and C. Lenzen. Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models. In 31st International Symposium on Dis- tributed Computing (DISC 2017), pages 7:1–7:16, 2017

    work page 2017

  8. [8]

    Bernstein and D

    A. Bernstein and D. Nanongkai. Distributed exact weighted all-pairs shortest paths in near-linear time. In 51st ACM Symposium on the Theory of Computing (STOC), 2019

    work page 2019

Show all 39 references
  1. [9]

    G. E. Blelloch, A. Gupta, I. Koutis, G. L. Miller, R. Peng, and K. Tangwongsan. Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs. Theory Comput. Syst., 55(3):521–554, 2014

    2014

  2. [10]

    Censor-Hillel, M

    K. Censor-Hillel, M. Dory, J. H. Korhonen, and D. Leitersdorf. Fast approximate shortest paths in the congested clique. CoRR, abs/1903.05956, 2019

    1903 arXiv

  3. [11]

    Censor-Hillel, P

    K. Censor-Hillel, P. Kaski, J. H. Korhonen, C. Lenzen, A. Paz, and J. Suomela. Algebraic Methods in the Congested Clique. In Proc. of 2015 ACM Symposium on Principles of Distributed Computing (PODC), pages 143–152. ACM, 2015

    2015

  4. [12]

    Drucker, F

    A. Drucker, F. Kuhn, and R. Oshman. On the power of the congested clique model. In Proc. of 33rd ACM Symposium on Principles of Distributed Computing (PODC 2014), pages 367—-376, 2014

    2014

  5. [13]

    M. Elkin. Distributed exact shortest paths in sublinear time. In 49th Annual ACM Symposium on Theory of Computing (STOC), pages 757–770, 2017

    2017

  6. [14]

    Farrington, G

    N. Farrington, G. Porter, S. Radhakrishnan, H. H. Bazzaz, V . Subramanya, Y . Fainman, G. Papen, and A. Vahdat. Helios: a hybrid electrical/optical switch architecture for modular data centers. In ACM SIGCOMM 2010 Conference on Applications, Technologies, Architectures, and Pr...

    2010

  7. [15]

    Foerster, M

    K. Foerster, M. Ghobadi, and S. Schmid. Characterizing the algorithmic complexity of reconfigurable data center architectures. In 2018 Symposium on Architectures for Networking and Communications Systems (ANCS), pages 89–96, 2018

    2018

  8. [16]

    Forster and D

    S. Forster and D. Nanongkai. A faster distributed single-source shortest paths algorithm. In 59th IEEE Symposium on Foundations of Computer Science (FOCS), pages 686–697, 2018

    2018

  9. [17]

    Frischknecht, S

    S. Frischknecht, S. Holzer, and R. Wattenhofer. Networks cannot compute their diameter in sublinear time. In 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1150–1162, 2012

    2012

  10. [18]

    Ghaffari

    M. Ghaffari. Near-Optimal Scheduling of Distributed Algorithms. In Proc. of the 2015 ACM Sympo- sium on Principles of Distributed Computing (PODC), pages 3–12, 2015

    2015

  11. [19]

    Ghaffari and J

    M. Ghaffari and J. Li. Improved distributed algorithms for exact shortest paths. In 50th ACM Sympo- sium on Theory of Computing (STOC), pages 431–444, 2018

    2018

  12. [20]

    R. Gmyr, K. Hinnenthal, C. Scheideler, and C. Sohler. Distributed monitoring of network properties: The power of hybrid networks. In Proc. of 44th International Colloqium on Algorithms, Languages, and Programming (ICALP 2017), pages 137:1–137:15, 2017

    2017

  13. [21]

    Halperin, S

    D. Halperin, S. Kandula, J. Padhye, P. Bahl, and D. Wetherall. Augmenting data center networks with multi-gigabit wireless links. In ACM SIGCOMM 2011 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pages 38–49, 2011

    2011

  14. [22]

    Henzinger, S

    M. Henzinger, S. Krinninger, and D. Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In 48th ACM Symposium on Theory of Computing (STOC), pages 489–498, 2016

    2016

  15. [23]

    Holzer and R

    S. Holzer and R. Wattenhofer. Optimal distributed all pairs shortest paths and applications. In 2012 ACM Symposium on Principles of Distributed Computing (PODC), pages 355–364, 2012

    2012

  16. [24]

    Huang, D

    C.-C. Huang, D. Nanongkai, and T. Saranurak. Distributed exact weighted all-pairs shortest paths in ˜O(n5/4) rounds. In 58th IEEE Symposium on Foundations of Computer Science (FOCS) , pages 168–179, 2017

    2017

  17. [25]

    D. Jung, C. Kolb, C. Scheideler, and J. Sundermeier. Competitive routing in hybrid communication networks. In 14th International Symposium on Algorithms and Experiments for Wireless Networks (ALGOSENSORS), 2018

    2018

  18. [26]

    Jurdzinski and K

    T. Jurdzinski and K. Nowicki. MST in o(1) rounds of congested clique. In Proc. of 29th ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), 2018

    2018

  19. [27]

    U. N. Kar and D. K. Sanyal. An overview of device-to-device communication in cellular networks. ICT Express, 4(3):203–208, 2018

    2018

  20. [28]

    C. Lenzen. Optimal deterministic routing and sorting on the congested clique. In Proc. 32nd Symp. on Principles of Distr. Comp. (PODC), pages 42–50, 2013

    2013

  21. [29]

    Lenzen and B

    C. Lenzen and B. Patt-Shamir. Fast routing table construction using small messages. In 45th ACM Symposium on Theory of Computing (STOC), pages 381–390, 2013

    2013

  22. [30]

    Lenzen and B

    C. Lenzen and B. Patt-Shamir. Fast partial distance estimation and applications. In 2015 ACM Sympo- sium on Principles of Distributed Computing (PODC), pages 153–162, 2015. 38

    2015

  23. [31]

    Lenzen and D

    C. Lenzen and D. Peleg. Efficient distributed source detection with limited bandwidth. In 2013 ACM Symposium on Principles of Distributed Computing (PODC), pages 375–382, 2013

    2013

  24. [32]

    Lotker, B

    Z. Lotker, B. Patt-Shamir, E. Pavlov, and D. Peleg. Minimum-weight spanning tree construction in o(log logn) communication rounds. SIAM Journal on Computing, 35(1):120–131, 2005

    2005

  25. [33]

    Nanongkai

    D. Nanongkai. Distributed approximation algorithms for weighted shortest paths. In 46th ACM Sym- posium on Symposium on Theory of Computing (STOC), pages 565–573, 2014

    2014

  26. [34]

    Peleg, L

    D. Peleg, L. Roditty, and E. Tal. Distributed algorithms for network diameter and girth. In 39th International on Colloquium Automata, Languages, and Programming (ICALP), Part II , pages 660– 672, 2012

    2012

  27. [35]

    Rossberg and G

    M. Rossberg and G. Schaefer. A survey on automatic configuration of virtual private networks. Com- puter Networks, 55(8):1684–1699, 2011

    2011

  28. [36]

    A. D. Sarma, S. Holzer, L. Kor, A. Korman, D. Nanongkai, G. Pandurangan, D. Peleg, and R. Watten- hofer. Distributed verification and hardness of distributed approximation.SIAM Journal on Computing, 41(5):1235–1265, 2012

    2012

  29. [37]

    J. P. Schmidt, A. Siegel, and A. Srinivasan. Chernoff-Hoeffding Bounds for Applications with Limited Independence. SIAM Journal on Discrete Mathematics, 8(2):223–250, 1995

    1995

  30. [38]

    A. Tell, W. Babalola, G. Kalebiala, and K. Chinta. Sd-wan: A modern hybrid-wan to enable digital transformation for businesses. IDC White Paper, April 2018

    2018

  31. [39]

    J. D. Ullman and M. Yannakakis. High-probability parallel transitive-closure algorithms. SIAM J. on Computing, 20(1):100–125, 1991. 39

    1991

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.