Optimistic algorithms for distributed transparent process replication
Arthur P. Goldberg · 1991
Process replication is an operating system function that can represent any sequential process in a distributed application as a set of concurrently executing instances, called replicas. The purpose of process replication is to speed up the execution of distributed applications. Suppose an application contains a bottleneck process--a process whose speedup would speedup the entire application. If most messages executed by a bottleneck process do not modify its local state, then executing multiple replicas of the bottleneck can speedup an application's execution in two ways. First, communication delays can be reduced by locating the replicas near processes communicating with the bottleneck. Second, parallelism can be increased by executing the replicas concurrently on multiple processors. To be convenient process replication must be transparent--execution of a message that modifies a replicated process's state must appear to the application to simultaneously modify the states of all the process's replicas. Implementing replication is challenging because it is difficult to achieve both transparency and good performance. We present several optimistic algorithms for transparent process replication. The algorithms are optimistic in that they that a message whose execution modifies a replica's state can be executed before applying the modification to the process' other replicas, without having the application observe the delayed consistency. If the guess is wrong then execution of the message may have to be undone. However, if the probability the guess is correct is sufficiently high then the advantages of executing parts of a computation earlier will outweigh the cost of support for undo plus the cost of undoing incorrect executions. We present two optimistic replication algorithms. The first modifies the Time Warp optimistic distributed simulation system into a replication mechanism. The second implements a dependency-tracked mechanism based on the Optimistic Recovery fault-tolerance algorithm. We present designs for these algorithms, and discussions of their performance.