Rollback algorithm and crash recovery based on fault-sensitive graphs

Extended graph-oriented distributed programming model (ExGOM) provides a system architecture to support dynamic configuration. Dynamic configuration involves system expansion and shrink during execution, upgrading while running, and reconfiguration after a fault occurs. One of the problems in reconfiguration is how to recover the system to the original states that exist just before the occurrence of faults. An asynchronous rollback algorithm and a crash recovery mechanism based on fault-sensitive graphs are proposed. The issue of multiple faulty processes on a single transient faulty host is addressed. Compared with other asynchronous rollback and recovery algorithms, the algorithm could make the region of faults localized and the only fault-sensitive nodes are rolled back. This results in a minimized system overhead.