License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2019.11
URN: urn:nbn:de:0030-drops-113183
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11318/
Go to the corresponding LIPIcs Volume Portal

Chechik, Shiri ; Mukhtar, Doron

Reachability and Shortest Paths in the Broadcast CONGEST Model

pdf-format:
LIPIcs-DISC-2019-11.pdf (0.4 MB)

Abstract

In this paper we study the time complexity of the single-source reachability problem and the single-source shortest path problem for directed unweighted graphs in the Broadcast CONGEST model. We focus on the case where the diameter D of the underlying network is constant.
We show that for the case where D = 1 there is, quite surprisingly, a very simple algorithm that solves the reachability problem in 1(!) round. In contrast, for networks with D = 2, we show that any distributed algorithm (possibly randomized) for this problem requires Omega(sqrt{n/ log{n}}) rounds. Our results therefore completely resolve (up to a small polylog factor) the complexity of the single-source reachability problem for a wide range of diameters.
Furthermore, we show that when D = 1, it is even possible to get an almost 3 - approximation for the all-pairs shortest path problem (for directed unweighted graphs) in just 2 rounds. We also prove a stronger lower bound of Omega(sqrt{n}) for the single-source shortest path problem for unweighted directed graphs that holds even when the diameter of the underlying network is 2. As far as we know this is the first lower bound that achieves Omega(sqrt{n}) for this problem.

BibTeX - Entry

@InProceedings{chechik_et_al:LIPIcs:2019:11318,
  author =	{Shiri Chechik and Doron Mukhtar},
  title =	{{Reachability and Shortest Paths in the Broadcast CONGEST Model}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Jukka Suomela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11318},
  URN =		{urn:nbn:de:0030-drops-113183},
  doi =		{10.4230/LIPIcs.DISC.2019.11},
  annote =	{Keywords: Distributed algorithms, Broadcast CONGEST, distance estimation, small diameter}
}

Keywords: Distributed algorithms, Broadcast CONGEST, distance estimation, small diameter
Collection: 33rd International Symposium on Distributed Computing (DISC 2019)
Issue Date: 2019
Date of publication: 08.10.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI