Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model
Matching and MIS for Uniformly Sparse Graphs in the Low-Memory MPC Model
复制标题
DOI：
--
复制
发表时间：
2018-07
期刊：
影响因子：
--
通讯作者：
S. Brandt;Manuela Fischer;Jara Uitto
中科院分区：
文献类型：
--
作者：
S. Brandt;Manuela Fischer;Jara Uitto
大规模并行计算（MPC）模型是许多现代大规模并行计算框架的共同抽象，近年来得到了很多重视，特别是在经典图问题的背景下。令人不满意的是，目前所有的$\text{poly} (\log \log n)$ -round MPC算法似乎从根本上陷入了线性内存障碍：它们的效率关键依赖于每台机器的节点数量至少是线性的$n$。由于这不仅可能大得令人望而却步，而且还允许稀疏图的简单解决方案，我们对低内存MPC模型感兴趣，其中每台机器的空间被限制为强次线性，即$n^{\delta}$对于任何$0<\delta<1$。我们设计了一种度约简技术，将具有树性$\lambda$的图中的最大匹配和最大独立集约简为$O(\log^2 \log n)$轮中具有最大度$\text{poly}(\lambda)$的图中的相应问题。这就产生了$O\left(\log^2\log n + T(\text{poly} \lambda)\right)$ -round算法，其中$T(\Delta)$是最大度$\Delta$的图中最大匹配集和最大独立集的轮复杂度的$\Delta$依赖性。Ghaffari和Uitto同时进行的一项研究表明$T(\Delta)=O(\sqrt{\log \Delta})$。对于具有树性$\lambda=\text{poly}(\log n)$的图，这比Luby的$O(\log n)$ -round PRAM算法[STOC'85， JALG'86]几乎呈指数级提高，并构成了低内存MPC模型中的第一个$\text{poly} (\log \log n)$ -round最大匹配算法，从而打破了线性内存障碍。此前，由于Lattanzi等人[SPAA'11]，已知的唯一次多对数算法需要强超线性，即$n^{1+\Omega(1)}$，每台机器的内存。
The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale parallel computation frameworks and has recently gained a lot of importance, especially in the context of classic graph problems. Unsatisfactorily, all current $\text{poly} (\log \log n)$-round MPC algorithms seem to get fundamentally stuck at the linear-memory barrier: their efficiency crucially relies on each machine having space at least linear in the number $n$ of nodes. As this might not only be prohibitively large, but also allows for easy if not trivial solutions for sparse graphs, we are interested in the low-memory MPC model, where the space per machine is restricted to be strongly sublinear, that is, $n^{\delta}$ for any $0<\delta<1$. We devise a degree reduction technique that reduces maximal matching and maximal independent set in graphs with arboricity $\lambda$ to the corresponding problems in graphs with maximum degree $\text{poly}(\lambda)$ in $O(\log^2 \log n)$ rounds. This gives rise to $O\left(\log^2\log n + T(\text{poly} \lambda)\right)$-round algorithms, where $T(\Delta)$ is the $\Delta$-dependency in the round complexity of maximal matching and maximal independent set in graphs with maximum degree $\Delta$. A concurrent work by Ghaffari and Uitto shows that $T(\Delta)=O(\sqrt{\log \Delta})$. For graphs with arboricity $\lambda=\text{poly}(\log n)$, this almost exponentially improves over Luby's $O(\log n)$-round PRAM algorithm [STOC'85, JALG'86], and constitutes the first $\text{poly} (\log \log n)$-round maximal matching algorithm in the low-memory MPC model, thus breaking the linear-memory barrier. Previously, the only known subpolylogarithmic algorithm, due to Lattanzi et al. [SPAA'11], required strongly superlinear, that is, $n^{1+\Omega(1)}$, memory per machine.