Deadlock, Starvation & Fairness

Pillar: deadlock-starvation-fairness | Date: May 2026
Scope: Failure modes in multi-agent locking systems: deadlock formation (mutual wait cycles across lock dependencies), deadlock prevention strategies (lock ordering, conservative locking, wound-wait/wait-die), wait-for graph cycle detection, timeout-and-backoff as a practical alternative, starvation scenarios (low-priority agents never acquiring high-contention locks), priority inversion, and fairness policies (FIFO queues, aging, work-conserving schedulers).
Sources: 32 gathered, consolidated, synthesized.

Table of Contents

1. Deadlock Fundamentals: Coffman Conditions & Taxonomy
2. Deadlock Prevention Strategies
3. Wait-For Graph: Structure, Detection & Limitations
4. Distributed Deadlock Detection: Chandy-Misra-Haas
5. Timeouts, Backoff & Jitter: Practical Deadlock Handling
6. Deadlock Recovery
7. Starvation: Causes, Definitions & Prevention
8. Priority Inversion: The Mars Pathfinder Failure Mode
9. Fairness Policies: Fair Queuing & Work-Conserving Schedulers
10. Queue-Based Mutual Exclusion: MCS & CLH Locks
11. Progress Guarantee Spectrum: Lock-Free & Wait-Free
12. Distributed Lock Systems in Practice

Section 1: Deadlock Fundamentals: Coffman Conditions & Taxonomy

A deadlock occurs when "no member of some group of entities can proceed because each waits for another member, including itself, to take action, such as sending a message or, more commonly, releasing a lock."^[26] In database contexts, the definition sharpens to a cycle in the wait-for graph where vertices denote transactions and edges denote waits for data items.^[1][12] Deadlock is distinct from starvation: starvation is a liveness failure where one process is perpetually denied resources while others make progress; deadlock is a mutual blocking cycle where no process in the cycle can proceed.^[5][15]

The Four Coffman Conditions

All four conditions must be present simultaneously for deadlock to occur. Breaking any single one prevents deadlock entirely.^[3][9][26]

Key finding: Deadlock prevention requires breaking exactly one Coffman condition. Resource ordering eliminates circular wait with zero runtime overhead; conservative locking eliminates hold-and-wait but requires knowing all lock needs upfront. Detection-and-recovery is preferred in practice precisely because it sacrifices none of the first three conditions, achieving higher resource utilization at the cost of occasional rollback.^[9][17]

^‡ The four necessary conditions were originally formalized in Coffman, Elphick, and Shoshani (1971), “System Deadlocks,” ACM Computing Surveys 3(2):67–78. That primary paper was not included in the corpus surveyed; the conditions as presented here are drawn from UIC Course Notes^[9] and Wikipedia Deadlock^[26], both of which attribute them to Coffman et al. Readers requiring direct verification should consult the original ACM Computing Surveys article.

Deadlock vs. Starvation: Liveness Hierarchy

Starvation-freedom is a strictly stronger liveness guarantee than deadlock-freedom.^[15] A mutual exclusion algorithm can be deadlock-free but not starvation-free if it resolves contention by arbitrary choice. "Finite bypass" (starvation-freedom) requires every process be bypassed at most finitely many times before accessing the shared resource — this is one of the two fundamental requirements for any mutual exclusion algorithm, alongside safety (correctness).^[5][15] (See Section 7 for the full Deadlock vs. Starvation comparison table.)

Distributed Deadlock Taxonomy

Four distinct deadlock types arise specifically in distributed multi-agent systems:^[3][22]

Section 2: Deadlock Prevention Strategies

Resource Ordering

Resource ordering assigns a global total order to all lock types and requires every agent to acquire resources in strictly ascending order.^[9][26][30] The anti-deadlock proof is direct: if P1 holds Rᵢ and waits for Rⱼ, and P2 holds Rⱼ and waits for Rᵢ, the ordering requires both i < j AND j < i — a contradiction.^[9] Resources with natural identifiers can use those IDs as the ordering key; otherwise hash codes suffice.^[30] This approach has zero runtime overhead — the problem is resolved at design time — but restricts programming flexibility and may force an agent to acquire resources it does not yet need.^[9]

