| Abstract | : | We study the maintenance of dynamic graphs under batches of edge insertions and deletions in the massively parallel model of computation. In this model, the graph is stored on a number of machines, each having space strongly sub-linear with respect to the number of vertices. 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 setting corresponds to the gradual buildup of databases over time, while the goal of obtaining constant rounds of communication in the static setting have been elusive for problems as simple as connectivity of undirected graphs. We give data structures for handling batches of updates in constant rounds of communication for a wide range of fundamental problems in graph algorithms, including c-edge-connectivity for c <= 3, minimum spanning trees, and triangle counting. Furthermore, for many of the problems, we use further partitioning techniques to reduce the total communication to sub-linear per update/query batch without increasing the number of communication rounds. Our techniques combine sequential data structures for dynamic graphs, structural observations of graphs, as well as distributed data structures supporting parallel updates and queries in batch. 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. |
