A state machine approach to reliable distributed systems

In many distributed applications, processes synchronize with one another in a complex way and execute for a long period of time. Atomic transactions are inadequate for designing reliable applications with these characteristics, because transactions restrict the types of synchronization than can be specified. An alternative approach that exploits behavior specified in a hierarchical finite-state machine (FSM) model is proposed. A set of general conditions that ensures the correctness of recovery is identified. These general conditions permit combinations of different types of recovery methods to be used in a recovery. They also enable one to enhance recovery efficiency by exploiting permutation and substitution of operations allowed by the behavior specification. It is shown that existing recovery techniques, including those that exploit application semantics, satisfy these conditions for correctness of recovery