The replicated state machine method of fault tolerance from 1980s

The first time I saw this method was when I went to work for Parallel Computer Systems, , later called Auragen, in the famous tech startup center of Englewood Cliffs, New Jersey. I commuted there from the East Village. (True story: I applied for the job after finding an advert in a discarded copy of the NY Times on the floor of a Brooklyn apartment while visiting friends. I sent via US mail a resume typed on a manual typewriter- I’m tempted to  say “composed by the light of a tallow candle” but that would be over the top- and forgot to send the second page. )

The company built a parallel computer based on Motorola 68000s  with a replicated message bus. The bus guaranteed message delivery to 3 destinations would either succeed to all three or fail to all three. This property is called “reliable broadcast”.  All interprocess communication was by message transfer (a fashionable idea at the time). Each process had a backup.  Whenever a primary process sent a message, the message was also delivered to the backup and to the destination backup. If the primary failed, the backup could be run. The backup would have a queue of messages received by the primary and a count of messages sent by the primary.  When the recovering backup tried to transmit a message, if the count was greater than zero, the count would be decremented and the message discarded because it has already been transmitted by the old primary. When the recovering secondary did a receive operation, if there was a message on the input queue, it would get that message.  In this way, the recovering backup would repeat the operations of the primary until it caught up. As an optimization, the primary could be periodically checkpointed and queues of duplicated messages could be discarded.

The operating system was an implementation of UNIX. In practice, it was discovered that making each UNIX system call into a message exchange, which was an idea advocated in the OS research community at the time, caused serious performance problems.  The replicated state machine operation depended on this design  in order to make the state machine operation deterministic. Suppose the primary requested, for example,  the time and then made a decision based on the time.  A recovering secondary would need exactly the same time to guarantee that it produced the same results as the primary. So every interaction between application and OS needed to be recorded in a message exchange.  But a message exchange is nowhere near as fast as a system call (unless the OS developers are horrible).

The performance issue was mitigated by some clever engineering, but  was a problem that was discovered in parallel by a number of development teams working on distributed OS designs and micro-kernels which were in vogue at the time. Execution of “ls -l” was particularly interesting.

Anyways, here’s the description from the patent.

To accomplish this object, the invention contemplates that instead of keeping the backup or secondary task exactly up to date, the backup is kept nearly up to date but is provided with all information necessary to bring itself up to the state of the primary task should there by a failure of the primary task. The inventive concept is based on the notion that if two tasks start out in identical states and are given identical input information, they will perform identically.

In particular, all inputs to a process running on a system according to the invention are provided via messages. Therefore, all messages sent to the primary task must be made available to the secondary or backup task so that upon failure of the primary task the secondary task catches up by recomputing based on the messages. In essence, then, this is accomplished by allowing every backup task to “listen in on” its primary’s message.

United States Patent 4,590,554 Glazer ,   et al.May 20, 1986

Inventors: Glazer; Sam D. (New York, NY), Baumbach; James (Brooklyn, NY), Borg; Anita (New York, NY), Wittels; Emanuel (Englewood Cliffs, NJ)
Assignee: Parallel Computers Systems, Inc. (Fort Lee, NJ)
Family ID: 23762790
Appl. No.: 06/443,937
Filed: November 23, 1982

See also: A message system supporting fault tolerance.

and a very similar later patent.

The Auragen file system.

This article on the interesting Wave Transactional File System inspired me to look up an earlier file system that also used copy on write semantics.


Anita Borg, Wolfgang Blau, Wolfgang Graetsch, Ferdinand Herrmann, and Wolfgang Oberle. 1989. Fault tolerance under UNIX. ACM Trans. Comput. Syst. 7, 1 (January 1989), 1-24. DOI=


4.3 Availability of the File System
Since a recovering file server reconstructs its buffers by reading blocks from the file system, the file system in the state as of the last sync must be available. The existence of that version of the file system is also necessary during recovery as the file server redoes requests. For example, if a file has been deleted since sync and a read request is reissued, the disk driver, and thus the recovering file server, will behave differently than the primary. Unfortunately, the contents of the disk can change between syncs, at least during the Fsync that constitutes the first phase of the sync operation.

The solution is to use a copy-on-write strategy between syncs, rather than overwriting existing blocks. Logically this corresponds to keeping two versions of a file system.3 An early version of the file system organization described here is discussed in Arnow [ 11].

There are two root nodes on disk. At any given time one of them is valid for recovery. We refer to the other as the alternate root. Associated with each root is state information (the state tables described above), the most recent being that associated with the currently valid root. Changes to the file system are done relative to a copy of the valid root kept in memory in the primary file server’s address space, and in a nondestructive manner, as seen in Figure 2(a-d). Freed blocks, which contain the old data, are added to a semi-free list, and cannot be reallocated until after the next sync. Therefore, the unmodified file system still exists rooted in the valid on-disk root node.

If a crash occurs at any time between syncs, the recovering file server is able to determine which root to use because of information sent on the primary’s last sync. It reads in the correct state information and reconstructs its buffers accordingly. Disk blocks that were used by the primary since the last sync appear to it as free blocks.

