US5712971A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Methods and systems for reconstructing the state of a computation
Assignee: AB Initio Technology LLC
•
Filing: 1995-12-11
•
Granted: 1998-01-27
•
Expires: 2015-12-11
Abstract
Abstract Methods and systems for running and checkpointing parallel and distributed applications which does not require modification to the programs used in the system nor changes to the underlying operating system. One embodiment of the invention includes the following general steps: (1) starting an application on a parallel processing system; (2) controlling processes for the application, including recording of commands and responses; (3) controlling a commit protocol; (4) detecting failures of the application; (5) continuing execution of the application from the most recently committed transaction after "replaying" the recorded commands and responses. A second embodiment comprises the following general steps: (1) starting an application on a parallel processing system; (2) controlling processes for the application, including recurrent recording of the memory image of a driver program that controls the application; (3) controlling a commit protocol; (4) detecting failures of the application; (5) continuing execution of the application from the most recently committed transaction after "restoring" the recorded memory image of the driver program.
Inventors
- 👤 Craig Stanfill
- 👤 Cliff Lasser
- 👤 Robert Lordi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 10:02
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1471; G06F11/1474
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
162 words
A method for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, comprising the steps of: (a) executing an application in distinct execution phases on a parallel processing system; (b) controlling processing of each execution phase of the application by issuing commands and replies to such commands; (c) recording all such commands and replies to such commands; (d) saving the end-state of each successfully completed execution phase; (e) detecting failure of the application in any of such execution phases; (f) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) recapitulating all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 2
Independent Claim
162 words
A method for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, comprising the steps of: (a) executing an application in distinct execution phases on a parallel processing system; (b) controlling processing of each execution phase of the application by issuing commands and replies to such commands; (c) recording all such commands and replies to such commands; (d) saving the end-state of each successfully completed execution phase; (e) detecting failure of the application in any of such execution phases; (f) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) recapitulating all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 3
Dependent Claim
187 words
A computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to: (a) execute an application in distinct execution phases on a parallel processing system; (b) control processing of each execution phase of the application by issuing commands and replies to such commands; (c) record all such commands and replies to such commands; (d) save the end-state of each successfully completed execution phase; (e) detect failure of the application in any of such execution phases; (f) restore the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) recapitulate all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restart the application at the beginning of the execution phase in which failure was detected.
Claim 4
Dependent Claim
187 words
A computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to: (a) execute an application in distinct execution phases on a parallel processing system; (b) control processing of each execution phase of the application by issuing commands and replies to such commands; (c) record all such commands and replies to such commands; (d) save the end-state of each successfully completed execution phase; (e) detect failure of the application in any of such execution phases; (f) restore the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) recapitulate all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restart the application at the beginning of the execution phase in which failure was detected.
Claim 5
Dependent Claim
187 words
A computer-readable storage medium, configured with a computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions of: (a) executing an application in distinct execution phases on a parallel processing system; (b) controlling processing of each execution phase of the application by issuing commands and replies to such commands; (c) recording all such commands and replies to such commands; (d) saving the end-state of each successfully completed execution phase; (e) detecting failure of the application in any of such execution phases; (f) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) recapitulating all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 6
Dependent Claim
187 words
A computer-readable storage medium, configured with a computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions of: (a) executing an application in distinct execution phases on a parallel processing system; (b) controlling processing of each execution phase of the application by issuing commands and replies to such commands; (c) recording all such commands and replies to such commands; (d) saving the end-state of each successfully completed execution phase; (e) detecting failure of the application in any of such execution phases; (f) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) recapitulating all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 7
Independent Claim
173 words
A method for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, comprising the steps of: (a) dividing an application into distinct execution phases; (b) starting execution of the application on a parallel processing system; (c) controlling processing of each execution phase of the application by issuing commands and replies to such commands; (d) recording all such commands and replies to such commands; (e) saving the end-state of each successfully completed execution phase by a two-phase commit protocol; (f) detecting failure of the application in any of such execution phases; (g) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) recapitulating all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (i) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 8
Independent Claim
173 words
A method for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, comprising the steps of: (a) dividing an application into distinct execution phases; (b) starting execution of the application on a parallel processing system; (c) controlling processing of each execution phase of the application by issuing commands and replies to such commands; (d) recording all such commands and replies to such commands; (e) saving the end-state of each successfully completed execution phase by a two-phase commit protocol; (f) detecting failure of the application in any of such execution phases; (g) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) recapitulating all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (i) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 9
Dependent Claim
198 words
A computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to: (a) divide an application into distinct execution phases; (b) start execution of the application on a parallel processing system; (c) control processing of each execution phase of the application by issuing commands and replies to such commands; (d) record all such commands and replies to such commands; (e) save the end-state of each successfully completed execution phase by a two-phase commit protocol; (f) detect failure of the application in any of such execution phases; (g) restore the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) recapitulate all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (i) restart the application at the beginning of the execution phase in which failure was detected.
Claim 10
Dependent Claim
198 words
A computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to: (a) divide an application into distinct execution phases; (b) start execution of the application on a parallel processing system; (c) control processing of each execution phase of the application by issuing commands and replies to such commands; (d) record all such commands and replies to such commands; (e) save the end-state of each successfully completed execution phase by a two-phase commit protocol; (f) detect failure of the application in any of such execution phases; (g) restore the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) recapitulate all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (i) restart the application at the beginning of the execution phase in which failure was detected.
Claim 11
Dependent Claim
198 words
A computer-readable storage medium, configured with a computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions of: (a) dividing an application into distinct execution phases; (b) starting execution of the application on a parallel processing system; (c) controlling processing of each execution phase of the application by issuing commands and replies to such commands; (d) recording all such commands and replies to such commands; (e) saving the end-state of each successfully completed execution phase by a two-phase commit protocol; (f) detecting failure of the application in any of such execution phases; (g) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) recapitulating all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (i) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 12
Dependent Claim
198 words
A computer-readable storage medium, configured with a computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions of: (a) dividing an application into distinct execution phases; (b) starting execution of the application on a parallel processing system; (c) controlling processing of each execution phase of the application by issuing commands and replies to such commands; (d) recording all such commands and replies to such commands; (e) saving the end-state of each successfully completed execution phase by a two-phase commit protocol; (f) detecting failure of the application in any of such execution phases; (g) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) recapitulating all recorded commands and replies to such commands from the beginning of execution of the application up through the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (i) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 13
Independent Claim
175 words
A method for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, comprising the steps of: (a) executing an application in distinct execution phases on a parallel processing system; (b) controlling processing of each execution phase of the application by a driver program; (c) saving the end-state of each successfully completed execution phase; (d) saving, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (e) detecting failure of the application in any of such execution phases; (f) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) restoring the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (h) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 14
Independent Claim
175 words
A method for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, comprising the steps of: (a) executing an application in distinct execution phases on a parallel processing system; (b) controlling processing of each execution phase of the application by a driver program; (c) saving the end-state of each successfully completed execution phase; (d) saving, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (e) detecting failure of the application in any of such execution phases; (f) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) restoring the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (h) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 15
Dependent Claim
200 words
A computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to: (a) execute an application in distinct execution phases on a parallel processing system; (b) control processing of each execution phase of the application by a driver program; (c) save the end-state of each successfully completed execution phase; (d) save, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (e) detect failure of the application in any of such execution phases; (f) restore the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) restore the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (h) restart the application at the beginning of the execution phase in which failure was detected.
Claim 16
Dependent Claim
200 words
A computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to: (a) execute an application in distinct execution phases on a parallel processing system; (b) control processing of each execution phase of the application by a driver program; (c) save the end-state of each successfully completed execution phase; (d) save, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (e) detect failure of the application in any of such execution phases; (f) restore the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) restore the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (h) restart the application at the beginning of the execution phase in which failure was detected.
Claim 17
Dependent Claim
200 words
A computer-readable storage medium, configured with a computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions of: (a) executing an application in distinct execution phases on a parallel processing system; (b) controlling processing of each execution phase of the application by a driver program; (c) saving the end-state of each successfully completed execution phase; (d) saving, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (e) detecting failure of the application in any of such execution phases; (f) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) restoring the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (h) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 18
Dependent Claim
200 words
A computer-readable storage medium, configured with a computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions of: (a) executing an application in distinct execution phases on a parallel processing system; (b) controlling processing of each execution phase of the application by a driver program; (c) saving the end-state of each successfully completed execution phase; (d) saving, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (e) detecting failure of the application in any of such execution phases; (f) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (g) restoring the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (h) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 19
Independent Claim
186 words
A method for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, comprising the steps of: (a) dividing an application into distinct execution phases; (b) starting execution of the application on a parallel processing system; (c) controlling processing of each execution phase of the application by a driver program; (d) saving the end-state of each successfully completed execution phase by a two-phase commit protocol; (e) saving, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (f) detecting failure of the application in any of such execution phases; (g) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restoring the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (i) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 20
Independent Claim
186 words
A method for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, comprising the steps of: (a) dividing an application into distinct execution phases; (b) starting execution of the application on a parallel processing system; (c) controlling processing of each execution phase of the application by a driver program; (d) saving the end-state of each successfully completed execution phase by a two-phase commit protocol; (e) saving, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (f) detecting failure of the application in any of such execution phases; (g) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restoring the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (i) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 21
Dependent Claim
211 words
A computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to: (a) divide an application into distinct execution phases; (b) start execution of the application on a parallel processing system; (c) control processing of each execution phase of the application by a driver program; (d) save the end-state of each successfully completed execution phase by a two-phase commit protocol; (e) save, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (f) detect failure of the application in any of such execution phases; (g) restore the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restore the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (i) restart the application at the beginning of the execution phase in which failure was detected.
Claim 22
Dependent Claim
211 words
A computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, the computer program being stored on a media readable by a computer system, for configuring the computer system upon being read and executed by the computer system to: (a) divide an application into distinct execution phases; (b) start execution of the application on a parallel processing system; (c) control processing of each execution phase of the application by a driver program; (d) save the end-state of each successfully completed execution phase by a two-phase commit protocol; (e) save, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (f) detect failure of the application in any of such execution phases; (g) restore the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restore the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (i) restart the application at the beginning of the execution phase in which failure was detected.
Claim 23
Dependent Claim
211 words
A computer-readable storage medium, configured with a computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions of: (a) dividing an application into distinct execution phases; (b) starting execution of the application on a parallel processing system; (c) controlling processing of each execution phase of the application by a driver program; (d) saving the end-state of each successfully completed execution phase by a two-phase commit protocol; (e) saving, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (f) detecting failure of the application in any of such execution phases; (g) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restoring the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (i) restarting the application at the beginning of the execution phase in which failure was detected.
Claim 24
Dependent Claim
211 words
A computer-readable storage medium, configured with a computer program for executing a computer application on a parallel processing system, where such application does not have pre-programmed checkpointing capability, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions of: (a) dividing an application into distinct execution phases; (b) starting execution of the application on a parallel processing system; (c) controlling processing of each execution phase of the application by a driver program; (d) saving the end-state of each successfully completed execution phase by a two-phase commit protocol; (e) saving, at the end of each successfully completed execution phase, at least those data structures of the driver program necessary to recreate a saved state for the driver program; (f) detecting failure of the application in any of such execution phases; (g) restoring the last saved end-state of the execution phase prior to the execution phase in which failure was detected; (h) restoring the driver program by reloading into memory the saved data structures of the driver program up through the end of the execution phase prior to the execution phase in which failure was detected; (i) restarting the application at the beginning of the execution phase in which failure was detected.
References Cited (Backward Citations)
US4823256A
Cited
US4703481A
Cited
US5499342A
Cited
US5313584A
Cited
US5435003A
Cited
US5440726A
Cited
US5530802A
Cited
US5590277A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-01-26 | 2001-07-28 | 2002-01-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-01-26 | 2005-07-28 | 2006-01-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-01-26 | 2009-07-28 | 2010-01-27 | $7700.00 | Window Closed / Lapsed |