The Library
Simple, deterministic, constant-round coloring in the congested clique
Tools
Czumaj, Artur, Davies, Peter and Parter, Merav (2020) Simple, deterministic, constant-round coloring in the congested clique. In: 39th Annual ACM Symposium on Principles of Distributed Computing (PODC 2020), Virtual conference, 3-7 Aug 2020. Published in: PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing pp. 309-318. ISBN 9781450375825. doi:10.1145/3382734.3405751
|
PDF
WRAP-Simple-deterministic-constant-round-coloring-congested-clique-Czumaj-2020.pdf - Accepted Version - Requires a PDF viewer. Download (1266Kb) | Preview |
Official URL: https://doi.org/10.1145/3382734.3405751
Abstract
We settle the complexity of the (\Delta+1)-coloring and (\Delta+1)-list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. This matches the complexity of the recent breakthrough randomized constant-round (\Delta+1)-list coloring algorithm due to Chang et al. (PODC’19), and significantly improves upon the state-of-the-art O(log(\Delta))-round deterministic (\Delta+1)-coloring bound of Parter (ICALP’18).
A remarkable property of our algorithm is its simplicity. Whereas the state-of-the-art randomized algorithms for this problem are based on the quite involved local coloring algorithm of Chang et al. (STOC’18), our algorithm can be described in just a few lines. At a high level, it applies a careful derandomization of a recursive procedure which partitions the nodes and their respective palettes into separate bins. We show that after O(1) recursion steps, the remaining uncolored subgraph within each bin has linear size, and thus can be solved locally by collecting it to a single node. This algorithm can also be implemented in the Massively Parallel Computation (MPC) model provided that each machine has linear (in n) the number of nodes in the input graph) space.
We also show an extension of our algorithm to the MPC regime in which machines have sublinear space: we present the first deterministic (\Delta+1)-list coloring algorithm designed for sublinear-space MPC, which runs in O(log(\Delta + loglog(n)) rounds.
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 programs (Computer programs) , Parallel computers , Numbers, Random , Computable functions, Graph algorithms | ||||||||||||||||||
Journal or Publication Title: | PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing | ||||||||||||||||||
Publisher: | ACM | ||||||||||||||||||
ISBN: | 9781450375825 | ||||||||||||||||||
Official Date: | 31 July 2020 | ||||||||||||||||||
Dates: |
|
||||||||||||||||||
Page Range: | pp. 309-318 | ||||||||||||||||||
DOI: | 10.1145/3382734.3405751 | ||||||||||||||||||
Status: | Peer Reviewed | ||||||||||||||||||
Publication Status: | Published | ||||||||||||||||||
Reuse Statement (publisher, data, author rights): | "© ACM, 2020. 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 PUBLICATION, {VOL#, ISS#, (DATE)} http://doi.acm.org/10.1145/nnnnnn.nnnnnn" | ||||||||||||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||||||||||||
Date of first compliant deposit: | 22 July 2020 | ||||||||||||||||||
Date of first compliant Open Access: | 22 July 2020 | ||||||||||||||||||
RIOXX Funder/Project Grant: |
|
||||||||||||||||||
Conference Paper Type: | Paper | ||||||||||||||||||
Title of Event: | 39th Annual ACM Symposium on Principles of Distributed Computing (PODC 2020) | ||||||||||||||||||
Type of Event: | Conference | ||||||||||||||||||
Location of Event: | Virtual conference | ||||||||||||||||||
Date(s) of Event: | 3-7 Aug 2020 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year