2019/12/11 by Artur Czumaj, Czumaj, Artur, Peter Maxwell Davies +3
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1912.05390
openalex publication_date 2019/12/11 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
The Massively Parallel Computation (MPC) model is an emerging model which\ndistills core aspects of distributed and parallel computation. It has been\ndeveloped as a tool to solve (typically graph) problems in systems where the\ninput is distributed over many machines with limited space. Recent work has\nfocused on the regime in which machines have sublinear (in n, the number of\nnodes in the input graph) memory, with randomized algorithms presented for\nfundamental graph problems of Maximal Matching and Maximal Independent Set.\nHowever, there have been no prior corresponding \deterministic\nalgorithms.\n A major challenge underlying the sublinear space setting is that the local\nspace of each machine might be too small to store all the edges incident to a\nsingle node. This poses a considerable obstacle compared to the classical\nmodels in which each node is assumed to know and have easy access to its\nincident edges. To overcome this barrier we introduce a new \graph\nsparsification technique that \deterministically computes a low-degree\nsubgraph with additional desired properties. Using this framework to\nderandomize the well-known randomized algorithm of Luby [SICOMP'86], we obtain\nO(\log \Δ+\log\log n)-round \deterministic MPC algorithms for\nsolving the fundamental problems of \Maximal Matching and \Maximal\nIndependent Set with O(n\ε) space on each machine for any constant\n\ε > 0. Based on the recent work of Ghaffari et al. [FOCS'18], this\nadditive O(\log\log n) factor is \conditionally essential. These\nalgorithms can also be shown to run in O(\log \Δ) rounds in the closely\nrelated model of congc, improving upon the state-of-the-art bound of O(\log2\n\Δ) rounds by Censor-Hillel et al. [DISC'17].\n