The Transaction Concept: Virtues and Limitations

In one breath — the whole paper, compressed

Gray takes the transaction, an idea he traces to contract law, and states it as three properties: consistency (the transformation obeys the system's constraints), atomicity (it either happens or it does not), and durability (once committed it cannot be abrogated). He argues the transaction is the right abstraction for fault-tolerant programming, because a NonStop-style system built from fail-fast modules and process pairs is still far too subtle to program directly, whereas BEGIN, COMMIT and ABORT hide all of that from the application. The paper then sets the two known implementations side by side: time-domain addressing, in which an object is addressed by name plus time and is evolved rather than updated, and logging plus locking, in which a DO-UNDO-REDO log records old and new values while locks hide uncommitted output. Gray concludes the two are more similar than different internally, since a timestamped log is already a version history and version systems garbage-collect old versions into something that looks like a log. The last third of the paper is the honest part: the model cannot nest transactions, assumes transactions last minutes rather than weeks, and does not fit conventional programming languages, and Gray's proposed escapes deliberately trade atomicity away.

Before this paper — the world it landed in

By 1981 the accounting discipline that computing inherited had been quietly abandoned. Tape-era batch runs read an old master plus the day's cards and wrote a new master, so the old state was never destroyed; direct access discs made it cheap to rewrite only the changed part, and Gray says most disc-based systems were seduced into updating in place. Concurrency control was still folklore in production: IMS/360 tried to predeclare each transaction's read and write sets and intersect them at scheduling time, and abandoned that intent scheduling in 1973. Fault tolerance was a separate craft again, done with duplexed discs since the late sixties and, at Tandem, with process pairs in which a primary checkpoints its state to a backup, a handoff Gray calls delicate and very subtle to resynchronize. Meanwhile application programmers were hand-rolling multi-step recovery in IMS scratchpads and CICS transaction work areas, keeping their own log as a record in the database, because the system gave them nothing for work that spanned more than one interaction.

The problem — what was actually breaking

Even a hypothetically perfect system still fails, because the people who adapt it make application programming errors and the people who operate it make data-entry and procedural errors, so at least one transaction in 100 aborts for reasons the hardware and software cannot prevent.
Given a highly available system, writing fault-tolerant applications on top of it is still non-trivial: takeover by the backup process must continue the computation where the primary left off without propagating the failure to other processes, and resynchronizing requestor and server is very subtle.
Update in place destroys the old value, which violates the accounting rule that the books are never altered, so nothing in the system remembers how to get back to the previous consistent state unless some mechanism is added on purpose.
If transactions run concurrently, one may read the updates or messages of another that later aborts; undoing the first then requires undoing the second, which may already have committed and therefore cannot be undone.
Transactions cannot be nested inside transactions, so a travel agent booking flights, cars and hotels has no way to express a scenario that the customer regards as one transaction but that the airlines and hotels see as separate committed transactions.
Transactions are assumed to last minutes rather than weeks, so applications in travel, insurance, government and electronic mail would produce thousands of concurrent long-lived transactions, and deadlock frequency rises with the square of the multiprogramming level and the fourth power of transaction size.

Core ideas — the contributions, and why they work

Transactions come from contract law

Gray grounds the concept not in computing but in contracts: parties negotiate, then a joint signature or a handshake makes the deal binding, and suspicious parties appoint an escrow officer to coordinate commitment. From this he reads off three properties: consistency, meaning the transaction obeys legal protocols; atomicity, meaning either all parties are bound or none are; and durability, meaning a committed transaction cannot be abrogated. The framing matters because it also supplies the repair mechanism: a contract cannot simply be annulled, so a bad transaction is adjusted by further compensating transactions. This is the same move that later rescues nested and long-lived transactions, and it is why compensation appears in the paper as a first-class concept rather than an afterthought.

You do not need a perfect system

One way to get atomicity and durability is to build hardware and software that never fail, but Gray argues that path is both impossible and unnecessary. Von Neumann showed a reliable system can be built from unreliable components, but his flat nerve-net model needed 20,000 wires for one wire because any failure in a chain broke the chain. Computer systems are hierarchically composed of fewer than about 100 modules, and each module can be made fail-fast, meaning it either works correctly or detects its own failure and does nothing. Fail-fast plus spares plus duplexing turns modules with mean times to failure measured in months into systems with mean times to failure measured in centuries, so a system that fails once every thousand years is good enough.

The transaction as the fault-tolerance interface

Gray's central argument for the transaction is not correctness in the abstract but programmability. The alternative technique, checkpointing state from a primary process to a backup before each operation, forces every application author to reason about failover and resynchronization. Instead, collect all the processes of a computation into a transaction and reset them all to the initial transaction state on failure, letting a new process continue from a save point or from the beginning. The implementers of the transaction concept must still wrestle with process pairs and NonStop subtleties, but thereafter every programmer writes ordinary code plus three verbs: BEGIN-TRANSACTION, COMMIT-TRANSACTION and ABORT-TRANSACTION.

Time-domain addressing as a unified answer

In Reed's proposal an object is never altered; it is evolved, so an entity E carries a sequence of values each valid over a time interval, and an address becomes a name together with a time rather than just a name. Every transaction is assigned a unique time of execution and all of its reads and writes are interpreted with respect to that time, so reading E at time T3 returns whatever value was current then. Reed observes that this is a unified solution to both the concurrency control problem and the reliability problem, since the same version history that gives you recovery also gives you a consistent read. It also gives the application the full power of time travel, so one can simply ask what the books looked like at year-end.

Logging and versioning are the same thing inside

This is the paper's sharpest structural observation. Logging systems must make undo and redo restartable, which they do by tagging objects or object fragments with version numbers, so most logging schemes already contain a form of time-domain addressing. Conversely, if each log record carries a timestamp then the log implements time-domain addressing, and time-domain schemes garbage-collect old versions into something that looks very much like a log while using locks to serialize updates of object headers. Gray concludes that despite the external differences the two are more similar than different in their internal structure, and reports Reed's claim that every locking and logging trick has an analogous trick for time-domain addressing.

Compensation for what cannot be undone

When a step has already committed at another organization, no recovery manager can roll it back; only a compensating transaction can reverse it. Gray therefore adds a fourth class of component to the transaction model: nested transactions, which may be undone by invoking a compensating transaction, alongside unprotected, protected and real actions. A nested transaction returns as a side effect the name and parameters of its compensating transaction, which the parent stores in its log and invokes if the parent is undone. He is candid that nested transactions differ from protected actions precisely because their effects are visible outside before the parent commits, so they keep consistency and the commit or compensate discipline but give up atomicity.

Transactions belong in the language

Gray proposes the verbs BEGIN, SAVE, COMMIT and ABORT as language constructs, and works out what a new abstract data type must supply to participate. Whenever a new object type and its operations are defined, protected operations on that type must generate undo and redo log records and acquire locks if the object is shared, and the type manager must provide UNDO and REDO procedures that accept those log records and reconstruct the old and new versions. Real operations must be deferred so the log manager can invoke the type manager at commit time, and nested operations must place the compensating transaction's name and inputs in the undo log. The type manager must also participate in system checkpoint and restart, and Gray admits he is not sure this generalizes beyond data processing, or that logging's performance will be tolerable.

How it works — the mechanism, concretely

System state, constraints, and three classes of action

A system state consists of records and devices with changeable values, plus assertions about those values and about the allowed transformations, which Gray calls the system consistency constraints. A transaction is a group of actions that together form a consistent transformation, carrying the state from one consistent state to another. Actions are classified by their reversibility: unprotected actions need not be undone or redone, such as operations on temporary files and transmission of intermediate messages; protected actions can and must be undone or redone, such as conventional database and message operations; and real actions cannot be undone once done, such as commitment itself and operations on cash dispensers and airplane wings. Each transaction has exactly one of two outcomes, committed or aborted: all protected and real actions of committed transactions persist even across failures, and none of the effects of an aborted transaction are ever visible to other transactions.

Time-domain addressing: versions, intervals and commit records

An entity E holds a set of values Vi, each valid for a half-open time period, so E might read as V0 valid over T0 to T1, V1 over T1 to T2, and V2 from T2 to the present. A transaction with execution time T3 that reads E gets the value current at T3 and, in doing so, extends that version's validity interval up to T3, which is why reads behave like writes. A transaction at T3 that writes V3 starts a new interval beginning at T3, but if the object's current interval already starts at or after T3 the transaction is aborted for attempting to rewrite history. All writes of a transaction depend on a commit record; at commit the system validates every update by setting the commit record's state and broadcasting the outcome, and at abort it invalidates them the same way. Reed uses pseudo-time rather than real time to avoid needing a global clock, and the full proposal includes its own nested transaction mechanism.

The log record and the DO-UNDO-REDO protocol

Every undoable action must both do the action and leave behind an undo log record that allows it to be undone; every redoable action must leave a redo log record. A database log record carries the transaction name, pointers to the previous and next log records of that same transaction, a time, the operation type, the object of the operation, and the old and new values. Old and new values can be complete copies but typically encode only the changed parts, so a field update logs the file, record and field names with the old and new field values rather than the whole record. The log records of a transaction are threaded together, so undo walks the thread backwards, and this same machinery serves both a program-issued abort and cleanup of incomplete transactions after deadlock or hardware failure. The records must live in stable storage, usually several non-volatile devices with independent failure modes, and a stable copy of each object should be taken occasionally so the current state can be rebuilt from an old state plus the redo log.

Deferred real actions and restartable undo/redo

Because a real action cannot be undone, it must not happen before the outcome is known, so it is deferred: the action initially generates only a redo log record, and at successful commit the recovery system uses that deferred log to perform the action for the first time. These deferred actions are named, for example by sequence number, so duplicates are discarded. Separately, undo and redo themselves must be restartable, meaning that applying them to an object that is already undone or redone must not damage or change it, because failures can occur during undo and redo processing. Restartability is achieved with version numbers for disc pages and sequence numbers for virtual circuits or sessions: the operation reads the number, does nothing if it is already the desired number, and otherwise transforms both the object and the number.

Two-phase commit across multiple logs

Commit is signaled by writing the commit record to the log, but a transaction that has contributed to several logs, as in a distributed system with one or more logs per node, must have the commit appear in all logs or none. The simplest scheme lets only the active node decide, with all other participants as slaves that look to it for the outcome. It is generally desirable, though, to let each participant unilaterally abort before commit, and two-phase commit exists to minimize the window in which that right is suspended: the coordinator asks each participant to prepare, and a participant abdicates its right to unilaterally abort once it answers yes. If all agree, the coordinator broadcasts commit; without unanimous consent the transaction aborts. Gray's analogy is the wedding ceremony, where the minister asks Do you, the participants say I do or refuse, and only then does he pronounce them married or call the deal off.

Locking: computing the input and output sets

The requirement is stated abstractly first: a transaction has an input set I and an output set O, other transactions may read I but must not read or write O, and inputs must additionally be held stable so that rereading a record does not give two different answers. Schemes that guess I and O in advance and intersect them at scheduling time were tried by IMS/360 and widely rediscovered, but have not been very successful, and IMS abandoned this intent scheduling in 1973. The simpler and more efficient scheme locks each object when it is accessed, computing I and O dynamically, with two modes so that read locks are compatible with each other while update locks are not. Granularity is handled by picking a fixed set of predicates, organizing them into a directed acyclic graph and locking from root to leaf, a compromise between the generality of arbitrary predicate locks and their expense. Deadlock must then be detected by timeout or by finding cycles in the who-waits-for-whom graph, after which victims are chosen, aborted using the log, and their locks released.

Nested transactions, save points and sleeping transactions

A nested transaction runs and returns, as a side effect, the name and parameters of its compensating transaction; the parent keeps this in its log and invokes it if the parent is undone. Gray insists this log be user-visible, that is, part of the database, so the user and application can see what has been done and what still needs to be done or undone, and notes that if all else fails the compensating transaction can simply send a human the message that it cannot handle this. For long-lived transactions he proposes accepting a lower degree of consistency so that only actively updating transactions hold locks while sleeping ones hold none, which exposes uncommitted updates and therefore requires that one transaction's UNDO and REDO commute with another's DO. Logging the delta rather than the old and new value makes this work for additions and subtractions, the trick IMS Fast Path already uses to reduce lock contention. Finally, save points let active transactions survive system restart: a transaction declares a save point and, at restart, program and data are reset to the most recent one rather than the transaction being discarded.

What the paper showed — measurements and proofs

Duplexing arithmetic for discs: a typical disc fails about once a year and takes about an hour to fix or replace, so a mirrored pair failing independently is down about once every three thousand years, with more realistic analysis giving a mean time to failure of 800 years; a system with eight disc pairs then has an unavailable pair about once a century, versus an unavailable disc about eight times a year without mirroring.
The fail-fast argument against brute-force redundancy: Von Neumann's flat majority-logic scheme needed 20,000 wires for one wire because any failure in a chain broke the chain, whereas a hierarchically composed computer system has typically fewer than 100 self-checked modules with mean times to failure measured in months, so very limited redundancy plus spares that give mean time to repair in seconds or minutes yields mean times to failure measured in centuries.
Field data from commercial systems: Tandem NonStop systems typically have mean times to failure between one and ten years, and the residual failures are operator error at about one per year and application program errors at several per year, so the vendor's hardware and software are no longer the limiting factor.
Failures the transaction system cannot design away: even in an otherwise perfect system at least one transaction in 100 fails due to data-entry or authorization error, citing the Japanese reliable-business-systems tutorial, which is why abort must be a normal, cheap operation rather than an exceptional one.
Concurrency control statistics: waits are rare at about one transaction in 1000 and deadlocks are rarer still, but deadlocks per second rise as the square of the degree of multiprogramming and as the fourth power of transaction size, which is the quantitative basis for the paper's warning about long-lived transactions.
The scale being extrapolated from: the largest airlines and banks then had about 10,000 terminals with about 100 active transactions at any instant, each living a second or two, whereas travel, insurance, government and electronic mail applications would produce thousands of concurrent transactions lasting days or weeks.

Limits and trade-offs — conceded and discovered

The paper's own critique of time-domain addressing lists four problems: reads are writes because they advance an object's clock and update its header, increasing I/O; waits become aborts because conflicts abort the writer instead of making it wait, which may preclude long-running batch transactions; timestamps force a single granularity, so reading a million records updates a million timestamps where a lock hierarchy would allow whole-file and single-record locking at once; and it is unclear how real operations on real devices, read or written at some real time, correlate with pseudo-time. Gray concedes all but the last are performance issues that implementers may well solve.
The paper concedes that its nested transactions are not really transactions: others can see their uncommitted updates, which may later be undone by compensation, so they retain consistent transformation and the commit-or-compensate discipline and the BEGIN, COMMIT and ABORT verbs, but give up atomicity outright.
The paper concedes that its answer for long-lived transactions rests on an unproven generalization. Accepting a lower degree of consistency requires UNDO and REDO to commute with other transactions' DO, which works when the log records deltas over operations like plus and minus, as IMS Fast Path exploits, and Gray writes plainly that no one knows how far this trick can be generalized.
The paper concedes deep uncertainty about the programming-language proposal: Gray is not sure the idea works in the general case, doubts whether the transaction concept generalizes to non-data-processing areas of programming, and warns that the performance of logging may be prohibitive. He closes by invoking the Peter Principle against his own subject.
Later work exposed what the paper leaves out. Isolation is never named as a separate property here, even though the mechanisms enforce it; Haerder and Reuter added the I and coined ACID in 1983. Two-phase commit is presented as the answer for multiple logs without confronting its blocking behavior when the coordinator fails after the prepare phase, a gap addressed later by three-phase commit and by consensus-based commit built on Paxos. And compensation-based nesting cannot restore serializability, which Garcia-Molina and Salem made explicit when they formalized sagas in 1987.

What it became — the systems that inherited it

This paper is where the transaction stopped being folklore and became a named abstraction with an agreed property list; Haerder and Reuter added isolation and turned Gray's three properties into ACID two years later, and Gray and Reuter's 1993 book Transaction Processing: Concepts and Techniques is essentially this paper's program carried out in full. The DO-UNDO-REDO protocol with threaded per-transaction log records, restartability via page version numbers, and deferred real actions is the direct ancestor of ARIES, whose log sequence numbers are exactly the version-number trick generalized, and through ARIES it reaches DB2, SQL Server, PostgreSQL, MySQL InnoDB and effectively every write-ahead-logging engine shipping today. The two-phase commit description became the reference presentation for distributed commit, standardized as X/Open XA and still the model for cross-shard commit in systems like Spanner, which layers Paxos underneath precisely to fix the coordinator-blocking problem Gray does not address. Time-domain addressing, which Gray reports from Reed's MIT work, is the lineage of multiversion concurrency control and snapshot isolation in PostgreSQL, Oracle and InnoDB, and of time-travel queries in Spanner, Datomic, Delta Lake and Apache Iceberg, vindicating Gray's claim that logging and versioning are the same structure viewed from different sides. His nested-transaction sketch was formalized by Moss and built into Argus by Liskov's group, the very work he cites as in progress. Most durably, the long-lived-transaction section, with its compensating transactions, save points and deliberately lowered consistency, is the origin of sagas and of the compensation-based workflow patterns that microservice architectures, Temporal-style orchestrators and business process engines rediscovered decades later.

In the paper’s words — verbatim

“A transaction is a transformation of state which has the properties of atomicity (all or nothing), durability (effects survive failures) and consistency (a correct transformation).”

Abstract

“To give a preview of the two techniques, logging clusters the current state of all objects together and relegates old versions to a history file called a log. Time-domain addressing clusters the complete history (all versions) of each object with the object.”

NonStop: Making failures rare

“This example makes it clear that actions may be transactions at the next lower level of abstraction.”

Nested Transactions

Vocabulary — as this paper uses it

Transaction: A collection of actions that forms a consistent transformation of the system state, and that is atomic and durable: either all its actions are done and it commits, or none of its effects survive and it aborts. Gray defines it by three properties, consistency, atomicity and durability, and never uses the word isolation.
Real action: An action which, once done, cannot be undone, such as commitment itself, dispensing cash, or moving an airplane wing. Real actions must be deferred until commit, so they generate only a redo log record which the recovery system applies for the first time after the commit decision.
Compensating transaction: A further transaction run after the fact to reverse or adjust the effects of one that has already committed, since a committed transaction cannot be abrogated. Gray takes the idea from contract law and from double-entry bookkeeping, where an error is annotated and a new offsetting entry is made rather than the books being altered.
Fail-fast module: A self-checked component that either operates correctly or detects its own failure and does nothing, never doing the wrong thing silently. Because a system is built hierarchically from fewer than about 100 such modules with mean times to failure measured in months, duplexing them plus quick spares yields system mean times to failure measured in centuries.
Time-domain addressing: An implementation style in which objects are never updated but evolved, so an address is a name together with a time and each entity holds a sequence of values with validity intervals. Also called version-oriented systems; Gray rejects the label immutable object systems as a misnomer, since objects do change values with time.
DO-UNDO-REDO protocol: The rule that executing a protected action must both perform it and emit log records sufficient to undo it and to redo it, while unprotected actions and pure reads need emit nothing. Undo walks the transaction's threaded log records backwards; redo replays committed actions forward onto an old stable copy to reconstruct lost state.
Restartability: The property that applying UNDO or REDO to an object which has already been undone or redone leaves it unchanged, needed because failures can occur during recovery processing itself. It is implemented by tagging objects with version numbers for disc pages or sequence numbers for sessions, and skipping the operation when the number already matches.
Two-phase commit: A commit protocol in which the coordinator first asks every participant to prepare, and a participant that answers yes abdicates its right to unilaterally abort; if consent is unanimous the coordinator broadcasts commit, otherwise the transaction aborts. Its purpose is to minimize the time during which a node is not allowed to unilaterally abort.
Save point: A declared intermediate state to which a transaction's program and data can be reset instead of being aborted entirely. Gray proposes save points so that active long-lived transactions survive system restart, since discarding 10,000 in-flight transactions at restart is inconceivable even though discarding 100 is merely unpleasant.

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