Vol. 13, No. 2, June 1981 | PHILIP A. BERNSTEIN AND NATHAN GOODMAN
This paper provides a comprehensive survey of the state-of-the-art in distributed database concurrency control. The authors decompose the concurrency control problem into two major subproblems: read-write and write-write synchronization. They describe various synchronization techniques for each subproblem and demonstrate how to combine these techniques into algorithms that solve the entire concurrency control problem. The paper introduces 48 principal methods, including practical algorithms from the literature and several new ones. The focus is on the structure and correctness of concurrency control algorithms, with performance issues given secondary attention.
The authors begin by defining the concurrency control problem and its challenges in distributed systems, where users may access data across multiple computers. They highlight the differences between distributed and non-distributed concurrency control, noting that the latter has a well-understood mathematical theory and standard solutions like two-phase locking.
The paper then introduces a standard terminology and model for describing DDBMS concurrency control algorithms. It decomposes the concurrency control problem into read-write and write-write synchronization, emphasizing that all practical algorithms use variations of two basic techniques: two-phase locking (2PL) and timestamp ordering (T/O).
The authors discuss the transaction-processing model of a DDBMS, including the roles of transaction managers (TMs) and data managers (DMs), and the interaction between these components. They present centralized and distributed transaction-processing models, detailing how transactions are processed in both environments.
The paper reviews the theory of serializability, defining it as a correct execution that can be transformed into a serial execution. It introduces the concept of conflict between operations and the notion of a serialization order. The authors decompose serializability into read-write and write-write synchronization, suggesting that these can be handled independently.
Two-phase locking (2PL) is discussed as a synchronization technique, with variations such as primary copy 2PL and voting 2PL. The paper also covers centralized 2PL and deadlock detection and prevention techniques, including deadlock prevention and detection methods.
Timestamp ordering (T/O) is introduced as another synchronization technique, where a serialization order is preselected and transactions are forced to follow it. The paper describes the basic T/O implementation and its application in distributed systems.
Overall, the paper provides a detailed analysis of the state-of-the-art in distributed database concurrency control, highlighting the importance of understanding and combining read-write and write-write synchronization techniques to achieve correct and efficient concurrency control.This paper provides a comprehensive survey of the state-of-the-art in distributed database concurrency control. The authors decompose the concurrency control problem into two major subproblems: read-write and write-write synchronization. They describe various synchronization techniques for each subproblem and demonstrate how to combine these techniques into algorithms that solve the entire concurrency control problem. The paper introduces 48 principal methods, including practical algorithms from the literature and several new ones. The focus is on the structure and correctness of concurrency control algorithms, with performance issues given secondary attention.
The authors begin by defining the concurrency control problem and its challenges in distributed systems, where users may access data across multiple computers. They highlight the differences between distributed and non-distributed concurrency control, noting that the latter has a well-understood mathematical theory and standard solutions like two-phase locking.
The paper then introduces a standard terminology and model for describing DDBMS concurrency control algorithms. It decomposes the concurrency control problem into read-write and write-write synchronization, emphasizing that all practical algorithms use variations of two basic techniques: two-phase locking (2PL) and timestamp ordering (T/O).
The authors discuss the transaction-processing model of a DDBMS, including the roles of transaction managers (TMs) and data managers (DMs), and the interaction between these components. They present centralized and distributed transaction-processing models, detailing how transactions are processed in both environments.
The paper reviews the theory of serializability, defining it as a correct execution that can be transformed into a serial execution. It introduces the concept of conflict between operations and the notion of a serialization order. The authors decompose serializability into read-write and write-write synchronization, suggesting that these can be handled independently.
Two-phase locking (2PL) is discussed as a synchronization technique, with variations such as primary copy 2PL and voting 2PL. The paper also covers centralized 2PL and deadlock detection and prevention techniques, including deadlock prevention and detection methods.
Timestamp ordering (T/O) is introduced as another synchronization technique, where a serialization order is preselected and transactions are forced to follow it. The paper describes the basic T/O implementation and its application in distributed systems.
Overall, the paper provides a detailed analysis of the state-of-the-art in distributed database concurrency control, highlighting the importance of understanding and combining read-write and write-write synchronization techniques to achieve correct and efficient concurrency control.