Conservative Two-Phase Locking (C2PL)

C2PL, also called Predeclaration Locking or Static-2PL, requires a transaction to acquire all necessary locks at the beginning of execution. If any required lock is unavailable, the transaction does not proceed at all.^[17][27] This directly breaks the Hold-and-Wait Coffman condition: a transaction either holds all its locks or none.^[17] The protocol was formalized in a 1985 ACM TODS paper, "Locking performance in centralized databases."^[17]

2PL Protocol Variants

C2PL's critical weakness: conditional logic forces worst-case lock acquisition. Branches that may not execute must pre-acquire locks "just in case," suppressing concurrency. The author notes this is "probably why it hasn't seen much use in the last twenty years."^[27] Most production database systems instead use 2PL with deadlock detection via wait-for graph cycle detection.^[17]

Timestamp-Based Protocols: Wound-Wait and Wait-Die

Both protocols assign timestamps at transaction start and use timestamp comparisons to guarantee unidirectional wait chains — making cycles structurally impossible.^[1][12][27]

Both protocols preserve starvation-freedom by maintaining original timestamps through rollback. A restarted transaction retains its original timestamp and will eventually become the oldest transaction in the system, guaranteeing eventual resource acquisition.^[1][12] The key cost: both may produce unnecessary rollbacks — transactions abort even when no actual deadlock would have formed.^[1][12]

Deadlock Avoidance: Banker's Algorithm

Before granting any resource request, the Banker's Algorithm checks whether the resulting state is "safe" — i.e., whether a sequence of all processes exists such that each process's remaining resource needs can be met from current available resources plus resources released by preceding processes.^[9][30]

Time complexity is O(n²m) where n = number of processes and m = resource types.^[9] This overhead rules it out for most real-time or high-throughput systems.

Prevention Strategy Comparison

^† C2PL forces worst-case lock pre-acquisition for all conditional code paths, suppressing concurrency. UIC Course Notes estimate ~20–30% utilization reduction from worst-case pre-acquisition^[9]; no peer-reviewed empirical benchmark was found in the sources surveyed. "Probably why it hasn't seen much use in the last twenty years" per the 1985 ACM TODS formalization.^[17][27]

Section 3: Wait-For Graph: Structure, Detection & Limitations

A wait-for graph (WFG) is "a directed graph used for deadlock detection in operating systems and relational database systems."^[13][21] It simplifies a Resource Allocation Graph (RAG) by collapsing resource nodes: for each request edge from process Pᵢ to resource R and assignment edge from R to process Pⱼ, a direct edge from Pᵢ to Pⱼ replaces both. This collapses per-resource detail while preserving all deadlock information.^[2][13]

Detection Rules by Waiting Model

A knot in the WFG is a set of nodes K where every node in K has at least one outgoing edge and from every node in K, all reachable nodes are also in K.^[21] The basic WFG scheme "is not applicable to a resource allocation system with multiple instances of each resource type."^[13][21]

Key finding: "A deadlock occurs in a schedule if and only if there is at least one cycle in the wait-for graph."^[13][21][2] This is the central theorem underlying all WFG-based detection — the biconditional is exact for single-instance resources under the AND model.

Cycle Detection Complexity

DFS-based cycle detection runs in O(V + E) time where V = vertices (processes) and E = edges (wait relations).^[2] A more general bound of O(n²) operations for n vertices applies to cycle-finding without the DFS structural assumption.^[13] Recommended practice: invoke detection at regular intervals rather than after each resource request, balancing detection latency against computational overhead.^[2]

Real-World WFG Applications

WFG Limitations

Section 4: Distributed Deadlock Detection: Chandy-Misra-Haas

