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.OPODIS.2019.35
URN: urn:nbn:de:0030-drops-118216
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11821/
Go to the corresponding LIPIcs Volume Portal

Dinitz, Michael ; Nazari, Yasamin

Massively Parallel Approximate Distance Sketches

pdf-format:
LIPIcs-OPODIS-2019-35.pdf (0.5 MB)

Abstract

Data structures that allow efficient distance estimation (distance oracles, distance sketches, etc.) have been extensively studied, and are particularly well studied in centralized models and classical distributed models such as CONGEST. We initiate their study in newer (and arguably more realistic) models of distributed computation: the Congested Clique model and the Massively Parallel Computation (MPC) model. We provide efficient constructions in both of these models, but our core results are for MPC. In MPC we give two main results: an algorithm that constructs stretch/space optimal distance sketches but takes a (small) polynomial number of rounds, and an algorithm that constructs distance sketches with worse stretch but that only takes polylogarithmic rounds.
Along the way, we show that other useful combinatorial structures can also be computed in MPC. In particular, one key component we use to construct distance sketches are an MPC construction of the hopsets of [Elkin and Neiman, 2016]. This result has additional applications such as the first polylogarithmic time algorithm for constant approximate single-source shortest paths for weighted graphs in the low memory MPC setting.

BibTeX - Entry

@InProceedings{dinitz_et_al:LIPIcs:2020:11821,
  author =	{Michael Dinitz and Yasamin Nazari},
  title =	{{Massively Parallel Approximate Distance Sketches}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11821},
  URN =		{urn:nbn:de:0030-drops-118216},
  doi =		{10.4230/LIPIcs.OPODIS.2019.35},
  annote =	{Keywords: Distance Sketches, Massively Parallel Computation, Distance Oracles, Single-Source Shortest Paths}
}

Keywords: Distance Sketches, Massively Parallel Computation, Distance Oracles, Single-Source Shortest Paths
Collection: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Issue Date: 2020
Date of publication: 11.02.2020

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