US5938775A — Distributed recovery with κ-optimistic logging

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.

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

Distributed recovery with κ-optimistic logging

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag