US5938775A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Distributed recovery with κ-optimistic logging
Assignee: AT&T Inc
•
Filing: 1998-04-03
•
Granted: 1999-08-17
•
Expires: 2018-04-03
Abstract
Abstract A fault tolerant message passing system includes a plurality of interconnected processors with storage and a watchdog process wherein the processors may undergo failure. A method restores a consistent system state using optimistic logging protocol with asynchronous recovery. Each process comprises a sequence of state intervals and includes checkpoints for saving in storage the state of the process sufficient to re-start execution of the process. Non-deterministic event messages are logged in storage by each process for replay after process re-start to reconstruct pre-failure state intervals. Transitive dependency tracking of messages and process states is performed to record the highest-index state interval of each process upon which a local process depends. A variable size dependency vector is attached to each outgoing message sent between processes. An integer K is assigned to each outgoing message as the upper bound on the vector size. The vector for the local process is updated upon receiving each incoming message. A process failure is detected and the failed process is re-started. The latest checkpoint is restored and the logged messages are replayed. A new incarnation of the failed process is started and identified by Pi, t where (i) is the process number and (t) is the incarnation number, each state interval being identified by (t,x)i where (x) is the state interval number. A failure announcement is broadcast to the other processes, the announcement containing (t,x)i where (x) is the state interval number of the last recreatable state interval of the failed process incarnation Pi, t. Upon receiving a failure announcement containing (t,x)i, the entry for process (i) is extracted from the local dependency vector. The entry for process (i) is compared to the (t,x)i contained in the failure announcement. The process is classified as orphaned from the comparison if the process depends upon a higher-index state interval than (t,x)i. A process roll-back is performed to reconstruct only non-orphaned state intervals in the rolled-back process.
Inventors
- 👤 Om P. Damani
- 👤 Vijay Kumar Garg
- 👤 Yi-Min Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 04:24
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/14; G06F11/1402; G06F11/1415; G06F11/1438
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
123 words
In a message passing system having a plurality of interconnected processors which include storage and a watchdog process and wherein the processors may undergo failure, a method for restoring a consistent system state using optimistic logging protocol with asynchronous recovery for a plurality of processes, comprising the steps of: a) performing transitive dependency tracking of messages and process states to record a highest-index state interval of each process upon which a local process depends by: i) attaching a variable size dependency vector to each outgoing message sent between processes; ii) assigning an integer K to each outgoing message as the upper bound on the vector size; and iii) updating a local dependency vector associated with the local process upon receiving each incoming message.
Claim 2
Dependent Claim
123 words
In a message passing system having a plurality of interconnected processors which include storage and a watchdog process and wherein the processors may undergo failure, a method for restoring a consistent system state using optimistic logging protocol with asynchronous recovery for a plurality of processes, comprising the steps of: a) performing transitive dependency tracking of messages and process states to record a highest-index state interval of each process upon which a local process depends by: i) attaching a variable size dependency vector to each outgoing message sent between processes; ii) assigning an integer K to each outgoing message as the upper bound on the vector size; and iii) updating a local dependency vector associated with the local process upon receiving each incoming message.
Claim 3
Dependent Claim
105 words
The method of claim 1 further comprising the steps of: b) detecting a process failure and re-starting the failed process by: i) restoring a latest checkpoint and replaying logged messages; ii) starting a new incarnation of the failed process identified by Pi, t where (i) is the process number and (t) is the incarnation number, each state interval being identified by (t,x) i where (x) is the state interval number; and iii) broadcasting a failure announcement to the other processes, the announcement containing (t,x) i where (x) is the state interval number of the last recreatable state interval of the failed process incarnation Pi, t.
Claim 4
Dependent Claim
93 words
The method of claim 2 further comprising the steps of: c) receiving a failure announcement containing (t, x) i and performing the following steps: i) extracting from the local dependency vector the entry for process (i) by each process; ii) comparing the entry for process (i) to the (t,x) i contained in the failure announcement; iii) classifying the process as orphaned from the comparison if the process depends upon a higher-index state interval than (t,x) i ; and iv) performing a process roll-back to reconstruct only non-orphaned state intervals in the rolled-back process.
Claim 5
Dependent Claim
343 words
In a message passing system having a plurality of interconnected processors which include storage and a watchdog process and wherein the processors may undergo failure, a method for restoring a consistent system state using optimistic logging protocol with asynchronous recovery, comprising the steps of: a) initializing processes in the system wherein each process comprises a sequence of state intervals; b) establishing checkpoints in each process by saving in storage the state of the process sufficient to re-start execution of the process; c) logging non-deterministic event messages in storage by each process for replay after process re-start to reconstruct pre-failure state intervals; d) performing transitive dependency tracking of messages and process states to record the highest-index state interval of each process upon which a local process depends by: i) attaching a variable size dependency vector to each outgoing message sent between processes; ii) assigning an integer K to each outgoing message as the upper bound on the vector size; iii) updating a vector for the local process upon receiving each incoming message; e) detecting a process failure and re-starting the failed process; i) restoring the latest checkpoint and replaying the logged messages; ii) starting a new incarnation of the failed process identified by Pi,t where (i) is the process number and (t) is the incarnation number, each state interval being identified by (t,x) i where (x) is the state interval number; iii) broadcasting a failure announcement to the other processes, the announcement containing (t,x) i where (x) is the state interval number of the last recreatable state interval of the failed process incarnation Pi,t; f) receiving a failure announcement containing (t,x)i and performing the following steps: (i) extracting from the local dependency vector the entry for process (i) by each process; ii) comparing the entry for process (i) to the (t,x) i contained in the failure announcement; iii) classifying the process as orphaned from the comparison if the process depends upon a higher-index state interval than (t,x) i ; and iv) performing process roll-back to reconstruct only non-orphaned state intervals in the rolled-back process.
Claim 6
Dependent Claim
343 words
In a message passing system having a plurality of interconnected processors which include storage and a watchdog process and wherein the processors may undergo failure, a method for restoring a consistent system state using optimistic logging protocol with asynchronous recovery, comprising the steps of: a) initializing processes in the system wherein each process comprises a sequence of state intervals; b) establishing checkpoints in each process by saving in storage the state of the process sufficient to re-start execution of the process; c) logging non-deterministic event messages in storage by each process for replay after process re-start to reconstruct pre-failure state intervals; d) performing transitive dependency tracking of messages and process states to record the highest-index state interval of each process upon which a local process depends by: i) attaching a variable size dependency vector to each outgoing message sent between processes; ii) assigning an integer K to each outgoing message as the upper bound on the vector size; iii) updating a vector for the local process upon receiving each incoming message; e) detecting a process failure and re-starting the failed process; i) restoring the latest checkpoint and replaying the logged messages; ii) starting a new incarnation of the failed process identified by Pi,t where (i) is the process number and (t) is the incarnation number, each state interval being identified by (t,x) i where (x) is the state interval number; iii) broadcasting a failure announcement to the other processes, the announcement containing (t,x) i where (x) is the state interval number of the last recreatable state interval of the failed process incarnation Pi,t; f) receiving a failure announcement containing (t,x)i and performing the following steps: (i) extracting from the local dependency vector the entry for process (i) by each process; ii) comparing the entry for process (i) to the (t,x) i contained in the failure announcement; iii) classifying the process as orphaned from the comparison if the process depends upon a higher-index state interval than (t,x) i ; and iv) performing process roll-back to reconstruct only non-orphaned state intervals in the rolled-back process.
Claim 7
Dependent Claim
25 words
The method of claim 4 further comprising the step of omitting vector entries in the dependency vector corresponding to state intervals that have become stable.
Claim 8
Dependent Claim
25 words
The method of claim 4 further comprising the step of sending a message if a process vector size is less than or equal to K.
Claim 9
Dependent Claim
31 words
The method of claim 4 further comprising the step of periodically broadcasting a logging progress notification by each process to let other processes know which of its state intervals is stable.
Claim 10
Dependent Claim
23 words
The method of claim 4 further comprising the step of starting a new state internal upon receiving a non-deterministic event from another process.
Claim 11
Dependent Claim
22 words
The method of claim 4 wherein the integer K is between 0 and N, and N is the total number of processes.
Claim 12
Dependent Claim
19 words
The method of claim 4 wherein K indicates the maximum number of processes whose failure may revoke the message.
Claim 13
Dependent Claim
12 words
The method of claim 4 wherein the storage maybe volatile or non-volatile.
Claim 14
Dependent Claim
22 words
The method of claim 4 wherein a state interval is stable when the state interval is recreatable from information saved in storage.
References Cited (Backward Citations)
US4570261A
Cited
US4665520A
Cited
US5485608A
Cited
US5396613A
Cited
US5440726A
Cited
US5530802A
Cited
US5590277A
Cited
US5630047A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-08-16 | 2003-02-15 | 2003-08-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-08-16 | 2007-02-15 | 2007-08-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-08-16 | 2011-02-15 | 2011-08-17 | $7700.00 | Window Closed / Lapsed |