Massively parallel approximate distance sketches

Michael Dinitz, Yasamin Nazari

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

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 [9]. 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.
Original languageEnglish
Title of host publication23rd International Conference on Principles of Distributed Systems, OPODIS 2019
EditorsP. Felber, R. Friedman, S. Gilbert, A. Miller
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771337
DOIs
Publication statusPublished - 1 Feb 2020
Externally publishedYes
Event23rd International Conference on Principles of Distributed Systems, OPODIS 2019 - Neuchatel, Switzerland
Duration: 17 Dec 201919 Dec 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969

Conference

Conference23rd International Conference on Principles of Distributed Systems, OPODIS 2019
Country/TerritorySwitzerland
CityNeuchatel
Period17/12/1919/12/19

Funding

This work supported is in part by NSF awards CCF-1464239 and CCF-1909111.

FundersFunder number
National Science FoundationCCF-1909111, CCF-1464239

    Fingerprint

    Dive into the research topics of 'Massively parallel approximate distance sketches'. Together they form a unique fingerprint.

    Cite this