The difficult case is when a crash occurs during a sync. To see that the solution works in this case, consider the sequence of actions that take place during a sync. First, all dirty blocks except the root are written to disk, and old blocks are added to the semi-free list. Second, the state information is collected and written to the alternate state area. Third, the in-memory root is written to the alternate on disk root block, Finally, the sync message is constructed and sent to the backup. It contains the information necessary to update message queues as well as specifying which on-disk state information and root block to use on recovery.

Once the sync message has been sent, the semi-free list is added to the free list and the primary continues. Just before the sync message is sent, there are two copies of every modified data and indirect block. At any time before the sync message is sent, the old consistent state is available. Any time after it is sent, the new state and file system will be used and message queues consistently updated. An additional benefit of this organization is that the file system as a whole is considerably more robust than a standard UNIXstyle file system. Even if the entire system is shut down in an uncontrolled way as the result of multiple faults or operator error, there will always be an entire consistent file system on disk.

fault tolerant patent

So I don’t understand the novelty in the methods here over the Glazer patent.

The replica supervisors provide interfaces to the replicas that are the same as the interface provided by the operating system. Thus, when one of the replicas makes a call to the operating system, the corresponding replica supervisor is invoked and the supervisor ensures that the effect of the intercepted call is the same regardless of whether the primary or backup performs the operation. When the primary supervisor intercepts a call by the primary replica, the primary supervisor makes the call to the operating system on behalf of the replica and then delivers the results of the operating system call (the “values returned by the operating system”) to the primary replica. In other words, the primary supervisor causes a transformation in the state of the primary replica that is equivalent to the transformation the operating system would have caused if the call had not been intercepted.

The primary supervisor also sends a message to the backup replica. The message contains the values returned by the operating system. When the backup supervisor intercepts a call to the operating system by the backup replica, the backup supervisor does not call the operating system on behalf of the backup replica. Instead, the backup supervisor uses the values sent by the primary supervisor, as a result of the corresponding call by the primary replica, to transform the state of the backup replica. Thus, the replica supervisors ensure that the primary and backup replicas undergo equivalent transformations of their application state as a result of corresponding calls to the operating system.

Inventors: Bressoud; Thomas C. (Northborough, MA), Ahern; John E. (Sudbury, MA), Birman; Kenneth P. (Ithaca, NY), Cooper; Robert C. B. (Wellesley, MA), Glade; Bradford B. (Harvard, MA), Schneider; Fred B. (Ithaca, NY), Service; John D. (Chelmsford, MA)
Assignee: Stratus Computer, Inc. (Marlboro, MA)
Appl. No.: 08/565,145
Filed: December 1, 1995

Compare to

More specifically, the invention contemplates a parallel computer system having at least a first and a second primary task performing means and a first and a second secondary (backup) task performing means. The task performing means are interconnected by a message bus means. In such a system, there is contemplated the method of sending messages among the task performing means. In particular, the invention contemplates sending messages from the first primary task performing means to the second primary task performing means which operates on the messages in accordance with the task associated with such means. The second primary task performing means operates on the received messages by initially storing a received message in a queue and thereafter reading the message from the queue for processing. In addition, this second primary task performing means accumulates a count of the messages it reads from the queue. At the same time, or immediately thereafter, the primary task performing means sends the same messages to the second secondary task performing means which stores these messages in a message queue associated therewith. The messages stored in the queue of the second secondary task performing means are only processed if there is a failure of the second primary task performing means.

Great software patents: fault tolerance

software patent

A parallel computer system which has a primary task processor, a second primary task processor, a secondary task processor acting as a backup for the second primary task processor transfers messages by: sending messages from the primary task processor to the second primary processor with the second primary task processor operating on the messages by initially storing a received message in a queue and thereafter reading the message from the queue for processing in accordance with the task associated therewith and accumulating a count of the messages read from its queue; and sending the same messages from the first primary task processor to the secondary task processor which stores the messages in a message queue for possible use if the second primary task processor fails. If a primary task processor fails after processing a given number of messages, the secondary task processor associated therewith starts processing the messages in its queue but after having discarded the first given number of messages.

Inventors: Glazer; Sam D. (New York, NY), Baumbach; James (Brooklyn, NY), Borg; Anita (New York, NY), Wittels; Emanuel (Englewood Cliffs, NJ)
Assignee: Parallel Computers Systems, Inc. (Fort Lee, NJ)
Appl. No.: 06/443,937
Filed: November 23, 1982

Auragen computers remembered

In the early 1980s, I worked for a start-up called Auragen Computers based in Fort Lee, New Jersey. We were making a 68K based fault tolerant UNIX based on a smart idea by Sam Glazer. Most of the software engineers lived in New York City and commuted out. Start-ups with New Yorkers have a different “culture” than start-ups with Californians. One of the senior technical staff was once asked to meet with investors to talk about why development was taking so long. After some fruitless attempts at discussion he explained, kindly, “I don’t think I can make this clear in 5 minutes. It took me 10 years to understand this stuff and I’m a lot smarter than you.” Auragen did some good work, but failed to get the product out to market in time. A good lesson to learn.
Auragen gave me my first job in the computer industry and a great education in operating systems. I still remember sitting in a room with Jim Baumbach, Anita Borg, David Arnow, and Sam Glazer soon after I started there, and confronting the reality that everyone in the room was a lot smarter, better educated, and more witty than me (my only consolation was that, in their early 30s, they seemed pretty damn old).