2020

• Fabian Kuhn, Philipp Schneider
  Computing Shortest Paths and Diameter in the Hybrid Network Model.
  2020 39th ACM Symposium on Principles of Distributed Computing (PODC)
  » show abstract« hide abstract
  Abstract

  The HYBRID model, introduced in [Augustine et al., SODA '20], provides a theoretical foundation for networks that allow multiple communication modes. The model follows the principles of synchronous message passing, whereas nodes are allowed to use two fundamentally different communication modes. First, a local mode where nodes may exchange arbitrary information per round over edges of a local communication graph G (akin to the LOCAL model). Second, a global mode where every node may exchange O(log n) messages of size O(log n) bits per round with arbitrary nodes in the network. The HYBRID model intends to reflect the conditions of many real hybrid networks, where high-bandwidth but inherently local communication is combined with highly flexible global communication with restricted bandwidth. We continue to explore the power and limitations of the HYBRID model by investigating the complexity of computing shortest paths and diameter of the local communication graph G. We show that the all pair shortest paths problem can be solved exactly in [EQUATION] rounds, which improves on the previous Õ(n2/3) round algorithm and closes the gap to the known [EQUATION] lower bound (up to polylog n factors). Furthermore, we give constant approximations for the k-source shortest paths problem (k-SSP) with runtime [EQUATION], provided that k is sufficiently large. As k-SSP has a lower bound of [EQUATION] even for large approximation ratios, our k-SSP algorithms are almost tight for large enough k. In the case of a single source we give an exact Õ(n2/5)-round algorithm, improving on the known [EQUATION]-round algorithm for graphs with large diameter D. For the diameter problem we provide algorithms with complexities Õ(n1/3/ε) and Õ(n0.397/ε) and approximation factors (3/2 + ε) and (1 + ε), respectively. On the negative side, we demonstrate that the classical 2-party set-disjointness framework can be adapted for the HYBRID model to prove a lower bound of [EQUATION] rounds for computing the diameter exactly. For the weighted diameter problem the same holds for computing (2 − ε)-approximations for any ε > 0.
• John Augustine, Kristian Hinnenthal, Fabian Kuhn, Christian Scheideler, Philipp Schneider
  Shortest Paths in a Hybrid Network Model
  2020 31st ACM-SIAM Symp. on Discrete Algorithms (SODA)
  » show abstract« hide abstract
  Abstract

  We introduce a communication model for hybrid networks, where nodes have access to two different communication modes: a local mode where (like in traditional networks) communication is only possible between specific pairs of nodes, and a global mode where (like in overlay networks) communication between any pair of nodes is possible. Typically, communication over short-range connections is cheaper and can be done at a much higher rate than communication via the overlay network. Therefore, we are focusing on the LOCAL model for the local connections where nodes can exchange an unbounded amount of information per round. For the global communication we assume the so-called nodecapacitated clique model, where in each round every node can exchange O(log n)-bit messages with O(log n) arbitrary nodes. We explore the impact of hybrid communication on the complexity of distributed algorithms by studying the problem of computing shortest paths in the graph given by the local connections. We present the following results. For the all-pairs shortest paths problem, we show that an exact solution can be computed in time Õ (n2/3), and that approximate solutions can be computed in time but not faster. For the single-source shortest paths problem an exact solution can be computed in time , where SPD denotes the shortest path diameter. Furthermore, a (l + o(1))-approximate solution can be computed in time . Finally, we show that for every constant ε > 0, it is possible to compute an O(1)-approximate solution in time.

2017

• Fabian Kuhn, Philipp Schneider
  Broadcasting in an Unreliable SINR Model
  2017 21st Conference on Principles of Distributed Systems (OPODIS) , pages: 3:1 - 3:21