US5630047A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for software error recovery using consistent global checkpoints
Assignee: Nokia of America Corp
•
Filing: 1995-09-12
•
Granted: 1997-05-13
•
Expires: 2015-09-12
Abstract
Abstract Disclosed is a method for error recovery in a multiprocessing computer system of the type in which each of the processes periodically takes checkpoints. In the event of a failure, a process can be rolled back to a prior checkpoint, and execution can continue from the checkpointed state. A monitor process monitors the execution of the processes. Upon the occurrence of a failure, a target set of checkpoints is identified, and the maximum consistent global checkpoint, which includes the target set of checkpoints, is computed. Each of the processes is rolled back to an associated checkpoint in the consistent global checkpoint. Upon a subsequent occurrence of the same failure, a second set of checkpoints is identified, and the minimum consistent global checkpoint, which includes the target set of checkpoints, is computed. Each of the processes is rolled back to an associated checkpoint in the consistent global checkpoint. Upon another occurrence of the same failure, the system is rolled back further to a coordinated checkpoint. Also disclosed are novel methods for calculating the minimum and maximum consistent global checkpoints. In accordance with one embodiment, the minimum and maximum consistent global checkpoints are calculated by a central process. In accordance with another embodiment, the minimum and maximum consistent global checkpoints are calculated in a distributed fashion by each of the individual processes.
Inventors
- 👤 Yi-Min Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 17:53
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1402; G06F11/1415; G06F11/1438; G06F11/1479
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
137 words
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, the method comprising the steps of: in response to an occurrence of said error: defining a first set of local checkpoints; determining a maximum consistent global checkpoint including said first set of local checkpoints; rolling back each of said processes to an associated checkpoint in said maximum consistent global checkpoint; in response to a subsequent occurrence of said error: defining a second set of local checkpoints; determining a minimum consistent global checkpoint including said second set of local checkpoints; and rolling back each of said processes to an associated checkpoint in said minimum consistent global checkpoint.
Claim 2
Independent Claim
137 words
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, the method comprising the steps of: in response to an occurrence of said error: defining a first set of local checkpoints; determining a maximum consistent global checkpoint including said first set of local checkpoints; rolling back each of said processes to an associated checkpoint in said maximum consistent global checkpoint; in response to a subsequent occurrence of said error: defining a second set of local checkpoints; determining a minimum consistent global checkpoint including said second set of local checkpoints; and rolling back each of said processes to an associated checkpoint in said minimum consistent global checkpoint.
Claim 3
Dependent Claim
34 words
The method of claim 1 further comprising the step of: in response to an occurrence of said error occurring after said subsequent occurrence: rolling back each of said processes to an associated coordinated checkpoint.
Claim 4
Dependent Claim
17 words
The method of claim 1 wherein said maximum consistent global checkpoint includes at least one volatile checkpoint.
Claim 5
Dependent Claim
17 words
The method of claim 1 wherein said minimum consistent global checkpoint includes at least one volatile checkpoint.
Claim 6
Dependent Claim
28 words
The method of claim 1 wherein said steps of determining a maximum consistent global checkpoint and determining a minimum consistent global checkpoint are performed by a central process.
Claim 7
Dependent Claim
186 words
The method of claim 5 wherein said inter-process communication and periodic local checkpoints define a checkpoint and communication pattern, wherein P i represents a process where i is the process identification, and where C i ,x represents the x th checkpoint of process P i , wherein said step of determining a maximum consistent global checkpoint further comprises 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 next of local checkpoints such that S next ={C i ,x+1 :C 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 next and marking each reachable node in said rollback dependency graph; and for each process, identifying the most recent checkpoint of the process which is represented by an unmarked node in said rollback dependency graph.
Claim 8
Dependent Claim
159 words
The method of claim 5 wherein said inter-process communication and periodic local checkpoints define a checkpoint and communication pattern and wherein said step of determining a minimum consistent global checkpoint further comprises 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 contains a checkpoint which is represented by a marked node in said rollback dependency graph, identifying the most recent checkpoint of the process which is represented by a marked node in said rollback dependency graph.
Claim 9
Dependent Claim
31 words
The method of claim 1 wherein said steps of determining a maximum consistent global checkpoint and determining a minimum consistent global checkpoint are performed by said processes in a distributed manner.
Claim 10
Dependent Claim
52 words
The method of claim 8 wherein each of said processes locally maintains dependency information, said dependency information representing said checkpoint and a communication pattern, said step of determining a maximum consistent global checkpoint further comprising the step of: each of said processes locally determining a checkpoint in the maximum consistent global checkpoint.
Claim 11
Dependent Claim
51 words
The method of claim 8 wherein each of said processes locally maintains dependency information, said dependency information representing said checkpoint and communication pattern, said step of determining a minimum consistent global checkpoint further comprising the step of: each of said processes locally determining a checkpoint in the minimum consistent global checkpoint.
Claim 12
Independent Claim
219 words
A method for operation of a computer system executing a plurality of processes, P 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 i ,x represents the x th checkpoint of process P 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 next of local checkpoints such that S next ={C i ,x+1 :C 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 next and marking each reachable node in said rollback dependency graph; and for each process P 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.
Claim 13
Independent Claim
219 words
A method for operation of a computer system executing a plurality of processes, P 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 i ,x represents the x th checkpoint of process P 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 next of local checkpoints such that S next ={C i ,x+1 :C 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 next and marking each reachable node in said rollback dependency graph; and for each process P 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.
Claim 14
Dependent Claim
36 words
The method of claim 11 wherein, for at least one of said processes, said most recent checkpoint of the process which is represented by an unmarked node in said rollback dependency graph is a volatile checkpoint.
Claim 15
Dependent Claim
36 words
The method of claim 11 wherein, for at least one of said processes, said most recent checkpoint of the process which is represented by an unmarked node in said rollback dependency graph is a non-volatile checkpoint.
Claim 16
Independent Claim
189 words
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.
Claim 17
Independent Claim
189 words
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.
Claim 18
Dependent Claim
33 words
The method of claim 14 wherein said step of performing a reverse reachability search on said rollback dependency graph further comprises the step of: reversing said directed edges of said rollback dependency graph.
Claim 19
Dependent Claim
36 words
The method of claim 14 wherein, for at least one of said processes, the most recent checkpoint of the process which is represented by a marked node in said rollback dependency graph is a volatile checkpoint.
Claim 20
Dependent Claim
36 words
The method of claim 14 wherein, for at least one of said processes, the most recent checkpoint of the process which is represented by a marked node in said rollback dependency graph is a non-volatile checkpoint.
Claim 21
Independent Claim
177 words
A method for operation of a computer system executing a plurality of processes, P 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 i ,x represents the xth checkpoint of process P 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 i locally determining a checkpoint C i ,x using said locally maintained dependency information, wherein C i ,x is a checkpoint in a maximum consistent global checkpoint including said target set of checkpoints; and each of said processes P i rolling back to the checkpoint C i ,x determined by the process.
Claim 22
Independent Claim
177 words
A method for operation of a computer system executing a plurality of processes, P 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 i ,x represents the xth checkpoint of process P 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 i locally determining a checkpoint C i ,x using said locally maintained dependency information, wherein C i ,x is a checkpoint in a maximum consistent global checkpoint including said target set of checkpoints; and each of said processes P i rolling back to the checkpoint C i ,x determined by the process.
Claim 23
Dependent Claim
14 words
The method of claim 18 wherein said dependency information comprises a transitive dependency vector.
Claim 24
Dependent Claim
18 words
The method of claim 18 wherein at least one of said locally determined checkpoints is a volatile checkpoint.
Claim 25
Dependent Claim
18 words
The method of claim 18 wherein at least one of said locally determined checkpoints is a non-volatile checkpoint.
Claim 26
Dependent Claim
16 words
The method of claim 18 wherein said action request is received from a central monitoring process.
Claim 27
Dependent Claim
19 words
The method of claim 18 wherein said action request includes an identification of said target set of local checkpoints.
Claim 28
Independent Claim
176 words
A method for operation of a computer system, executing a plurality of processes, P 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 i ,x represents the xth checkpoint of process P 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 i locally determining a checkpoint C i ,x using said locally maintained dependency information, wherein C i ,x is a checkpoint in a minimum consistent global checkpoint including said target set of checkpoints; and each of said processes P i rolling back to the checkpoint C i ,x determined by the process.
Claim 29
Independent Claim
176 words
A method for operation of a computer system, executing a plurality of processes, P 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 i ,x represents the xth checkpoint of process P 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 i locally determining a checkpoint C i ,x using said locally maintained dependency information, wherein C i ,x is a checkpoint in a minimum consistent global checkpoint including said target set of checkpoints; and each of said processes P i rolling back to the checkpoint C i ,x determined by the process.
Claim 30
Dependent Claim
14 words
The method of claim 24 wherein said dependency information comprises a transitive dependency vector.
Claim 31
Dependent Claim
16 words
The method of claim 24 wherein said action request is received from a central monitoring process.
Claim 32
Dependent Claim
19 words
The method of claim 24 wherein said action request includes an identification of said target set of local checkpoints.
Claim 33
Dependent Claim
18 words
The method of claim 24 wherein at least one of said locally determined checkpoints is a volatile checkpoint.
Claim 34
Dependent Claim
18 words
The method of claim 24 wherein at least one of said locally determined checkpoints is a non-volatile checkpoint.
References Cited (Backward Citations)
US4697266A
Cited
US4665520A
Cited
US4740969A
Cited
US4852092A
Cited
US5204960A
Cited
US5235700A
Cited
US5293613A
Cited
US5528750A
Cited
US5481694A
Cited
US5440726A
Cited
US5530802A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-05-12 | 2000-11-11 | 2001-05-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-05-12 | 2004-11-11 | 2005-05-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-05-12 | 2008-11-11 | 2009-05-13 | $7700.00 | Window Closed / Lapsed |