In distributed systems, each site maintains a local wait-for graph for all processes that hold or request local resources. Global deadlock detection requires combining local graphs into a global WFG and running cycle detection on it.^{[2][13][19][20]} Due to message delays and partial visibility, the coordinator's global WFG may not exactly reflect reality — phantom deadlocks (false positives) can be incorrectly reported.^[19][20]

Detection Architecture Options

Chandy-Misra-Haas (CMH) Algorithm

Published in 1983 by K. Mani Chandy, Jayadev Misra, and Laura M. Haas, CMH is considered one of the best deadlock detection algorithms for distributed systems.^[28] It operates in two variants corresponding to the AND and OR waiting models.

AND Model: Edge-Chasing (Probe-Based)

A special message — a probe triplet (i, j, k) — circulates along WFG edges. The probe (i, j, k) means: process Pᵢ initiated detection; message sent by the home site of Pⱼ to the home site of Pₖ. Blocked processes forward the probe along outgoing edges. Process Pᵢ declares deadlock when probes it initiated return to itself.^[28]

OR Model: Diffusion Computation

Uses query(i, j, k) and reply(i, j, k) messages. A blocked process initiates detection by sending queries to all processes in its dependent set.^[28]

CMH Performance Characteristics

Key finding: CMH's probe-based design detects all true deadlocks and reports zero false deadlocks — eliminating phantom deadlocks that plague centralized approaches — while requiring no site to maintain global WFG state and transmitting only constant-size messages.^[28]

Hybrid Approaches

Sites may be grouped into clusters: local coordinators merge sub-group WFGs before escalating to a higher tier.^[13] One algorithm detects and resolves all O(n−1) cycles in a worst-case n-vertex WFG by transmitting O(n³) messages of constant size.^[2][19]

Section 5: Timeouts, Backoff & Jitter: Practical Deadlock Handling

"Most distributed systems do not implement accurate deadlock detection and instead rely on timeouts, retries, and recovery."^[3][22][4] A communication deadlock forms because something is willing to wait forever — the remedy is strict timeouts on every outbound request.^[4]

Timeouts as Deadlock Prevention

Timeouts break the Hold-and-Wait Coffman condition: if an agent cannot acquire a resource within the timeout window, it releases what it holds and backs off.^[4] Without timeouts, a synchronous service call chain can lock up indefinitely.^[4]

Timeout Configuration Guidelines

A Dead Man's Switch (watchdog timer) monitors task progress — if a task makes no progress within a specified window, assume deadlock and terminate or restart.^[22]

Exponential Backoff

Exponential backoff increases wait time between retry attempts geometrically. The standard formula:^[4]

wait = min(cap, base × 2^attempt)

Critical failure mode — cascading amplification: In multi-layer systems, independent retries at each layer multiply load exponentially. A 5-deep call stack with 3 retries per layer produces 3⁵ = 243× load on the backend, making recovery impossible and triggering cascading failure.^{[4][14][22][29]}

Backoff Mitigation Strategies

Jitter: Preventing Retry Storms

Jitter adds randomness to backoff timing. Without it: "All the failed calls back off to the same time, they cause contention or overload again when retried."^[4] Amazon observed that with 100 contending clients, jitter reduces the call count by more than half.^[29]

Key finding: AWS recommends Equal Jitter for throttling scenarios.^[29] For scheduled work, deterministic (per-host) jitter enables pattern-based troubleshooting that randomized approaches cannot provide.^[4]

TTL-Based Lock Expiry and Architectural Best Practices

Always set a TTL on every distributed lock to prevent permanent deadlocks from holder crashes. "No lock should live longer than the business operation."^[3][10]

Section 6: Deadlock Recovery

When deadlock is detected, recovery requires selecting a victim from the deadlocked cycle and breaking it. Three strategies exist:^[3][20]

Recovery Approaches

Emerging Approaches

