If failure occurs, the system rolls back to a previous checkpoint, replays those actions that the system has saved, and proceeds with execution. Processes are grouped into recovery units. Periodically, process state is also logged in stable storage. Recovery is controlled by retaining state-dependency information for all messages sent and received by a recovery unit. Hence, when a recovery unit fails and then restarts with a new incarnation, other recovery units can determine which of their sent messages are now invalid because of dependencies on the failed unit.
Dependent units rollback their state and in effect recall their invalid messages.
The technique guarantees that there is a fixed and finite amount of necessary rollback. Performance tuning modifications and garbage collection of recovery information are discussed. The paper is self-contained, reasonably easy to read, and provides good references to related work. My only criticism is that the comparison to other work in database systems and distributed system snapshots is shallow, but at least references are there for interested readers. The Digital Library is published by the Association for Computing Machinery.