Multiversion concurrency control—theory and algorithms

TLDR

Concurrency control synchronizes operations from concurrently executing programs on a shared database, and in multiversion systems each write creates a new data item version. The paper aims to produce serial‑equivalent executions and introduces a theory for analyzing correctness of multiversion concurrency control algorithms. The authors apply the theory to analyze both new and previously published multiversion concurrency control algorithms. The analysis confirms the correctness of the examined algorithms.

Abstract

Concurrency control is the activity of synchronizing operations issued by concurrently executing programs on a shared database. The goal is to produce an execution that has the same effect as a serial (noninterleaved) one. In a multiversion database system, each write on a data item produces a new copy (or version ) of that data item. This paper presents a theory for analyzing the correctness of concurrency control algorithms for multiversion database systems. We use the theory to analyze some new algorithms and some previously published ones.