A state machine approach to reliable and dynamically reconfigurable distributed systems
Alvin Lim · Minds at UW (University of Wisconsin) · 1993
Maintaining consistency among distributed processes in the presence of failures and reconfigurations is a difficult problem, especially when the processes may synchronize with one another in complex ways and execute for a long period of time. Atomic transactions are commonly used to simplify the management of concurrency and failure by preserving serializability and failure atomicity. The major drawback of preserving these properties is that they restrict the types of synchronization that can be specified. This thesis focuses on a general set of correctness conditions for preserving consistency based on a general synchronization model of process interaction. Instead of extending established but inappropriate concepts used in atomic transactions, this thesis explores three more fundamental questions: (1) How can consistency be maintained without enforcing serializability and failure atomicity? (2) How can applications be specified that will assist the system maintain consistency automatically? (3) How can we implement mechanisms for managing synchronization, recovery and dynamic reconfiguration uniformly? To preserve consistency in the presence of a failure or reconfiguration, we introduce a general set of conditions that guarantees the correctness of recovery and dynamic reconfiguration of applications that need not be serializable or linearizable. These conditions are based on a basic definition of interactive consistency. Existing recovery techniques, including those that exploit application-specific semantics, satisfy these conditions. We present algorithms for automatically checking these conditions from application behaviors specified in a hierarchical finite-state machine model. These correctness conditions, defined as properties of finite-state machine graphs, enable us to improve recovery efficiency by exploiting the permutation and substitution of operations allowed by the behavior specification. They also permit combinations of different types of recovery methods to be used in a recovery. We have separated the policy information for maintaining consistency from the mechanism that implements them. We exploit this in an implementation of a uniform set of control mechanisms that use these information to maintain consistency in the presence of concurrency, failure, and reconfiguration.