Machine learning models for anomaly detection in cloud thread scheduling represent an emerging direction. UIC Course Notes report resolution automated “40% faster than traditional Banker's algorithm”^[9]; no peer-reviewed primary paper was found in the sources surveyed to support this figure, so it should be treated as a directional estimate from course notes rather than an established benchmark.

Section 7: Starvation: Causes, Definitions & Prevention

Resource starvation occurs when "a process is perpetually denied necessary resources to process its work."^[15] In priority scheduling, a low-priority process keeps waiting indefinitely because higher-priority processes continuously receive the CPU.^[5][23]

Starvation vs. Deadlock

Root Causes

Aging

Aging is a scheduling technique that gradually increases the priority of processes waiting too long.^[5][23] Concrete example: in a system where priority ranges from 127 (lowest) to 0 (highest), a waiting process advances one priority level every 15 minutes — eventually becoming high-priority regardless of origin.^[5] After execution, the process returns to its original priority.^[5]

Bounded Deferment

Bounded deferment ensures a low-priority item is delayed by at most a fixed number of pops (the maxDeferment bound). A starvation-free priority queue balances priority and arrival time:^[5][23]

1. A FIFO Queue holds all pending items in arrival order
2. When the priority frontier is empty, up to maxDeferment + 1 items are pulled from the FIFO Queue
3. Those items are sorted by priority and moved to the priority frontier for removal

This achieves bounded delays for low-priority tasks with deterministic guarantees, unlike aging which converges asymptotically.^[23]

Prevention Strategy Summary

Key finding: FIFO intake reduces perceived unfairness and prevents starvation via arrival-order guarantees — fairness-first scheduling need not sacrifice performance (see Section 9 MQFQ benchmarks for concrete throughput figures).^[25] Eliminating starvation typically requires adding fairness (aging, queuing) or deterministic bounds at the potential cost of increased average latency or reduced responsiveness for priority-sensitive tasks.^[5]

Section 8: Priority Inversion: The Mars Pathfinder Failure Mode

Priority inversion is "a scenario in scheduling in which a high-priority task is indirectly superseded by a lower-priority task, effectively inverting the assigned priorities."^[6][16] The mechanism requires exactly three priority levels and a shared resource.

The Classic Three-Task Scenario

1. Low-priority task L acquires a shared resource^[6]
2. High-priority task H requests that resource — must wait for L^[6]
3. Medium-priority task M — which does not need the resource — preempts L (since M > L)^[16]
4. H is blocked by M, even though H > M — H is effectively blocked by the lowest-priority task in the system^[16]

This creates unbounded priority inversion: H's block duration is bounded only by M's total execution time, not L's critical section time.^[16]

The Mars Pathfinder Incident (1997)

The definitive real-world case study in priority inversion occurred on the Mars Pathfinder lander, running VxWorks RTOS.^[16][24]

Failure sequence: The communications task (medium priority) preempted the meteorological task (low priority) while ASI/MET held the bus mutex. The bus management task (high priority) was blocked waiting for the mutex. The watchdog timer detected that the bus management task had not run within its deadline and triggered a total system reset.^[16][24] JPL engineers reproduced the reset on an exact spacecraft replica using VxWorks full-trace mode.^[24]

Root cause: The mutex had priority inheritance disabled for performance reasons.^[16][24] Fix: A software update from Earth enabled priority inheritance on the mutex.^[24]

Solutions and Protocols

Priority Inheritance Protocol (PIP)

When H blocks waiting for a resource held by L, L's priority is temporarily raised to H's priority. L executes its critical section at H's elevated priority — M cannot preempt L. When L exits, it regains its original priority. This bounds inversion to the length of L's critical section.^[6][16][24] This was the Pathfinder fix. POSIX: PTHREAD_PRIO_INHERIT.^[6]

Priority Ceiling Protocol (PCP)

