Consistent state detection and recovery for concurrent processing

This thesis describes distinct features and consistency constraints of the two types of concurrent processing in distributed systems: type (1) concurrent database accesses, and type (2) concurrent checkpointing and rollback-recovery of multiprocesses. More efficient synchronization mechanisms have been developed. For type one, the thesis extends single-valued timestamp ordering to vectorized timestamp ordering. This new mechanism enforces a partial order among concurrent database transactions, and provides a higher degree of concurrency as the vector size increases. The thesis also analyzes algebraic properties of timestamp vectors, designs a parallel processing scheme for vectors, and extends this mechanism for the nested transaction model. For type two, the thesis designs a transaction model for concurrent checkpointing and recovery in distributed systems. We have shown that the consistency of recovery lines and rollback lines established by checkpoint transactions and rollback transactions can be assured by enforcing serializability on the corresponding transactions. An algorithm is designed to construct and execute checkpoint transactions or rollback transactions concurrently. The algorithm supports efficient recovery, reduces the response time of transactions, and allows normal messages to be transmitted in any order. The algorithm is evaluated experimentally. The thesis analyzes the performance, and provides guidelines for efficient applications of the algorithm