Graph sparsification for derandomizing massively parallel computation with low space

Czumaj A, Davies P, Parter M. 2021. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms. 17(2), 16.

Download
OA MISMM-arxiv.pdf 587.40 KB

Journal Article | Published | English
Author
Czumaj, Artur; Davies, PeterIST Austria ; Parter, Merav
Department
Abstract
The Massively Parallel Computation (MPC) model is an emerging model that distills core aspects of distributed and parallel computation, developed as a tool to solve combinatorial (typically graph) problems in systems of many machines with limited space. Recent work has focused on the regime in which machines have sublinear (in n, the number of nodes in the input graph) space, with randomized algorithms presented for the fundamental problems of Maximal Matching and Maximal Independent Set. However, there have been no prior corresponding deterministic algorithms. A major challenge underlying the sublinear space setting is that the local space of each machine might be too small to store all edges incident to a single node. This poses a considerable obstacle compared to classical models in which each node is assumed to know and have easy access to its incident edges. To overcome this barrier, we introduce a new graph sparsification technique that deterministically computes a low-degree subgraph, with the additional property that solving the problem on this subgraph provides significant progress towards solving the problem for the original input graph. Using this framework to derandomize the well-known algorithm of Luby [SICOMP’86], we obtain O(log Δ + log log n)-round deterministic MPC algorithms for solving the problems of Maximal Matching and Maximal Independent Set with O(nɛ) space on each machine for any constant ɛ > 0. These algorithms also run in O(log Δ) rounds in the closely related model of CONGESTED CLIQUE, improving upon the state-of-the-art bound of O(log 2Δ) rounds by Censor-Hillel et al. [DISC’17].
Publishing Year
Date Published
2021-06-01
Journal Title
ACM Transactions on Algorithms
Volume
17
Issue
2
Article Number
16
ISSN
eISSN
IST-REx-ID

Cite this

Czumaj A, Davies P, Parter M. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms. 2021;17(2). doi:10.1145/3451992
Czumaj, A., Davies, P., & Parter, M. (2021). Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms. ACM. https://doi.org/10.1145/3451992
Czumaj, Artur, Peter Davies, and Merav Parter. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” ACM Transactions on Algorithms. ACM, 2021. https://doi.org/10.1145/3451992.
A. Czumaj, P. Davies, and M. Parter, “Graph sparsification for derandomizing massively parallel computation with low space,” ACM Transactions on Algorithms, vol. 17, no. 2. ACM, 2021.
Czumaj A, Davies P, Parter M. 2021. Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms. 17(2), 16.
Czumaj, Artur, et al. “Graph Sparsification for Derandomizing Massively Parallel Computation with Low Space.” ACM Transactions on Algorithms, vol. 17, no. 2, 16, ACM, 2021, doi:10.1145/3451992.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
2021-06-10
MD5 Checksum
a21c627683890c309a68f6389302c408


Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1912.05390

Search this title in

Google Scholar