Source-linked AI summary
Sparsifying Distributed Algorithms with Ramifications in Massively Parallel Computation and Centralized Local Computation
Mohsen Ghaffari, Jara Uitto
TL;DR
The paper addresses the difficulty of improving large-scale graph algorithms in MPC with strongly sublinear machine memory and of reducing MIS LCA queries below the Parnas–Ron paradigm. It sparsifies LOCAL algorithms by limiting the input volume relevant to each output, yielding improvements in both settings.
Problem
In MPC, known faster algorithms for the listed graph problems lose their advantage with strongly sublinear machine memory; known MIS LCAs also face a query-complexity barrier associated with simulating LOCAL algorithms by learning full neighborhoods.
Source: §1.1 · p. 3, §1.2 · p. 5Method
The paper devises sparse LOCAL algorithms whose outputs depend on a small locality volume of the input.
Source: §1 · p. 2Results
The sparsification approach yields significant improvements in both MPC and LCA settings.
Source: §1 · p. 2Takeaways & Limitations
Locality volume corresponds to per-node memory requirements in MPC and query complexity in LCA.
Source: §1 · p. 2The authors describe their discussion of the sparsified MIS approach as informal and imprecise.
Source: §3.2 · p. 9
Abstract
from arXiv · showhide
We introduce a method for sparsifying distributed algorithms and exhibit how it leads to improvements that go past known barriers in two algorithmic settings of large-scale graph processing: Massively Parallel Computation (MPC), and Local Computation Algorithms (LCA). - MPC with Strongly Sublinear Memory: Recently, there has been growing interest in obtaining MPC algorithms that are faster than their classic $O(\log n)$-round parallel counterparts for problems such as MIS, Maximal Matching, 2-Approximation of Minimum Vertex Cover, and $(1+\epsilon)$-Approximation of Maximum Matching. Currently, all such MPC algorithms require $\tilde{\Omega}(n)$ memory per machine. Czumaj et al. [STOC'18] were the first to handle $\tilde{\Omega}(n)$ memory, running in $O((\log\log n)^2)$ rounds. We obtain $\tilde{O}(\sqrt{\log \Delta})$-round MPC algorithms for all these four problems that work even when each machine has memory $n^{\alpha}$ for any constant $\alpha\in (0, 1)$. Here, $\Delta$ denotes the maximum degree. These are the first sublogarithmic-time algorithms for these problems that break the linear memory barrier. - LCAs with Query Complexity Below the Parnas-Ron Paradigm: Currently, the best known LCA for MIS has query complexity $\Delta^{O(\log \Delta)} poly(\log n)$, by Ghaffari [SODA'16]. As pointed out by Rubinfeld, obtaining a query complexity of $poly(\Delta\log n)$ remains a central open question. Ghaffari's bound almost reaches a $\Delta^{\Omega\left(\frac{\log \Delta}{\log\log \Delta}\right)}$ barrier common to all known MIS LCAs, which simulate distributed algorithms by learning the local topology, \`{a} la Parnas-Ron [TCS'07]. This barrier follows from the $\Omega(\frac{\log \Delta}{\log\log \Delta})$ distributed lower bound of Kuhn, et al. [JACM'16]. We break this barrier and obtain an MIS LCA with query complexity $\Delta^{O(\log\log \Delta)} poly(\log n)$.
1 Introduction and Related Work
The introduction proposes locality volume as a way to sparsify LOCAL algorithms, enabling improvements in both MPC and LCA. It presents results that address the strongly sublinear-memory MPC regime and move MIS LCA query complexity below the Parnas–Ron paradigm.
1 Introduction and Related Work
- Sparse LOCAL algorithms use small locality volume, which links the input elements affecting each output to per-node MPC memory and LCA query complexity.The output of a node depends on only a small part of the topology within its locality radius.Source: §1 · p. 2
1.1 Massively Parallel Computation (MPC)
- With strongly sublinear memory per machine, the paper gives faster-than-O(log n) MPC algorithms for four graph problems.The problems are MIS, maximal matching, (1 + ε)-approximation of maximum matching, and 2-approximation of minimum vertex cover.Source: §1.1 · p. 3
1.2 Local Computation Algorithms (LCA)
- The MIS LCA has query complexity Δ^O(log log Δ) poly(log n), improving on Ghaffari’s Δ^O(log Δ) poly(log n) bound while remaining short of poly(Δ log n).The introduction describes the older bound as approaching a barrier for LCAs that simulate LOCAL algorithms by learning a node’s full T-hop neighborhood.Source: §1.2 · p. 5
2 Warm Up: Matching Approximation
This warm-up sparsifies a distributed algorithm for constant-approximation maximum matching, then simulates it in MPC and LCA. Its small locality volume yields sublogarithmic MPC rounds with strongly sublinear memory and an LCA query bound below the Parnas-Ron paradigm.
Warm-up results
- The warm-up yields an ˜O(√log ∆)-round MPC algorithm with strongly sublinear memory and an LCA with query complexity ∆^O(√log ∆).The LCA query complexity is below the Parnas-Ron paradigm.Source: §2 · p. 6
Basic and sparse matching algorithms
- The matching process marks edges incident on high-degree vertices, adds isolated marked edges to the matching, and removes matched endpoints and high-degree vertices.The sparsified simulation retains a constant-approximation guarantee with high probability in the matching size.Source: §2 · pp. 6–7
Sparse distributed algorithm
- Each phase simulates iterations on a sparsified graph H formed as the union of independently sampled subgraphs, with sampling probabilities scaled by K = Θ(log ∆).Each sampled edge is subsequently subsampled to mark iteration-i edges, while vertices with excessive remaining degree in Hi are removed.Source: §2 · pp. 6–7
- Across Θ(log ∆) phases, each node’s behavior depends on at most ∆^Θ(√log ∆) other nodes and edges, despite a locality radius of Θ(log ∆).The smaller locality volume is the property used to obtain the MPC and LCA improvements.Source: §2 · pp. 6–7
LCA simulation
- For the LCA, a node’s phase oracle builds its R-hop neighborhood in H using at most ∆^3/2 base-graph queries, and recursive phase calls give total query complexity ∆^O(√log ∆).Each later phase makes at most ∆^5/2 calls to the preceding phase’s oracle.Source: §2 · p. 8
3 Maximal Independent Set (MIS) and Implications
This section develops sparsification-based simulations for MIS in low-memory MPC and LCA settings. It then extends the approach to maximal matching, minimum vertex cover, and approximate maximum matching.
3.1 Reviewing Ghaffari’s MIS Algorithm
- Ghaffari’s dynamic yields an MIS in O(log n) iterations and a nearly-maximal independent set after O(log ∆) iterations, leaving few nodes in small components.The remaining nodes can be handled more easily to complete the MIS.Source: §3.1 · p. 9
3.2 Sparsifying Ghaffari’s MIS Algorithm
- Each phase oversamples neighbors using their current probabilities, stalls nodes with large neighbor-probability sums, and estimates those sums through parallel sampling.Oversampling by 2^R captures vertices that could be sampled during the next R rounds; the resulting sparse graph supports phase simulation.Source: §3.2 · pp. 10–11
- With probability at least 1/∆^C, each node or a neighbor joins the MIS during T = c log ∆ iterations, and remaining components have O(log ∆ · n · ∆^4) nodes with probability at least 1 − 1/n^10.The per-node guarantee is independent of randomness outside its 2-hop neighborhood.Source: §3.2 · pp. 11–12
3.3 Constructing a Sparse Graph to Simulate a Phase of the Sparsified Algorithm
- The phase graph includes relevant good light nodes, represents relevant heavy nodes with degree-one copies, and labels vertices with phase randomness for local simulation.Given probability values and random bits, the graph can be constructed from each node’s 1-hop neighborhood; learning an R-hop neighborhood suffices to simulate the phase.Source: §3.3 · pp. 12–13
3.4 Simulation in the Low Memory MPC Model
- The low-memory MPC algorithm processes log log ∆ + 1 degree-threshold steps, and each phase neighborhood can be learned in O(log log ∆i) communication rounds while fitting machine memory.Each step removes vertices whose degree meets its threshold, reducing the maximum degree in the remaining graph.Source: §3.4 · p. 14
- With probability 1−1/n^10, the low-memory MPC algorithm computes MIS in O(√(log log n)) communication rounds.The theorem gives the stated round bound for the low-memory MPC model.Source: §3.4 · p. 15
3.5 Simulation in the LCA Model
- With probability 1−1/n^10, the LCA computes MIS with query complexity Δ^{O(√log Δ)} · log n.It simulates phase oracles whose query complexity grows by a factor of at most Δ^{9/8} per phase, then learns the remaining component.Source: §3.5 · p. 16
3.6 Implications on Other Problems
- An MIS algorithm on the line graph yields maximal matching and, by selecting its endpoints, a 2-approximation of minimum vertex cover.For LCA, this extension needs no extra effort; MPC simulates edge behavior without explicitly constructing the line graph to respect memory limits.Source: §3.6 · pp. 16–17
- For constant ε > 0, a constant number of maximal-matching calls extends the algorithm to a (1 + ε)-approximation of maximum matching in MPC and LCA without asymptotic complexity increase.The subgraphs are easy to identify in O(1) LOCAL rounds; the method follows McGregor.Source: §3.6 · p. 17
4 An Improved LCA for MIS
The section adapts the MIS algorithm for LCA simulation by recursively splitting phases and simulating them on sparse phase graphs. It obtains an MIS LCA with query complexity Δ^O(log log Δ) poly(log n).
4.1 Recursive Splitting to Subphases
- Recursive splitting modifies Algorithm 2 by dividing phases until their lengths are between 2 log log Δ and 4 log log Δ.Stalling thresholds are adjusted to the subphase length.Source: §4 · p. 17, §4.1 · p. 17
4.2 Bound on the Number of Iterations
- After T=c log Δ iterations, each node or one of its neighbors joins the MIS with probability at least 1−1/Δ^98, independently of randomness outside its 2-hop neighborhood.The remaining components have O(log Δ·n·Δ^4) nodes.Source: §4.2 · p. 17
4.3 Sparsification
- Recursive phase simulation has low query cost because short phases run on sparse graphs, whose R-hop neighborhoods are bounded.For phase lengths at most 4 log log Δ, the query complexity is 2^O(log^2 log Δ).Source: §4.3 · pp. 18–19
- Each phase graph H contains relevant good light nodes and degree-one copies of relevant heavy nodes, enabling simulation of the phase from its R-hop neighborhood.The graph also carries labels for the previous sampling probabilities and random bits.Source: §4.3 · p. 18
- The LCA computes an MIS with query complexity Δ^O(log log Δ) poly(log n), with probability 1−1/n^10.The analysis completes the remaining components after O(log Δ) iterations.Source: §4.3 · pp. 19–20
A.1 Proof of Theorem 3.1
The proof tracks golden iterations, in which a node has a constant probability of being removed, and shows that each node experiences many such iterations. It then bounds the size of the surviving set.
A.1 Proof of Theorem 3.1
- With probability at least 1−1/Δ^C, the degree estimate is below 2 when d_t(v)<0.4.The proof also bounds the chance that the estimate is at least four times the true value by e^(1/3)·(k/4), which is less than 1/Δ^C.Source: §A.1 · p. 23
- Each node has at least 0.05·T golden iterations over T=c·log Δ rounds with probability at least 1−1/Δ^C−2.In each golden round, the node is removed with constant probability.Source: §A.1 · p. 23
- When Δ^4≤n^α, the surviving set B has at most n/Δ^10 nodes with probability at least 1−1/n^10.The proof uses bounded dependencies, since each survival event depends on at most Δ^5 other nodes.Source: §A.1 · p. 24
A.2 Proof of Theorem 4.1
The proof adjusts the stalling analysis for phases of length R. It shows that degree falls quickly during a stalled phase and leaves the remainder of the proof analogous to Theorem 3.1.
A.2 Proof of Theorem 4.1
- In a stalled phase of length R, degree drops by a factor of at least 2^(R+1) across the phase under the stated conditions.At the phase's start, the degree is greater than 2^(2R−2), while its end degree is below 0.4·2^R.Source: §A.2 · p. 25
- Amortized across the phase, each iteration reduces d_i(v) by a factor below 0.65.The argument applies when v is stalling and d_i(v)≤0.4 for some iteration in the phase.Source: §A.2 · p. 25
- The rest of the proof follows the argument for Theorem 3.1 after this stalling adjustment.Source: §A.2 · p. 25