  Reconfiguration schedules, i.e., sequences that gradually transform one
solution of a problem to another while always maintaining feasibility, have
been extensively studied. Most research has dealt with the decision problem of
whether a reconfiguration schedule exists, and the complexity of finding one. A
prime example is the reconfiguration of vertex covers. We initiate the study of
batched vertex cover reconfiguration, which allows to reconfigure multiple
vertices concurrently while requiring that any adversarial reconfiguration
order within a batch maintains feasibility. The latter provides robustness,
e.g., if the simultaneous reconfiguration of a batch cannot be guaranteed. The
quality of a schedule is measured by the number of batches until all nodes are
reconfigured, and its cost, i.e., the maximum size of an intermediate vertex
cover.
  To set a baseline for batch reconfiguration, we show that for graphs
belonging to one of the classes $\{\mathsf{cycles, trees, forests, chordal,
cactus, even\text{-}hole\text{-}free, claw\text{-}free}\}$, there are schedules
that use $O(\varepsilon^{-1})$ batches and incur only a $1+\varepsilon$
multiplicative increase in cost over the best sequential schedules. Our main
contribution is to compute such batch schedules in $O(\varepsilon^{-1}\log^*
n)$ distributed time, which we also show to be tight. Further, we show that
once we step out of these graph classes we face a very different situation.
There are graph classes on which no efficient distributed algorithm can obtain
the best (or almost best) existing schedule. Moreover, there are classes of
bounded degree graphs which do not admit any reconfiguration schedules without
incurring a large multiplicative increase in the cost at all.
