Skip to content

Instantly share code, notes, and snippets.

@pbailis
Created November 3, 2015 02:15
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save pbailis/e238e308354616d55cf0 to your computer and use it in GitHub Desktop.
Save pbailis/e238e308354616d55cf0 to your computer and use it in GitHub Desktop.

Distributed concurrency control...is in a state of extreme turbulence. More than 20 concurrency control algorithms have been proposed for DDBMSs, and several have been, or are being, implemented. These algorithms are usually complex, hard to understand, and difficult to prove correct (indeed, many are incorrect). Because they are described in different terminologies and make different assumptions about the underlying DDBMS environment, it is difficult to compare the many proposed algorithms, even in qualitative terms. Naturally each author proclaims his or her approach as best, but there is little compelling evidence to support the claims...

After studying the large number of proposed algorithms, we find that they are compositions of only a few subalgorithms. In fact, the subalgorithms used by all practical DDBMS concurrency control algorithms are variations of just two basic techniques: two-phase locking and timestamp ordering; thus the state of the art is far more coherent than a review of the literature would seem to indicate.

-- Phil Bernstein and Nathan Goodman, 1981

http://www.cs.cmu.edu/~pavlo/courses/fall2013/static/papers/bernstein-1981.pdf

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment