论文标题
您可以更新MST？ （用于集群计算的动态算法）
How fast can you update your MST? (Dynamic algorithms for cluster computing)
论文作者
论文摘要
想象一下，一个由$ k $ - 机器模型或大量并行计算模型描述的计算机群体正在处理的大图。但是，该图不是静态的。相反，它正在接收不断的更新流。群集可以处理更新流的速度？我们想在本文中提出的基本问题是，我们是否可以足够快地更新图表以跟上流。我们专门关注维护最小生成树（MST）的问题，并为$ k $ - 机器人模型提供算法，该算法可以处理$ o（k）$ graph更新，每$ o（1）$ rounds具有很高的可能性。 （这些结果将延续到大规模并行计算（MPC）模型。）我们还显示了一个下限，即，在$ o（1）$ nounds中不可能处理$ k^{1+ε} $更新。因此，我们对群集可以在维护MST时可以对图形修改的响应的速度响应的速度几乎紧密地答案。
Imagine a large graph that is being processed by a cluster of computers, e.g., described by the $k$-machine model or the Massively Parallel Computation Model. The graph, however, is not static; instead it is receiving a constant stream of updates. How fast can the cluster process the stream of updates? The fundamental question we want to ask in this paper is whether we can update the graph fast enough to keep up with the stream. We focus specifically on the problem of maintaining a minimum spanning tree (MST), and we give an algorithm for the $k$-machine model that can process $O(k)$ graph updates per $O(1)$ rounds with high probability. (And these results carry over to the Massively Parallel Computation (MPC) model.) We also show a lower bound, i.e., it is impossible to process $k^{1+ε}$ updates in $O(1)$ rounds. Thus we provide a nearly tight answer to the question of how fast a cluster can respond to a stream of graph modifications while maintaining an MST.
