Distributed recovery with .kappa.-optimistic logging
US5938775A · kind A · utility
Assignee
Inventors
Key dates
| Filing date | Apr 3, 1998 |
| Grant date | Aug 17, 1999 |
| Priority date | — |
| Expiry date | Apr 3, 2018 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F11/1438
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
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 …
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.