  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.
