Method for software error recovery using consistent global checkpoints

A method for operation of a computer system executing a plurality of processes, P.sub.i, where i is the process identification, and for recovering from an error in said system, each of said processes capable of inter-process communication, and each of said processes capable of performing periodic local checkpoints, where C.sub.i,x represents the x.sup.th checkpoint of process P.sub.i, and wherein said inter-process communication and periodic local checkpoints define a checkpoint and communication pattern, the method comprising the steps of:

• creating a rollback dependency graph representing said checkpoint and communication pattern, said rollback dependency graph comprising nodes and edges, wherein said nodes represent said periodic local checkpoints and said edges represent rollback dependency of said periodic local checkpoints;
• defining a target set S of local checkpoints, each from a different process;
• determining a set S.sub.next of local checkpoints such that S.sub.next ={C.sub.i,x+1 :C.sub.i,x .di-elect cons.S};
• performing a reachability search on said rollback dependency graph starting from each node representing a local checkpoint in S.sub.next and marking each reachable node in said rollback dependency graph;
• and
• for each process P.sub.i, rolling back execution of the process to the most recent checkpoint of the process which is represented by an unmarked node in said rollback dependency graph.

A method for operation of a computer system executing a plurality of processes and for recovering from an error in said system, each of said processes capable of inter-process communication, and each of said processes capable of performing periodic local checkpoints, wherein said inter-process communication and periodic local checkpoints define a checkpoint and communication pattern, the method comprising the steps of:

• creating a rollback dependency graph representing said checkpoint and communication pattern, said rollback dependency graph comprising nodes and directed edges, wherein said nodes represent said periodic local checkpoints and said directed edges represent rollback dependency of said periodic local checkpoints;
• defining a target set of local checkpoints, each from a different process;
• performing a reverse reachability search on said rollback dependency graph starting from each node representing a local checkpoint in said target set and marking each reachable node in said rollback dependency graph;
• and
• for each process which has a checkpoint represented by a marked node in said rollback dependency graph, rolling back execution of the process to the most recent checkpoint of the process which is represented by a marked node in said rollback dependency graph.

A method for operation of a computer system executing a plurality of processes, P.sub.i, where i is the process identification, and for recovering from an error in said computer system, each of said processes capable of inter-process communication, and each of said processes capable of performing periodic local checkpoints, where C.sub.i,x represents the xth checkpoint of process P.sub.i, and wherein said inter-process communication and periodic local checkpoints define a checkpoint and communication pattern, the method comprising the steps of:

• each of said processes locally maintaining dependency information, said dependency information representing said checkpoint and communication pattern;
• defining a target set of local checkpoints, each from a different process;
• upon receipt of an action request, each of said processes P.sub.i locally determining a checkpoint C.sub.i,x using said locally maintained dependency information, wherein C.sub.i,x is a checkpoint in a maximum consistent global checkpoint including said target set of checkpoints;
• and
• each of said processes P.sub.i rolling back to the checkpoint C.sub.i,x determined by the process.

A method for operation of a computer system, executing a plurality of processes, P.sub.i, where i is the process identification, and for recovering from an error in said system, each of said processes capable of inter-process communication, and each of said processes capable of performing periodic local checkpoints, where C.sub.i,x represents the xth checkpoint of process P.sub.i, and wherein said inter-process communication and periodic local checkpoints define a checkpoint and communication pattern, the method comprising the steps of:

• each of said processes locally maintaining dependency information, said dependency information representing said checkpoint and communication pattern;
• defining a target set of local checkpoints, each from a different process;
• upon receipt of an action request, each of said processes P.sub.i locally determining a checkpoint C.sub.i,x using said locally maintained dependency information, wherein C.sub.i,x is a checkpoint in a minimum consistent global checkpoint including said target set of checkpoints;
• and
• each of said processes P.sub.i rolling back to the checkpoint C.sub.i,x determined by the process.