The overhead of locking (and commit) protocols in distributed databases
Ouri Wolfson · ACM Transactions on Database Systems · 1987
The main purpose of a locking protocol is to ensure correct interleaving of actions executed by concurrent transactions. The locking protocol consists of a set of rules dictating how accessed entities should be locked and unlocked. As a result of obeying the rules, transactions in a distributed database incur an overhead. We propose three measures of evaluating this overhead, each most suitable to a different type of underlying communication network. Then, using a graph theoretic model, we analyze and compare three protocols according to each measure: two-phase locking, two-phase locking with a fixed order imposed on the database entities (ensuring deadlock freedom), and the tree protocol. In practice, a transaction also executes the two-phase commit protocol in order to guarantee atomicity. Therefore, the combined overhead of each locking protocol and the two-phase commit protocol is also determined.