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.42
URN: urn:nbn:de:0030-drops-113491
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11349/
Go to the corresponding LIPIcs Volume Portal

Dinitz, Michael ; Nazari, Yasamin

Brief Announcement: Massively Parallel Approximate Distance Sketches

pdf-format:
LIPIcs-DISC-2019-42.pdf (0.3 MB)

Abstract

Data structures that allow efficient distance estimation have been extensively studied both in centralized models and classical distributed models. 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. 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 is 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:2019:11349,
  author =	{Michael Dinitz and Yasamin Nazari},
  title =	{{Brief Announcement: Massively Parallel Approximate Distance Sketches}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{42:1--42:3},
  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/11349},
  URN =		{urn:nbn:de:0030-drops-113491},
  doi =		{10.4230/LIPIcs.DISC.2019.42},
  annote =	{Keywords: Distance Sketches, Massively Parallel Computation, Congested Clique}
}

Keywords: Distance Sketches, Massively Parallel Computation, Congested Clique
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