Assigns each shared resource a "priority ceiling" equal to the maximum priority of any task that will ever access it. When a task acquires a resource, its priority is raised to that ceiling — preventing any medium-priority task from running while a low-priority task holds the resource. PCP completely prevents priority inversion and also prevents deadlock with nested locks.^[6][16][24] POSIX: PTHREAD_PRIO_PROTECT.^[6]

PIP vs. PCP Comparison

Additional Solutions

Seminal research: Sha, Rajkumar, and Lehoczky, “Priority Inheritance Protocols: An Approach to Real-Time Synchronization,” IEEE Transactions on Computers, Vol. 39, No. 9 (1990) — introduced both PIP and PCP.^[6][24] Note: this primary paper was not in the corpus surveyed; it is credited here via Wikipedia’s Priority Inversion article (src-6, src-24), which cites it as the origin of both protocols. Readers requiring direct verification should consult the original IEEE paper.

Key finding: The Mars Pathfinder incident (1997) demonstrates that disabling priority inheritance for performance on a single mutex — a seemingly minor configuration choice — can cascade into total system failure through an unbounded priority inversion chain. The fix required only enabling a flag; the cost was a spacecraft in near-failure on another planet.^[16][24]

Section 9: Fairness Policies: Fair Queuing & Work-Conserving Schedulers

Fair queuing is "a family of scheduling algorithms used in some process and network schedulers" designed to "achieve fairness when a limited resource is shared."^[8][18] With link data-rate R and N active flows, each receives at least R/N.^[8]

Historical Development

Formal Fairness Notions

Work-Conserving Property

A work-conserving scheduler never leaves resources idle when pending work exists.^[8][25] Example with three servers sharing a 6 Mbps link:^[8]

FIFO, priority queuing, and fair queuing are all work-conserving. Non-work-conserving schedulers (traffic shapers) artificially delay work to enforce bandwidth caps, sacrificing utilization for isolation.^[8][25] Time-slice schedulers are generally not work-conserving.^[25]

Fair Queuing Variants

Multi-Queue Fair Queuing (MQFQ)

MQFQ, published at USENIX ATC 2019, is the first fair, work-conserving scheduler suitable for multi-queue systems (NVMe/NVMf storage with multiple hardware queues).^[25]

MQFQ Key Innovations

Performance: With 15–19 active threads, MQFQ reaches more than 3M IOP/s — 2.6× better than MQFQ-serial, 20× better than Linux BFQ — constituting 71% of peak throughput.^[25]

Preemptive MQFQ (P-MQFQ) addresses "deceptive idleness": parallel threads that frequently block due to lock synchronization appear idle to the scheduler but are actively waiting. Standard schedulers unfairly penalize these threads by reducing their future allocation. P-MQFQ uses a centralized queue to fairly dispatch threads based on received CPU bandwidth from multiple cores.^[25]

