CMU-CS-85-114

Computer Science Department
School of Computer Science, Carnegie Mellon University


CMU-CS-85-114

Modular Concurrency Control and Failure Recovery -- Consistency, Correctness and Optimality

CMU-CS-85-114

Lui Sha - Thesis oot Department of Electrical and Computer Engineering

March 1985

A distributed computer system offers the potential for a degree of concurrency, modularity and reliability higher than that which can be achieved in a centralized system. To realize this potential, we must develop provably consistent and correct scheduling rules to control the concurrent execution of transactions. Furthermore, we must develop failure recovery rules that ensure the consistency and correctness of concurrency control in the face of system failures. Finally, these scheduling and recovery rules should support the modular development of system and application software so that a transaction can be written, modified, scheduled and recovered from system failures independently of others.

To realize these objectives, we have developed a formal theory of modular scheduling rules and modular failure recovery rules. This theory is a generalization of the classical works of serializability theory, nested transactions and failure atomicity. In addition, this theory addresses the concepts of consistency, correctness, modularity and optimality in concurrency control and failure recovery. This theory also provides us with provably consistent, correct and optimal modular concurrency control and failure recovery rules.

Currently, this theory is being used in the development of the ArchOS decentralized operating system at the Computer Science Department of Carnegie-Mellon University.

104 pages


Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu