Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
Parallel Batch-Dynamic Graphs: Algorithms and Lower Bounds
复制标题
DOI：
10.1137/1.9781611975994.79
复制
发表时间：
2019-08
期刊：
影响因子：
--
通讯作者：
D. Durfee;Laxman Dhulipala;Janardhan Kulkarni;Richard Peng;Saurabh Sawlani;Xiaorui Sun
中科院分区：
文献类型：
--
作者：
D. Durfee;Laxman Dhulipala;Janardhan Kulkarni;Richard Peng;Saurabh Sawlani;Xiaorui Sun
本文研究了在大规模并行计算模型下，在批量边插入和删除的情况下，图的性质的动态维护问题。在这种情况下，图被存储在许多机器上，每个机器都有关于顶点数的强次线性空间，即对于某个常数$0 < \n < 1$有$n^\n $。我们的目标是处理成批的更新和查询，其中每批数据都适合一台机器上的恒定轮并行计算，以及减少机器之间的总通信。这一目标对应于随着时间的推移逐渐建立数据库，而在静态环境中获得恒定的问题通信回合的目标对于像无向图连通性这样简单的问题来说是难以捉摸的。我们给出了一个算法的动态图连接在此设置恒定的通信轮和通信成本几乎线性的批量大小。我们的技术结合联合收割机一个新的图形收缩技术，一个独立的随机样本提取器相关的样本，以及分布式数据结构，支持并行更新和查询批量。我们还说明了动态算法在MPC模型中的能力，表明自适应连接问题的批处理版本在集中式设置中是$\mathsf{P}$-完全的，但是子线性大小的批处理可以在恒定数量的轮中处理。由于我们的方法的广泛适用性，我们相信它代表了一个实际的动机解决目前的困难，设计更有效的大规模并行静态图算法。
In this paper we study the problem of dynamically maintaining graph properties under batches of edge insertions and deletions in the massively parallel model of computation. In this setting, the graph is stored on a number of machines, each having space strongly sublinear with respect to the number of vertices, that is, $n^\epsilon$ for some constant $0 < \epsilon < 1$. Our goal is to handle batches of updates and queries where the data for each batch fits onto one machine in constant rounds of parallel computation, as well as to reduce the total communication between the machines. This objective corresponds to the gradual buildup of databases over time, while the goal of obtaining constant rounds of communication for problems in the static setting has been elusive for problems as simple as undirected graph connectivity. We give an algorithm for dynamic graph connectivity in this setting with constant communication rounds and communication cost almost linear in terms of the batch size. Our techniques combine a new graph contraction technique, an independent random sample extractor from correlated samples, as well as distributed data structures supporting parallel updates and queries in batches. We also illustrate the power of dynamic algorithms in the MPC model by showing that the batched version of the adaptive connectivity problem is $\mathsf{P}$-complete in the centralized setting, but sub-linear sized batches can be handled in a constant number of rounds. Due to the wide applicability of our approaches, we believe it represents a practically-motivated workaround to the current difficulties in designing more efficient massively parallel static graph algorithms.