Direct dependency-based determination of consistent global checkpoints
Building consistent global checkpoints that contain a given set of local checkpoints has been usually handled by using transitive dependency tracking. This imply the usage of a vector of integers piggybacked on each message of the computation (the vector size being given by the number of processes). In this paper we address the problem to get consistent global checkpoints including a given subset of local checkpoints tracking just direct dependencies. In that case application messages are required to piggyback one integer. An algorithm is proposed that takes a set of local checkpoints as an input and returns the minimum consistent global checkpoint, if any, including that set. Otherwise it returns the first consistent global checkpoint that follows this subset. Among the applications of the algorithm there are rollback-recovery and global predicate detection.
direct dependency transitive dependency predicate detection asynchronous systems checkpoint consistency communication-induced checkpointing uncoordinated checkpointing