Czumaj, Artur, Davies, Peter and Parter, Merav (2021) Improved deterministic (Δ + 1)-coloring in low-space MPC. In: 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021), Virtual, Italy, 26-30 Jul 2021. Published in: PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing pp. 469-479. ISBN 9781450385480. doi:10.1145/3465084.3467937
Preview |
PDF
WRAP-improved-deterministic(Δ + 1)-coloring-low-space-MPC-Czumaj-2021.pdf - Accepted Version - Requires a PDF viewer. Download (1MB) | Preview |
Abstract
We present a deterministic O(log log log n)-round low-space Massively Parallel Computation (MPC) algorithm for the classical problem of (Δ + 1)-coloring on n-vertex graphs. In this model, every machine has sublinear local space of size n^b for any arbitrary constant b ∈ (0, 1). Our algorithm works under the relaxed setting where each machine is allowed to perform exponential local computations, while respecting the n^b space and bandwidth limitations.
Our key technical contribution is a novel derandomization of the ingenious (Δ + 1)-coloring local algorithm by Chang-Li-Pettie (STOC 2018, SIAM J. Comput. 2020). The Chang-Li-Pettie algorithm runs in T(n) = poly(log log n) rounds, which sets the state-of-the-art randomized round complexity for the problem in the local model. Our derandomization employs a combination of tools, notably pseudorandom generators (PRG) and bounded-independence hash functions.
The achieved round complexity of O(log log log n) rounds matches the bound of log(T(n)), which currently serves an upper bound barrier for all known randomized algorithms for locally-checkable problems in this model. Furthermore, no deterministic sublogarithmic low-space MPC algorithms for the (Δ + 1)-coloring problem have been known before.
| Item Type: | Conference Item (Paper) |
|---|---|
| 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): | Parallel algorithms, Distributed algorithms , Graph coloring , Graph algorithms, Numbers, Random, Random number generators |
| Journal or Publication Title: | PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing |
| Publisher: | ACM |
| ISBN: | 9781450385480 |
| Official Date: | 21 July 2021 |
| Dates: | Date Event 21 July 2021 Published 30 April 2021 Accepted |
| Page Range: | pp. 469-479 |
| DOI: | 10.1145/3465084.3467937 |
| Status: | Peer Reviewed |
| Publication Status: | Published |
| Re-use Statement: | © 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 Proceedings of the 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021) http://doi.acm.org/10.1145/nnnnnn.nnnnn |
| Access rights to Published version: | Restricted or Subscription Access |
| Date of first compliant deposit: | 8 June 2021 |
| Date of first compliant Open Access: | 9 June 2021 |
| RIOXX Funder/Project Grant: | Project/Grant ID RIOXX Funder Name Funder ID EP/V01305X/1 [EPSRC] Engineering and Physical Sciences Research Council |
| Conference Paper Type: | Paper |
| Title of Event: | 40th Annual ACM Symposium on Principles of Distributed Computing (PODC 2021) |
| Type of Event: | Conference |
| Location of Event: | Virtual, Italy |
| Date(s) of Event: | 26-30 Jul 2021 |
| Related URLs: | |
| URI: | https://wrap.warwick.ac.uk/153753/ |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |