Eight Transaction Papers by Jim Gray

In one breath — the whole paper, compressed

Philip Bernstein revisits eight of Jim Gray's transaction papers, spanning 1976 to 2006, and shows how the transaction abstraction was assembled piece by piece. The 1976 CACM paper with Eswaran, Lorie and Traiger defined a transaction as a consistency-preserving unit, set serializability as the correctness goal, invented two-phase locking, and named the phantom problem; the companion granularity paper added intention locks and degrees of consistency, which SQL later renamed isolation levels. Later papers formalized logging, recovery and atomic commitment, separated the transaction commit problem from Byzantine agreement, showed that ANSI SQL's SERIALIZABLE level is not actually serializable, quantified why replication does not scale, and finally fused Paxos with two-phase commit into Paxos Commit. Read together, the eight trace the field's arc from "what does correct concurrency even mean" to "how do we commit a distributed transaction without blocking". Bernstein writes as a participant: he was a coauthor on one of the eight and spent his career following Gray's footsteps.

Before this paper — the world it landed in

Before 1976 it was already understood that concurrent reads and writes on shared data cause trouble. Two programs each adding 1 to a shared variable x, both reading x before either writes it, lose one update; a reader that sees Account 1 before a $100 transfer and Account 2 after it sees a database that never existed. Locking was known to be the remedy, but setting and releasing locks was the application program's job, with little guidance about exactly which locks should be set and when. There was no agreed name for the unit of work that locks were meant to protect, no stated correctness criterion for a concurrent execution, and no proof that any particular locking discipline achieved one. Commercial systems of the era, IBM's IMS/VS and UNIVAC's DMS 1100 among them, each had their own ad hoc locking behavior, which Gray's granularity paper surveys at the end.

The problem — what was actually breaking

Concurrency anomalies such as lost updates and inconsistent reads were well known, but locking was left to the application programmer with little guidance about exactly which locks should be set and when.
There was no stated correctness criterion for a concurrent execution, so no locking discipline could be proved correct or compared against another.
Locking every record one by one is prohibitively expensive for a transaction that touches most or all records in a file, yet a coarse file lock and another transaction's fine record locks must still be detected as conflicting.
Two-phase locking over the records that happen to exist does not stop the phantom problem, where a row inserted by another transaction invalidates a set-retrieval that already completed; predicate locks fix it but checking mutual satisfiability of predicates is in general computationally expensive.
Full serializability throttles throughput, so weaker isolation is used everywhere, but ANSI SQL-92 defined isolation levels by a list of prohibited phenomena that lets plainly non-serializable executions pass as SERIALIZABLE.
Replicating a database for availability and disconnected use creates deadlock or reconciliation storms that grow steeply with the number of nodes, while two-phase commit blocks resource managers whenever the transaction manager fails.

Core ideas — the contributions, and why they work

The transaction abstraction

The 1976 CACM paper by Eswaran, Gray, Lorie and Traiger defined a transaction as a sequence of operations over a shared state made of entities, such as the records of a file or the tuples of a relation, and assumed that each transaction preserves the internal consistency of that state. That single definition moved lock placement from the application programmer to the system: once reads and writes are grouped into a named, consistency-preserving unit with a defined beginning and a commit or abort at the end, the system knows what interval a lock must cover. The 1981 paper sharpened the abstraction by likening it to contract law, where two parties make a binding agreement, and by listing its properties as consistency, atomicity and durability, with isolation subsumed under consistency. Commit is precisely the act of giving up the right to discard the updates; abort discards them all. This is the abstraction the rest of the field is built on.

Serializability as the correctness goal

The paper's second contribution was to state what correct concurrency actually means: an interleaved execution is correct if it has the same effect as some serial, non-interleaved execution of the same transactions. The argument for why this is the right criterion is compositional. Each transaction, run alone, preserves the consistency of the state by assumption, so any serial execution of transactions does too; if the real execution is equivalent to some serial one, it inherits the guarantee for free. The programmer therefore never has to reason about interleavings, only about one transaction at a time, and the system is left free to interleave as aggressively as its protocol permits.

Isolation levels, and their broken specification

The granularity paper observed that full two-phase locking is often more isolation than an application needs, and defined a hierarchy of weaker locking protocols called degrees of consistency, distinguished purely by how long read and write locks are held. Nineteen years later the ANSI SQL-92 committee, needing definitions that also admitted non-locking implementations, respecified those levels in terms of three prohibited behaviors: dirty read, non-repeatable read and phantom. The 1995 critique by Berenson, Bernstein, Gray, Melton and the O'Neils showed that this reformulation is not merely inelegant but wrong: prohibiting the three phenomena does not imply serializability. Snapshot isolation, a real and popular protocol, prohibits all three and still admits executions with no equivalent serial order, so the standard's claim that SERIALIZABLE executions are guaranteed to be serializable is false. The lesson generalizes past SQL: defining isolation by a list of anomalies you have thought of leaves out the ones you have not.

Compensation and the honest edges of ACID

The 1981 paper is the field's first honest accounting of what transactions cannot do. It classifies actions rather than entities: unprotected actions need not be undone on abort; real actions, such as an ATM dispensing money, cannot be undone by the computer at all; only protected actions are undone on abort and made durable on commit. Once a transaction has committed, the only way to change its effects is to run another transaction, which this paper appears to be the first to call a compensating transaction. It also compares the two implementation families for atomicity and durability, time-domain addressing (what we now call multiversioning, where each update creates a new timestamped version and a consistent state at time t is the set of versions with the largest timestamp at or before t) against logging with update in place, and it closes by naming three things then beyond the state of the art: nested transactions, long-lived transactions and transactions in programming languages. Those three were the field's agenda for the next 25 years.

A formal model of failure and recovery

The 1980 ICALP paper consolidated the mathematics. It distinguishes three kinds of entity by durability: real entities whose values cannot be changed, such as printed output; stable entities that are changeable and durably stored and so survive restart; and volatile entities that are changeable but lost on restart. It then distinguishes transaction failure, where a transaction loses its state and must be restarted, from system failure, where all volatile entities including every running transaction's internal state are lost. Logging modifications lets a recovery procedure redo logged updates and return the system to its state shortly before the failure, and this paper was among the first, possibly the first, to define formally what conditions a checkpointed state and its redo actions must satisfy for that to be correct. The same paper contributes a performance model showing that a given transaction's deadlock probability is linear in the degree of concurrency, and gives a formal characterization of atomic commitment and of why Lampson and Sturgis's two-phase commit satisfies it.

Commit is consensus, but a peculiar kind

Atomic commitment looks like the Byzantine Generals Problem and is not. Gray's 1986 Asilomar note pinned down four differences: commit requires that all participants make the same decision, not merely all non-faulty ones; a commit protocol tolerates many faults including message loss from a working process, whereas Byzantine agreement needs fewer than N/3 of N processes faulty; a commit protocol never returns an incorrect result while a Byzantine protocol can once that bound is exceeded; and a Byzantine protocol decides within a fixed time bound while a commit protocol provably cannot, because operational processes may simply not know what a failed process decided and unanimity is required. The 2006 paper with Leslie Lamport then took the other half of the relationship seriously: atomic commitment is a consensus problem, so solve it with a consensus algorithm. Paxos Commit's insight is that three-phase commit really contains two consensus rounds, one to reach the commit decision and one to make it survive further failures, and that they collapse into one if you reach consensus on the prepare decision instead of on the commit decision.

Replication's quadratic price

The 1996 paper laid out the four ways to update a replicated database, as the cross product of update-everywhere versus primary-copy with eager versus lazy propagation, and showed that three of them scale badly. Update-everywhere with eager propagation deadlocks whenever two nodes concurrently update the same item, because each transaction's remote write waits on the other's local lock; the governing ratio is propagation delay against the interarrival time of conflicting transactions, so deadlock rate climbs steeply with both conflict rate and degree of replication. Update-everywhere with lazy propagation trades deadlocks for equally frequent manual reconciliation, and works in Lotus Notes only because most Notes updates are commuting timestamped insertions rather than overwrites. Lazy primary-copy converges via Thomas' Write Rule, applying a write only if its timestamp exceeds every timestamp already applied, but still lets a query read a node where a later write has landed and an earlier one has not. Eager primary-copy is the survivor, because writes reach every replica in the primary's order, and it is what today's distributed databases mostly use.

How it works — the mechanism, concretely

The three rules of two-phase locking

A transaction must acquire a lock on each entity before accessing it; it must hold that lock until after it is done accessing the entity; and it must acquire all the locks it needs before it releases any of them. The third rule is the one that does the work: it splits every transaction into a growing phase in which locks are only acquired and a shrinking phase in which they are only released, which is why the protocol is called two-phase. Because no transaction can acquire a lock after releasing one, conflicting transactions can be ordered by the moment each reached its lock point, and that ordering is a serial order the execution is equivalent to. The paper proves this, giving the field its first correctness theorem for a concurrency control protocol.

Predicate locks and the hidden read behind a set query

The canonical counterexample uses an Accounts table [Account#, Location, Balance] and an Assets table [Location, Total], consistent when the balances for a location sum to that location's Total. An audit transaction T1 locks every Accounts row with Location = 'Napa'; T2 then inserts a new Napa account and adds its balance to the Napa Total, commits and releases; T1 then locks the Assets row and finds the sum no longer matches, even though both transactions were two-phase locked. The resolution is that step one contains a hidden operation, namely whatever T1 read to determine which rows are Napa rows: an index entry, or a table scan running to the end-of-table marker. If T1 had locked that data item, T2's insert would have had to update it and would have been blocked, so the anomaly could not occur. The paper's general fix is to lock predicates such as Location = 'Napa', or Boolean combinations like ((Location = 'Napa' or Location = 'Santa Rosa') and Balance < 200), granting a request only if no other transaction holds a mutually satisfiable predicate lock on the same table, which is exact but in general computationally expensive.

Multigranularity locking with intention modes

Lockable entities are organized into a hierarchy such as database, area (a disk volume), file, record, where a lock on an entity implicitly locks all of its descendants. To keep a coarse S or X lock from coexisting with another transaction's X lock on a descendant, the protocol adds intention modes: an IS lock on entity e announces that its owner holds or will hold S locks below e, and an IX lock announces X locks below e. IS is therefore incompatible with X on e, and IX is incompatible with both S and X on e, so a transaction that intends to lock records must first intention-lock the file, and any transaction wanting the whole file is stopped there. SIX combines shared access to the entity itself with the right to set X locks on descendants, which is exactly what a transaction that reads a whole file and updates part of it needs. The paper also handles the case where the hierarchy is a directed acyclic graph rather than a tree, as when a record is reachable both by scanning a file and by an index on one of its fields, including what happens when an update moves a record from one index range to another and threatens a phantom.

Degrees 0 through 3 as lock-duration rules

Degree 0 holds an X lock only while the update is being performed, a short duration lock released before commit; this permits both reading and overwriting dirty data, so an abort by T1 forces a cascading abort of any T2 that read from it, and a T2 that already committed lands in a catch-22 where its updates must be both permanent and undone. Degree 1 makes the X lock long duration, held until after commit, which stops a transaction from overwriting dirty data and removes the tangled bookkeeping of chained uncommitted updates on one entity. Degree 2 adds a short duration S lock before every read, guaranteeing that only committed data is read; it is what we now call Read Committed. Degree 3 promotes that S lock to long duration, at which point the transaction is fully two-phase locked and therefore serializable, modulo the phantom problem; it is what we now call Repeatable Read at the standard's naming and Serializable at Gray's.

Snapshot isolation: start timestamps and first-writer-wins

Each transaction is assigned a start timestamp st when it begins and, if it commits, a commit timestamp ct greater than any previously assigned, which is attached to every version it wrote. A read of an entity returns the version with the largest commit timestamp less than or equal to st, so the transaction sees one frozen snapshot of committed state and is immune to concurrent activity, which is why it avoids dirty reads, non-repeatable reads and phantoms as the standard defines them. At commit the system inspects every entity the transaction wrote and aborts it if any of them was updated by a transaction that committed with a timestamp greater than st, the first-writer-wins rule, which is what prevents ordinary lost-update race conditions. What survives is the write-skew execution: T1 and T2 read both X and Y from the same snapshot, T1 writes X, T2 writes Y, neither wrote what the other wrote, both commit, and no serial order reproduces the outcome because in any serial order one would have read the other's output.

Two-tier replication with Tentative Mode

The 1996 paper's proposed answer to disconnected operation splits nodes into base nodes, which hold the entire database and stay mutually connected, and disconnected nodes, which usually hold only part of the database and connect only occasionally. Every data item has a designated primary copy, which may live on either kind of node. A disconnected node N may run any transaction over data stored at N, but if N lacks the primary copy of something the transaction reads, the transaction runs in Tentative Mode. On reconnection N first discards the versions written by Tentative transactions, since they will be refreshed anyway, then ships its Tentative transactions and the results of its non-Tentative transactions to the base node and accepts the base node's replica updates, all of which are non-Tentative. The base node installs the non-Tentative results, re-runs each Tentative transaction against the primary copies, and where the new output differs from the original it applies an application-specific acceptance test, installing the updates and returning the result if the test passes and a diagnostic message if it does not.

Paxos Commit's message flow

Classical two-phase commit has a transaction manager (TM) and resource managers (RMs): the TM sends Prepare-Request to all RMs, each RM writes the transaction's updates to persistent storage and replies Prepared, and the TM writes its decision to persistent storage and sends Commit, three one-way message delays in the failure-free case. Three-phase commit adds backup TMs and two more delays, because the primary must notify the backups and collect their acknowledgements before telling the RMs. Paxos Commit instead gives each RM its own Paxos instance over a shared set of acceptors: the leader sends Prepare-Request, each RM sends its Prepared straight to the acceptors, each acceptor forwards Prepared to the leader, and when the leader has seen a majority of acceptors report Prepared for every RM the transaction is committed and Commit goes out. That is four message delays, one fewer than three-phase commit, and the majority of acceptors accepting Prepared substitutes for the TM writing the decision to storage while the acceptors themselves play the role of backup TMs. An acceptor participating in every RM's instance can batch, waiting until it has Prepared from all RMs and sending the leader one message; a further optimization has acceptors send Prepared to all RMs so each RM decides commit itself, trading extra messages for one fewer delay.

What the paper showed — measurements and proofs

Eswaran, Gray, Lorie and Traiger proved that any execution in which every transaction obeys the three two-phase locking rules has the same effect as a serial execution of those transactions, the property now called serializability, subject to the phantom caveat that the data item identifying a retrieved set must also be locked.
The 1980 transaction model shows the probability that a given transaction deadlocks is linearly proportional to the degree of concurrency, so the probability that some transaction deadlocks, and hence the system-wide deadlock rate, is proportional to the square of the degree of concurrency, which is the quantitative argument for capping the multiprogramming level.
The 1995 critique reports that throughput under degree 2 isolation can be as much as three times that of two-phase locking, a difference that translates directly into hardware cost, and notes that many vendors report most of their users run at Read Committed.
The same paper's counterexample is fully concrete: T1 and T2 read rows X and Y from a common snapshot, T1 updates X, T2 updates Y, and both commit, producing no dirty read, no non-repeatable read and no phantom, yet no serial order reproduces the result, so the SQL-92 sentence claiming SERIALIZABLE executions are guaranteed to be serializable is false.
Gray's 1986 comparison bounds both problems: Byzantine agreement provably needs at least four generals to tolerate one traitor and is correct only while fewer than N/3 of N processes are faulty, whereas commit protocols never return an incorrect result but provably cannot bound the time to decide, since operational processes may not know what a failed process decided and unanimity is required.
Consensus on Transaction Commit counts message delays exactly: failure-free two-phase commit takes three one-way delays, three-phase commit adds two for the primary-to-backup round trip, and Paxos Commit takes four, one fewer than three-phase commit, because RMs send Prepared directly to the acceptors rather than through the primary TM.

Limits and trade-offs — conceded and discovered

Conceded in the paper: predicate locks, the 1976 answer to phantoms, are exact but impractical, because checking that a requested predicate is not mutually satisfiable with any predicate already locked on the table is in general computationally expensive, which is why the very next paper reaches for multigranularity locking instead.
Conceded, and still unresolved: two-phase locking's throughput cost pushes everyone to weaker isolation, and weaker isolation is unsound. Bernstein notes it is not easy to construct compelling practical examples of snapshot isolation's non-serializable executions, that some systems therefore ship snapshot isolation with no truly serializable option and their customers appear satisfied, and that a serializable strengthening of snapshot isolation only arrived in 2008 with Cahill, Rohm and Fekete.
Raised by Bernstein in hindsight: the 1996 replication model assumes every node stores a full copy of the database and executes transactions at a fixed rate, so each node added both generates work for others and adds its own transaction stream, a quadratic effect. Analyzing added replicas without added transactions would give smaller exponents and less alarming formulas, though the scalability conclusions for all four strategies would be unchanged.
Still open decades later: the 1981 paper's three extensions have not fully landed. Long-lived transactions settled on the notion of workflow but on no specific software abstraction embodying it, and transactional memory, which Gray in 2006 hoped would simplify error handling on multicore machines, has made progress but, Bernstein writes over 15 years later, still has challenging problems remaining.
Conceded in the paper: Paxos Commit's most aggressive optimization, having each RM send Prepared spontaneously once it has persisted the transaction's updates, is unsafe unless the RM knows the transaction has terminated, because it could still receive a later update after announcing Prepared and after the transaction commits. Two-phase commit and Paxos Commit also both assume non-Byzantine participants that follow the protocol and never lose persisted state.

What it became — the systems that inherited it

Multigranularity locking became standard equipment in essentially every SQL database system, and degrees of consistency were rebadged as ANSI SQL-92's isolation levels, which is how Read Committed and Repeatable Read got their names. The 1995 critique reshaped that standard's reputation and set off a line of work culminating in Cahill, Rohm and Fekete's 2008 serializable snapshot isolation, which PostgreSQL adopted for its SERIALIZABLE level, while Oracle still labels plain snapshot isolation SERIALIZABLE, exactly the confusion the paper predicted. Compensating transactions, introduced in the 1981 paper, became sagas in the hands of Garcia-Molina and Salem and are now the failure model of workflow engines and microservice orchestrators; commit-abort dependencies from the ACTA framework serve the same role for ordering steps within a workflow. Gray's insistence that transactions belong in programming languages produced Barbara Liskov's Argus and, much later, transactional memory. Paxos Commit's process structure, treating each resource manager's transition to prepared as its own consensus instance, is the direct ancestor of MDCC, Replicated Commit, Carousel, TAPIR's inconsistent replication, Ocean Vista and Cornus, and of the Paxos-group two-phase commit that Google Spanner runs in production. Behind all of it, Gray and Reuter's 1993 Transaction Processing: Concepts and Techniques remains the book implementers still open when they build these mechanisms.

In the paper’s words — verbatim

“With his many collaborators, Jim created transactions as one of the foundational abstractions of software.”

Introduction

“This arises because T2 is a phantom row, i.e., it comes and goes like a ghost.”

Paper #1

“The insight in Paxos Commit is that these two consensus rounds can be combined into one by reaching consensus on the prepare decision rather than the commit decision.”

Paper #8

Vocabulary — as this paper uses it

Two-phase locking: A locking discipline with three rules: lock every entity before accessing it, hold the lock until after access finishes, and acquire all locks before releasing any. Obeying it makes an execution equivalent to some serial execution of the same transactions.
Serializability: The correctness goal that a concurrent execution has the same effect as some non-interleaved serial execution of the same transactions. Because each transaction preserves consistency on its own, a serializable execution preserves it too.
Phantom problem: A row that appears or vanishes between operations of a transaction that retrieves records by field value, breaking serializability even though both transactions are two-phase locked. The fix is to lock the data item the retrieval actually consulted, such as an index entry or the end-of-table marker.
Predicate lock: A lock that names a set of records by a predicate over their field values, such as Location = 'Napa', rather than by their identities. Granting one requires checking that no other transaction holds a mutually satisfiable predicate lock on the same table.
Intention lock: A weak lock (IS or IX) set on a coarse entity to warn others that its owner holds or will hold finer-grained S or X locks on descendants. IS conflicts with X on the same entity, IX conflicts with both S and X, and SIX combines shared access to the entity with the right to X-lock its descendants.
Degrees of consistency: Gray's four-level hierarchy of locking protocols, distinguished by lock duration: degree 0 holds X locks only during the update, degree 1 holds them until commit, degree 2 adds short read locks, and degree 3 adds long read locks and is therefore two-phase locked. These are what SQL later called isolation levels.
Compensating transaction: A transaction run afterwards to change the effects of an already-committed transaction, since committing gives up the right to discard updates. The 1981 paper appears to be the first to introduce the concept, later generalized by sagas.
Snapshot isolation: A multiversion protocol in which a transaction reads the version of each entity with the largest commit timestamp at or before its start timestamp, and at commit aborts if any entity it wrote was updated by a transaction that committed later, the first-writer-wins rule. It prohibits all three ANSI phenomena yet still permits non-serializable executions.
Paxos Commit: An atomic commit protocol in which each resource manager's transition to the prepared state is decided by its own Paxos instance over a set of acceptors that stand in for backup transaction managers. Reaching consensus on prepare rather than on commit merges three-phase commit's two consensus rounds and saves a message delay.

On the timeline — where this sits in the story

YearLate 1970s–1980s

MilestoneTransaction processing theory and ACID systems

Problem solvedConcurrent users and crashes made database updates unsafe: partial writes, lost updates, dirty reads, and inconsistent state were common risks.

How it solved itTransaction processing theory formalized atomicity, consistency, isolation, durability, commit protocols, locking, and recovery.

Why it matteredCreated the correctness foundation for enterprise OLTP, banking, reservations, inventory, and other mission-critical systems.

DDIACh. 8: Transactions

View on the timeline