Preemption with Rollback¶
Procedure — instantiates Deadlock Prevention
Allows a resource or commitment to be taken back before a cycle hardens, while rollback restores a coherent prior state.
Preemption with Rollback attacks the no-preemption precondition of deadlock: the assumption that once a participant holds something, no one can take it away. Here, a held resource can be forcibly reclaimed from its current holder when keeping it would let a wait cycle form — and the mechanism's whole subtlety is the second half of its name. Yanking a resource from a participant that was mid-work would leave that participant in a broken, half-finished state, so preemption is always paired with rollback: the victim is wound back to a clean prior checkpoint, as though it had never started, and re-runs later. The defining idea is that possession is revocable but repaired — the system breaks a would-be cycle by taking a resource back, and pays for it by restoring the loser to a coherent state rather than leaving it corrupted.
Example¶
A database runs many concurrent transactions, each locking rows as it goes. Two long transactions are about to deadlock: T-old (started at 10:00:01) holds row X and wants row Y; T-new (started at 10:00:05) holds row Y and wants row X. Under a wound-wait rule, the older transaction is allowed to preempt the younger[1], so when T-old requests Y and finds it held by the younger T-new, the system wounds T-new: it aborts T-new, releases its lock on Y, and — crucially — rolls T-new back through its write-ahead log so every row it had modified is restored to its pre-transaction value. No half-applied update survives. T-old proceeds and commits; T-new is automatically restarted from scratch a moment later and, finding the rows free, completes cleanly. The cycle never hardened, and the database never showed a partial write.
How it works¶
- Detect the imminent conflict. At the moment a hold-and-request would close a cycle, the system decides whether to make one holder yield rather than let both block.
- Choose the victim by a stable rule. A tie-break — oldest wins, lowest priority yields, least work done is cheapest to redo — picks which holder is preempted, chosen so the same transaction is not endlessly victimized (which would be livelock).
- Reclaim and roll back. The victim's resource is released and the victim is wound back to its last coherent checkpoint, undoing any partial changes so the reclaimed resource and the victim are both left valid.
- Re-run the loser. The preempted participant restarts later, ideally after the winner has finished, so it does not immediately re-collide.
Tuning parameters¶
- Victim-selection rule — oldest, lowest-priority, or least-progress. Preempting the least-progressed transaction wastes the least work; preempting the youngest (wound-wait) guarantees no starvation of old transactions.
- Checkpoint granularity — how often coherent rollback points are captured. Frequent checkpoints make rollback cheap but cost overhead; sparse ones make each preemption expensive.
- Preemption threshold — how close to a cycle the system must be before it reclaims. Eager preemption avoids blocking but aborts transactions that might have resolved on their own.
- Restart discipline — immediate retry versus backoff before re-running the victim, to avoid it colliding again the instant it restarts.
When it helps, and when it misleads¶
Its strength is that it preserves liveness without a global acquisition order or a demand that all needs be known up front: participants acquire resources freely and opportunistically, and the system unwinds any conflict that arises — invaluable when a total lock order is impractical or resource needs are discovered mid-task. Because rollback restores coherence, it breaks cycles without corrupting anyone.
Its failure mode is cost and, in careless designs, starvation or livelock: rolling back a nearly-complete transaction throws away real work, and a naive victim rule can preempt the same participant over and over so it never finishes — the classic misuse is preempting where rollback is not actually clean, reclaiming a resource whose partial effects (a sent message, an external side effect, a human commitment already relied upon) cannot be undone, so the "recovery" leaves damage behind. The guarding discipline is to preempt only where a genuine, tested rollback path exists, to choose victims by a rule that guarantees eventual progress for every participant, and to never apply it to irreversible commitments where taking something back cannot be made whole.
How it implements the components¶
preemption_or_release_rule— it defines exactly when and from whom a held resource may be forcibly reclaimed, and by what victim-selection rule.rollback_and_recovery_path— every preemption is paired with a wind-back to a coherent checkpoint, so reclaiming a resource never leaves the victim or the resource in a broken state.
It does not require a participant to grab its whole resource bundle up front (hold_and_wait_limit) — that is All-or-Nothing Acquisition; nor does it merely try, fail, and voluntarily back off (contention_monitoring_signal) — that is Try-Lock and Backoff. Preemption is *involuntary reclamation with repair, not a self-imposed acquisition limit or a voluntary retreat.*
Related¶
- Instantiates: Deadlock Prevention — it removes the no-preemption precondition, letting the system break a forming cycle by reclaiming a resource.
- Consumes: Lease-Based Resource Hold — a lease's expiry-recovery path is a close cousin of the checkpoint machinery preemption relies on.
- Sibling mechanisms: All-or-Nothing Acquisition · Try-Lock and Backoff · Agenda Ordering Rule · Lock Ordering Protocol · Safe-State Admission Check
Editorial Notes¶
Form Classification¶
Form family: Control, Automation & Runtime
Rationale: Preemption with Rollback operates as a live operational control that automatically routes, enforces, adapts, or responds during execution because it allows a resource or commitment to be taken back before a cycle hardens, while rollback restores a coherent prior state.
Independent corroboration: The frozen evidence defines Preemption with Rollback as 'Allows a resource or commitment to be taken back before a cycle hardens, while rollback restores a coherent prior state', so its operative form is Control, Automation & Runtime.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Cross-disciplinary synthesis
Present-day reach: Specialized
Rationale: Preemption, resource reclamation, and rollback to coherent state are canonical operating-systems and transaction mechanisms for deadlock avoidance.
Related originating lineages:
- Operations Research — Resource-allocation and deadlock theory materially formalize cycles, recovery costs, and victim choice.
Review resolution: Both blind reviewers agree that computer science is the primary origin. Reconciliation resolves alternate origin disagreement, origin mode disagreement. Formative alternate lineages are retained as operations_research; later breadth of use is recorded separately as domain_reach=specialized, while origin_mode=cross_disciplinary_synthesis describes the relationship among origin lineages.
Review outcome: Reconciled after independent review; high confidence.
References¶
[1] Rosenkrantz, D. J., Stearns, R. E., & Lewis, P. M. II. "System Level Concurrency Control for Distributed Database Systems". ACM Transactions on Database Systems 3(2), 178–198 (1978). Supports the wound-wait rule that an older requester preempts and rolls back a younger transaction holding the requested item. registry ↩