The Library
Graph sparsification for derandomizing massively parallel computation with low space
Tools
Tools
Tools
Czumaj, Artur, Davies, Peter and Parter, Merav (2021) Graph sparsification for derandomizing massively parallel computation with low space. ACM Transactions on Algorithms, 17 (2). 16. doi:10.1145/3451992 ISSN 1549-6325.
|
PDF
WRAP-graph-sparsification-derandomizing-massively-parallel-computation-low space-Czumaj-2021.pdf - Accepted Version - Requires a PDF viewer. Download (1348Kb) | Preview |
Official URL: https://doi.org/10.1145/3451992
Abstract
The Massively Parallel Computation (MPC) model is an emerging model which 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
| Item Type: | Journal Article | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | |||||||||||||||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Distributed algorithms, Parallel algorithms , Graph algorithms , Numbers, Random, Computational complexity, Parallel processing (Electronic computers) | |||||||||||||||||||||
| Journal or Publication Title: | ACM Transactions on Algorithms | |||||||||||||||||||||
| Publisher: | ACM | |||||||||||||||||||||
| ISSN: | 1549-6325 | |||||||||||||||||||||
| Official Date: | 29 May 2021 | |||||||||||||||||||||
| Dates: |
|
|||||||||||||||||||||
| Volume: | 17 | |||||||||||||||||||||
| Number: | 2 | |||||||||||||||||||||
| Article Number: | 16 | |||||||||||||||||||||
| DOI: | 10.1145/3451992 | |||||||||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||||||||
| Publication Status: | Published | |||||||||||||||||||||
| Reuse Statement (publisher, data, author rights): | © ACM, 2021. 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 ACM Transactions on Algorithms, 17 (2). 16. http://doi.acm.org/10.1145/10.1145/3451992 | |||||||||||||||||||||
| Access rights to Published version: | Restricted or Subscription Access | |||||||||||||||||||||
| Copyright Holders: | Association for Computing Machinery (ACM) | |||||||||||||||||||||
| Date of first compliant deposit: | 8 June 2021 | |||||||||||||||||||||
| Date of first compliant Open Access: | 9 June 2021 | |||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||||||||||||||
| Is Part Of: | 1 | |||||||||||||||||||||
| 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
