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

Nazari, Yasamin

Sparse Hopsets in Congested Clique

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

Abstract

We give the first Congested Clique algorithm that computes a sparse hopset with polylogarithmic hopbound in polylogarithmic time. Given a graph G=(V,E), a (β,ε)-hopset H with "hopbound" β, is a set of edges added to G such that for any pair of nodes u and v in G there is a path with at most β hops in G ∪ H with length within (1+ε) of the shortest path between u and v in G. Our hopsets are significantly sparser than the recent construction of [Censor-Hillel et al., 2019], that constructs a hopset of size Õ (n^{3/2}), but with a smaller polylogarithmic hopbound. On the other hand, the previously known construction of sparse hopsets with polylogarithmic hopbound in the Congested Clique model, proposed by [Elkin and Neiman, 2018; Elkin and Neiman, 2019; Elkin and Neiman, 2019], all require polynomial rounds.
One tool that we use is an efficient algorithm that constructs an l-limited neighborhood cover, that may be of independent interest. Finally, as a side result, we also give a hopset construction in a variant of the low-memory Massively Parallel Computation model, with improved running time over existing algorithms.

BibTeX - Entry

@InProceedings{nazari:LIPIcs:2020:11820,
  author =	{Yasamin Nazari},
  title =	{{Sparse Hopsets in Congested Clique}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{34:1--34:16},
  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/11820},
  URN =		{urn:nbn:de:0030-drops-118207},
  doi =		{10.4230/LIPIcs.OPODIS.2019.34},
  annote =	{Keywords: Hopsets, Congested Clique, Shortest Paths, Massively Parallel Computation}
}

Keywords: Hopsets, Congested Clique, Shortest Paths, Massively Parallel Computation
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