Replicated Virtual Machines

The Replicated State Machines (RSM) is a powerful, simple abstraction for providing fault tolerance to arbitrary computational tasks. Unfortunately, RSMs require the computational task to be specified as a deterministic state machine, a model that is theoretically convenient, but in practice, often difficult to achieve given legacy libraries and development environments. We observe that the Virtual Machine (VM) interface is an interesting level at which to constrain the behavior of a computation to be a deterministic state machine. Because it is a narrow interface, it is possible to eliminate nondeterminism in the execution of the VM; this paper describes the techniques necessary to achieve that goal. And because the VM is a very low interface, it enables the reuse of almost the entire software stack, including the operating system, all libraries, and existing applications, even entirely unmodified.