Skip to content
About
Main content

What concurrency schemes forbid

What this article forbids

  • Serializability without either waiting or aborting. There is no third currency, except commutativity, which changes the problem instead of solving it.
  • Exact, cheap conflict detection. Every practical scheme is conservative and pays in false conflicts.
  • A long-running transaction concurrent with a high write rate on overlapping data. That is arithmetic, not tuning.
  • Avoiding a collector once you have multiversioned.
  • Isolation behaviour that is independent of physical design. Because predicate locking is intractable, which index exists determines which are taken, which determines which transactions conflict.

Escapes and their prices

EscapePrice
Weaken the guaranteeThe application pays, in anomalies
MultiversionSpace, a collector, and the oldest reader's veto over both
Partition and serializeCross-partition transactions become a cliff, not a slope
DeterminizeNo interactive transactions, advance access sets, a global
Works only where the operation has an algebra
Shrink WThe most underrated of the six, and the only one with no structural cost