The Library
Graph sparsification for derandomizing massively parallel computation with low space
Tools
Tools
Tools
Czumaj, Artur, Davies, Peter and Parter, Merav (2020) Graph sparsification for derandomizing massively parallel computation with low space. In: 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020), Virtual, USA, 15-17 Jul 2020. Published in: SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures pp. 175-185. ISBN 9781450369350. doi:10.1145/3350755.3400282
|
PDF
WRAP-Graph-sparsification-derandomizing-massively-parallel-low-spaces-Czumaj-2020.pdf - Accepted Version - Requires a PDF viewer. Download (1830Kb) | Preview |
Official URL: https://doi.org/10.1145/3350755.3400282
Abstract
Massively Parallel Computation (MPC) is an emerging model which distills core aspects of distributed and parallel computation. It was developed as a tool to solve (typically graph) problems in systems where input is distributed over many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. There are, however, no prior corresponding deterministic algorithms.
A major challenge in the sublinear space setting is that the local space of each machine may be too small to store all the edges incident to a single node. To overcome this barrier we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph with additional desired properties: degrees in the subgraph are sufficiently small that nodes’ neighborhoods can be stored on single machines, and solving the problem on the subgraph provides significant global progress towards solving the problem for the original input graph.
Using this framework to derandomize the well-known randomized algorithm of Luby [SICOMP’86], we obtain O(log(\Delta) + loglog(n))- round deterministic MPC algorithms for solving the fundamental problems of Maximal Matching and Maximal Independent Set with O(n epsilon) space on each machine for any constant epsilon > 0. Based on the recent work of Ghaffari et al. [FOCS’18], this additive O(loglog(n)) factor is conditionally essential. These algorithms can also be shown
to run in O(log(\Delta)) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log^2(\Delta)) rounds by Censor-Hillel et al. [DISC’17].
| Item Type: | Conference Item (Paper) | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||||||||||||
| Divisions: | Faculty of Science > Computer Science | ||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Parallel computers, Distributed algorithms, Graph algorithms | ||||||||||||||||||
| Journal or Publication Title: | SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures | ||||||||||||||||||
| Publisher: | ACM | ||||||||||||||||||
| ISBN: | 9781450369350 | ||||||||||||||||||
| Official Date: | July 2020 | ||||||||||||||||||
| Dates: |
|
||||||||||||||||||
| Date of first compliant deposit: | 23 July 2020 | ||||||||||||||||||
| Page Range: | pp. 175-185 | ||||||||||||||||||
| DOI: | 10.1145/3350755.3400282 | ||||||||||||||||||
| Status: | Peer Reviewed | ||||||||||||||||||
| Publication Status: | Published | ||||||||||||||||||
| Publisher Statement: | Copyright © 2020 ACM.This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in SPAA '20: Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures, July 2020 http://doi.acm.org/10.1145/3350755.3400282" | ||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
||||||||||||||||||
| Conference Paper Type: | Paper | ||||||||||||||||||
| Title of Event: | 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020) | ||||||||||||||||||
| Type of Event: | Conference | ||||||||||||||||||
| Location of Event: | Virtual, USA | ||||||||||||||||||
| Date(s) of Event: | 15-17 Jul 2020 | ||||||||||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
