  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+\epsilon}$ 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.
