US5802265A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Transparent fault tolerant computer system
Assignee: Ascend Communications Inc
•
Filing: 1995-12-01
•
Granted: 1998-09-01
•
Expires: 2015-12-01
Abstract
Abstract In a fault-tolerant computer system, a primary replica supervisor is interposed between an operating system and a primary replica of an application program being executed by a primary processor. An object-code editor locates calls to the operating system and loops in the application program and inserts instruction sequences that enable the replica supervisor to intercept the calls to the operating system, results returned by the operating system as a result of the calls and asynchronous events delivered by the operating system to the replica. A backup replica supervisor is similarly interposed between an operating system and a backup replica of the application program being executed by a backup processor. The primary replica interacts with an environment. The replica supervisors ensure that the backup replica undergoes state transformations, as a result of the calls to the operating system and asynchronous events, that are equivalent to state transformations that the primary replica undergoes as a result of corresponding calls and asynchronous events. Thus, after a failure in the primary processor, the backup replica can interact with the environment in a manner consistent with interactions between the primary replica and the environment prior to the failure.
Inventors
- 👤 Thomas C. Bressoud
- 👤 John E. Ahern
- 👤 Kenneth P. Birman
- 👤 Robert C. B. Cooper
- 👤 Bradford B. Glade
- 👤 Fred B. Schneider
- 👤 John D. Service
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 03:12
CPC Classifications
G; G06; G06F; G06F11/00; G06F11/07; G06F11/16; G06F11/20; G06F11/2097; G06F11/14; G06F11/1479; G06F11/1482; G06F11/202; G06F11/2023
Claims Analysis
Total Claims: 6
Claim 1
Independent Claim
234 words
In a fault-tolerant computer system having a primary processor and a backup processor, a method for executing a primary replica of a program (primary replica) on the primary processor and a backup replica of the program (backup replica) on the backup processor, the primary processor including a primary replica supervisor interposed between the primary replica and a primary operating system, the backup processor including a backup replica supervisor interposed between the backup replica and a backup operating system, each replica having a process state, the method comprising the steps of: at the primary replica supervisor, intercepting an asynchronous event provided by the primary operating system in response to a system call issued the primary replica; delivering the asynchronous event to the primary replica at an application-relative time that advances as the replica executes independent of the system call to the primary operating system, the asynchronous event causing a process state change at the primary replica (primary state change); sending the intercepted asynchronous event to the backup replica supervisor over a replica coordination communication medium coupling the primary and backup replica supervisors; and delivering the intercepted asynchronous event to the backup replica at the application-relative time, the intercepted asynchronous event causing a process state change at the backup replica (backup state change) such that if the primary processor fails, the backup state change is equivalent to the primary state change as of the application-relative time.
Claim 2
Dependent Claim
234 words
In a fault-tolerant computer system having a primary processor and a backup processor, a method for executing a primary replica of a program (primary replica) on the primary processor and a backup replica of the program (backup replica) on the backup processor, the primary processor including a primary replica supervisor interposed between the primary replica and a primary operating system, the backup processor including a backup replica supervisor interposed between the backup replica and a backup operating system, each replica having a process state, the method comprising the steps of: at the primary replica supervisor, intercepting an asynchronous event provided by the primary operating system in response to a system call issued the primary replica; delivering the asynchronous event to the primary replica at an application-relative time that advances as the replica executes independent of the system call to the primary operating system, the asynchronous event causing a process state change at the primary replica (primary state change); sending the intercepted asynchronous event to the backup replica supervisor over a replica coordination communication medium coupling the primary and backup replica supervisors; and delivering the intercepted asynchronous event to the backup replica at the application-relative time, the intercepted asynchronous event causing a process state change at the backup replica (backup state change) such that if the primary processor fails, the backup state change is equivalent to the primary state change as of the application-relative time.
Claim 3
Dependent Claim
27 words
The method of claim 1 further comprising the step of partitioning execution of the replicas into epochs, each of which contains at least one logical time offset.
Claim 4
Dependent Claim
55 words
The method of claim 2 wherein the application-relative time comprises an epoch and a logical time offset from the beginning of the epoch and wherein the step of partitioning comprises the steps of: instrumenting the replicas to advance the logical time offset; and transferring control to the replica supervisors at a boundary of the epoch.
Claim 5
Dependent Claim
275 words
In a fault-tolerant computer system having a primary processor and a backup processor, a method for executing a primary replica of a program (primary replica) on the primary processor and a backup replica of the program (backup replica) on the backup processor, the primary processor including a primary replica supervisor interposed between the primary replica and a primary operating system, the backup processor including a backup replica supervisor interposed between the backup replica and a backup operating system, each replica having a plurality of threads, the method comprising the steps of: executing each thread of the primary replica to perform acquisitions and releases of exclusive accesses to shared resources (primary acquisitions and releases); at the primary replica supervisor, (i) intercepting the primary acquisitions and releases to identify the thread executed by the primary replica and the shared resources accessed by the primary replica and (ii) permitting performance of the primary acquisitions and releases of the shared resources; sending identities of the executed thread and accessed shared resources to the backup replica supervisor over a replica coordination communication medium coupling the primary and backup replica supervisors; executing each thread of the backup replica to perform acquisitions and releases of exclusive accesses to shared resources (backup acquisitions and releases); at the backup replica supervisor, (i) intercepting the backup acquisitions and releases and (ii) permitting performance of those backup acquisitions and releases to shared resources that correspond to the identified executed thread and accessed shared resources of the primary replica, such that if the primary processor fails, the backup acquisitions and releases are equivalent to the primary acquisitions and releases as of a time prior to the failure.
Claim 6
Dependent Claim
275 words
In a fault-tolerant computer system having a primary processor and a backup processor, a method for executing a primary replica of a program (primary replica) on the primary processor and a backup replica of the program (backup replica) on the backup processor, the primary processor including a primary replica supervisor interposed between the primary replica and a primary operating system, the backup processor including a backup replica supervisor interposed between the backup replica and a backup operating system, each replica having a plurality of threads, the method comprising the steps of: executing each thread of the primary replica to perform acquisitions and releases of exclusive accesses to shared resources (primary acquisitions and releases); at the primary replica supervisor, (i) intercepting the primary acquisitions and releases to identify the thread executed by the primary replica and the shared resources accessed by the primary replica and (ii) permitting performance of the primary acquisitions and releases of the shared resources; sending identities of the executed thread and accessed shared resources to the backup replica supervisor over a replica coordination communication medium coupling the primary and backup replica supervisors; executing each thread of the backup replica to perform acquisitions and releases of exclusive accesses to shared resources (backup acquisitions and releases); at the backup replica supervisor, (i) intercepting the backup acquisitions and releases and (ii) permitting performance of those backup acquisitions and releases to shared resources that correspond to the identified executed thread and accessed shared resources of the primary replica, such that if the primary processor fails, the backup acquisitions and releases are equivalent to the primary acquisitions and releases as of a time prior to the failure.
References Cited (Backward Citations)
US4590554A
Cited
US4608688A
Cited
US4965717B1
Cited
US4965717A
Cited
US5295258A
Cited
US5157663A
Cited
US5193180A
Cited
US5335344A
Cited
US5440727A
Cited
US5363503A
Cited
US5423037A
Cited
US5555404A
Cited
US5590277A
Cited
US5621885A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-31 | 2002-03-02 | 2002-09-01 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-31 | 2006-03-02 | 2006-09-01 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-31 | 2010-03-02 | 2010-09-01 | $7700.00 | Window Closed / Lapsed |