At+t Corp.

Lucent Technologies Inc.

Wesley K Fuchs

Yi-Min Wang

Yennun Huang

Chandra M Kintala

A progressive retry recovery system based on checkpointing, message logging, rollback, message replaying and message reordering is disclosed. The disclosed progressive retry system minimizes the number of involved processes as well as the total rollback distance. The progressive retry method consists of a number of retry steps which gradually increase the scope of the rollback when a previous retry step fails. Step one attempts to bypass a software fault by having the faulty process replay the messages in its message log. Step two will attempt to bypass the software fault by having the faulty process reorder and then replay the messages in its message log. Step three will attempt to bypass the software fault by having the processes which have sent messages to the faulty process resend those messages to the faulty process. Step four will attempt to bypass the software fault by having the processes which have sent messages to the faulty process reorder and then resend their in-transit messages. Step five will attempt to bypass the software fault by implementing a large scope roll back of all monitored processes to the latest consistent global checkpoint. A mechanism is included for verifying the piecewise deterministic assumption.

Progressive retry method and apparatus for software failure recovery in

A software failure bypass system based on checkpointing, input logging, rollback and input sequence reordering is disclosed. The software fault bypass system minimizes the number of involved processes as well as the total rollback distance. The software fault bypass system includes a progressive retry recovery algorithm which gradually increases the scope of the recovery when a previous retry step fails to bypass the detected fault and a reorder recovery algorithm which will attempt to bypass the detected fault by reordering and reprocessing the inputs that have been received by the faulty application process. The fault tolerant system includes a mechanism which utilizes information about the particular application process or the cause of the detected fault to determine if the recovery of a particular application process should proceed directly to the reorder recovery algorithm. In one embodiment, if the faulty process exhibits nondeterministic behavior, the overall progressive retry recovery algorithm should be utilized to recover the faulty process. If the faulty process does not exhibit nondeterministic behavior, however, the reorder recovery algorithm should be utilized to recover the faulty process.

Input sequence reordering method for software failure recovery

A progressive retry recovery system based on checkpointing, message logging, rollback, message replaying and message reordering is disclosed. The disclosed progressive retry system minimizes the number of involved processes as well as the total rollback distance. The progressive retry recovery system includes a fault tolerant software library which provides a number of functions which may be invoked by application processes to implement fault tolerance. Fault tolerant functions are provided for allowing an application process to generate a heartbeat message at specified intervals indicating that the application process is still active. In addition, fault tolerance implementation functions are provided for specifying critical memory, for executing checkpoints to store backup copies of critical data, and for restoring critical data during a recovery. In addition, functions are provided which process messages that are sent or received by an application process and maintain logs of the sent and received messages. The progressive retry recovery method consists of a number of retry steps which gradually increase the scope of the rollback when a previous retry step fails.

Growing community of inventors

Mahomet, IL, United States of America

Wesley K Fuchs