Massively parallel algorithms for finding well-connected components in sparse graphs

Sepehr Assadi, Xiaorui Sun, Omri Weinstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

30 Scopus citations

Abstract

Massively parallel computation (MPC) algorithms for graph problems have witnessed a resurgence of interest in recent years. Despite major progress for numerous graph problems however, the complexity of the sparse graph connectivity problem in this model has remained elusive: While classical logarithmic-round PRAM algorithms for finding connected components in any n-vertex graph have been known for more than three decades (and imply the same bounds for MPC model), no o(log n)-round MPC algorithms are known for this task with truly sublinear in n memory per machine (which is the only interesting regime for sparse graphs with O(n) edges). It is conjectured that an o(log n)-round algorithm for connectivity on general sparse graphs with n1- (1) per-machine memory may not exist, a conjecture that also forms the basis for multiple conditional hardness results on the round complexity of other problems in the MPC model. We take an opportunistic approach towards the sparse graph connectivity problem by designing an algorithm with improved performance in terms of the connectivity structure of the input graph. Formally, we design an MPC algorithm that finds all connected components with spectral gap at least in a graph in O(log log n + log(1/)) MPC rounds and n memory per machine for any constant (0,1). While this algorithm still requires (log n) rounds in the worst-case, it achieves an exponential round reduction on "well-connected'' components with 1/polylog(n) using only n memory per machine and (n) total memory, and still operates in o(log n)l rounds even when = 1/no(1). En-route to our main result, we design a new distributed data structure for performing independent random walks from all vertices simultaneously, as well as a new leader-election algorithm with exponentially faster round complexity on random graphs.

Original languageEnglish (US)
Title of host publicationPODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing
PublisherAssociation for Computing Machinery
Pages461-470
Number of pages10
ISBN (Electronic)9781450362177
DOIs
StatePublished - Jul 16 2019
Externally publishedYes
Event38th ACM Symposium on Principles of Distributed Computing, PODC 2019 - Toronto, Canada
Duration: Jul 29 2019Aug 2 2019

Publication series

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Conference

Conference38th ACM Symposium on Principles of Distributed Computing, PODC 2019
Country/TerritoryCanada
CityToronto
Period7/29/198/2/19

All Science Journal Classification (ASJC) codes

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications

Keywords

  • Random walk
  • Sparse connectivity
  • Spectral gap

Fingerprint

Dive into the research topics of 'Massively parallel algorithms for finding well-connected components in sparse graphs'. Together they form a unique fingerprint.

Cite this