Key finding: Queue-based resource allocation locks (the MQFQ paper's implementation) achieve FIFO ordering of lock acquisitions, lock-free deadlock freedom, and starvation-freedom for all enqueued requests. As contention increases, the multi-resource lock implementation obtains an average 10× speedup over alternatives including GNU C++'s lock method and Boost's lock function.^[25]

Section 10: Queue-Based Mutual Exclusion: MCS & CLH Locks

Queue-based locks (MCS, CLH) provide local spinning and FIFO ordering, making them more scalable than test-and-set spinlocks. The key insight: at most one thread busy-waits on a given location at any one time, increasing ownership transfer rate relative to global-spinning techniques.^[31]

MCS Lock (Mellor-Crummey and Scott)

MCS locks provide strict FIFO order with local spinning.^[31][15]

• Each thread spins on its own queue node (not a shared memory location)^[31]
• Lock body requires just a pointer to the tail — compact^[31]
• Used in the Linux kernel for the low-level "qspinlock" construct^[31]
• Readily allows editing and re-ordering the queue of waiting threads^[31]
• Modern extensions make MCS NUMA-Aware by editing queue order to prioritize co-located threads^[31]
• Requires the queue element address from the owner to be passed to the unlock operator^[31]

CLH Lock (Craig, Landin, and Hagersten)

CLH links the queue from tail to head (opposite of MCS).^[31]

• Requires only a single atomic exchange operation in Acquire — no atomic read-modify-write in Release^[31]
• Requires only O(1) network transactions per lock acquisition on both coherent and non-coherent cache machines^[31]
• Waiting elements migrate between threads — potentially problematic in NUMA environments where migrated nodes become remote^[31]

MCS vs. CLH Comparison

CLH has better overall performance on cache-coherent machines; MCS is expected to win on non-cache-coherent machines.^[31]

Timeout Interactions with Queue-Based Locks

Queue-based locks create a fundamental tension with timeouts: "While threads competing for a test-and-set lock are mutually anonymous and can abandon their spins without anyone being the wiser, threads in a queue-based lock are linked into an explicit data structure. A timed-out thread must somehow introduce its neighbors in the queue to one another."^[31]

Mercury Computer Systems' MCS variant with timeout abandons fairness: threads willing to wait indefinitely bypass threads with bounded wait times.^[31] The Hemlock variant provides FIFO admission and is compact, requiring just one word per extant lock plus one word per thread regardless of the number of locks held.^[31]

Correctness Requirements

Any queue-based lock must guarantee:^[31]

• Safety (mutual exclusion): At most one thread holds the lock at any time
• Liveness (bounded waiting / starvation-freedom): Every waiting thread eventually acquires the lock

Both MCS and CLH guarantee starvation-freedom via FIFO queue ordering.^[31]

Section 11: Progress Guarantee Spectrum: Lock-Free & Wait-Free

Three principal levels of progress guarantee exist in concurrent algorithm design, from weakest to strongest:^[7][26]

Deadlock-freedom is classified as a blocking progress condition — it admits implementations where delay of a single thread can prevent all other threads from making progress. It guarantees minimal progress, in contrast to maximal progress conditions such as wait-freedom and starvation-freedom.^[26]

Lock-Free Systems

"While any particular computation may be blocked for some period of time, all CPUs are able to continue performing other computations."^[7] System-wide progress is always guaranteed. Lock-free eliminates: deadlocks, priority inversion, convoying, and serial bottlenecks.^[7]

Implementation: Based on hardware atomic primitives (Compare-And-Swap). RethinkDB uses coroutines to implement lock-free concurrency at the language level, with all blocking happening in user space.^[7] On an N-core machine, approximately 4N concurrent transactions keeps all cores productive.^[7]

Critical caveat: Lock-free does not mean starvation-free. Individual threads may be continuously preempted by others and never complete. To achieve starvation-freedom, wait-free algorithms are required.^[7][26]

Wait-Free Systems

"No computation can ever be blocked by another computation." Every thread completes in a bounded number of steps regardless of other threads' actions.^[7] Required when: few concurrent operations relative to available processors, hard real-time demands requiring guaranteed non-probabilistic completion, or safety-critical control systems (e.g., nuclear reactor control).^[7]

Lock-Free Mechanism Catalog

Composition limitation: Lock-free data structures are harder to compose — no transactions across multiple structures without additional mechanism. CAS-based retry loops also increase CPU waste under very high contention.^[7]

Key finding: Lock-free is the strongest form of deadlock prevention, but not all problems are amenable to lock-free solutions. The progression from lock-based → lock-free → wait-free trades implementation complexity for ever-stronger liveness guarantees — choose the minimum strength that satisfies the problem's latency and safety requirements.^[7][26]

Section 12: Distributed Lock Systems in Practice

A correct distributed lock must guarantee three minimum properties:^[10][32]

1. Safety (Mutual Exclusion): At any given moment, only one client can hold a lock
2. Liveness A — Deadlock Free: It is always eventually possible to acquire a lock, even if the holding client crashes or gets partitioned
3. Liveness B — Fault Tolerance: As long as the majority of nodes are up, clients can acquire and release locks

Fairness is an optional but desirable property — granting access in FIFO order to ensure predictable behavior and prevent starvation.^[10][32]

Redis-Based Distributed Locks

Redis stores a lock key with a TTL. If the key doesn't exist, a client creates it and claims the lock; on task completion, the key is removed. If the process crashes, Redis removes the key after TTL expiration.^[10][32]

Clock skew risk: Redis does not use a monotonic clock for TTL expiration. A wall-clock shift may result in a lock being acquired by more than one process simultaneously.^[10][32]

Fairness limitation: Basic Redis locks don't guarantee fairness — "a client may wait a long time to get the lock while another client gets it immediately."^[32] Read-Write locks can starve writers if there is a constant stream of readers and fairness policies aren't enforced.^[10][32]

Production clients such as Redisson implement fair lock variants that approximate FIFO ordering over basic Redis primitives, partially mitigating the default fairness limitation.^[32]

Redlock Algorithm and Kleppmann's Critique

Redlock uses 5 independent Redis master nodes: a client requests the lock from each sequentially; if acquired from a majority within a bounded time window, the client holds the lock.^[10][32]

Martin Kleppmann's critique^[11][32] identifies three failure modes:

Redlock generates no fencing tokens, leaving systems vulnerable to paused-process race conditions. "Given its widely accepted vulnerability to timing-based failures and its lack of a native fencing mechanism, Redlock should not be considered a safe algorithm for applications that require strong mutual exclusion guarantees."^[10]

ZooKeeper-Based Distributed Locks

ZooKeeper clients create sequential ephemeral znodes. The client holding the lowest-numbered znode holds the lock. Each client watches only its immediate predecessor node (not all nodes — avoiding herd effect).^[10]

• Deadlock prevention: If a client dies or loses connection, ZooKeeper automatically deletes the ephemeral node — locks are never left hanging indefinitely^[10]
• Fairness via sequential znodes: Creates a fair, FIFO queue for lock acquisition — starvation is impossible^[10]
• Herd effect avoidance: Predecessor-watching delivers notifications in sequence, ensuring smooth lock handovers without unnecessary network traffic^[10]

Fencing Tokens

A fencing token is a unique, always-increasing number issued when a client acquires a distributed lock. Storage systems reject writes with lower or expired tokens, preventing a paused process from corrupting data after its lock expires.^[11][32]

Phantom lock holder problem: In distributed systems, there is no reliable way to distinguish a slow process from a dead one. A process can be "alive" but paused (GC, network partition, swap). During the pause, its lock may have expired while it still believes it holds the lock. Systems must be designed to be safe in either case.^[11]

Any production distributed lock must:^[11]

1. Generate strictly monotonic fencing tokens
2. Enforce token checking on all resource accesses
3. Make no assumptions about bounded network delays or process execution times
4. Separate safety properties from liveness properties

Multi-Lock Deadlock Risk

When acquiring multiple distributed locks simultaneously, classic circular wait applies: Process A holds Lock1 and wants Lock2; Process B holds Lock2 and wants Lock1.^[10][32] Mitigation:^[10]

• Lock ordering: always acquire locks in consistent global order
• Avoid nested distributed locks
• Use distributed lock only for the smallest possible critical section
• Deterministic multi-key lock ordering to prevent circular waiting state

Distributed Lock System Comparison

Key finding: Kleppmann's recommendation for correctness-critical locking: use ZooKeeper (with Apache Curator recipes), PostgreSQL with transaction guarantees, etcd, or any system based on Raft, Viewstamped Replication, Zab, or Paxos — not Redis or Redlock, which make timing assumptions that production systems violate routinely.^[11]

Kleppmann draws a critical distinction between two use cases for distributed locks:^[11]

• Efficiency locks: Prevent redundant work; a single Redis instance is simpler and sufficient
• Correctness locks: Prevent concurrent data corruption; require a proper consensus system, not Redlock

Home