Deadlock Detection Database: Storage and Query Deep Dive

Introduction and Core Concepts

A deadlock detection database is a specialized subsystem within a database management system (DBMS) responsible for identifying and resolving circular wait conditions among concurrent transactions. In any system where multiple transactions compete for shared resources such as rows, pages, tables, or locks, a deadlock occurs when each transaction in a set waits for a resource held by another transaction in the same set, creating an indefinite block. Unlike deadlock prevention, which imposes strict ordering to avoid deadlocks entirely, a deadlock detection database takes an optimistic approach: it allows deadlocks to occur, efficiently stores the wait relationships, and periodically queries this structure to find cycles.

At its core, the deadlock detection database maintains a Wait-For Graph (WFG), a directed graph where vertices represent active transactions and an edge T1 -> T2 indicates that transaction T1 is waiting for a resource currently held by transaction T2. A deadlock exists if and only if this graph contains a directed cycle. The storage layer is responsible for persisting these edges durably and consistently under high concurrency, while the query layer executes graph traversal algorithms to detect cycles with minimal latency. The effectiveness of this design directly impacts database throughput, tail latency, and availability.

Why does this matter? Modern OLTP systems handle thousands of concurrent transactions per second, and blocking is unavoidable when enforcing isolation levels like Serializable or Repeatable Read. Without efficient detection, deadlocked transactions would hold locks forever, starving other transactions and eventually requiring manual intervention or timeout-based aborts that are both slow and imprecise. A well-engineered deadlock detection database provides fast, accurate detection with low overhead, enabling automatic victim selection and rollback to break the cycle while preserving overall system progress. This is critical for financial systems, e-commerce platforms, and distributed databases where correctness and liveness must coexist.

Key Terminology

• Wait-For Graph (WFG): The central data structure for deadlock detection database storage. Nodes are transactions, edges are wait dependencies.
• Resource Allocation Graph (RAG): A bipartite graph with transaction and resource nodes. The WFG is derived by collapsing resource nodes.
• Victim Selection: The policy for choosing which transaction to abort when a cycle is found, often based on cost, priority, or age.
• Detection Frequency: The interval or trigger for running cycle detection, balancing CPU overhead against deadlock resolution time.

Storage vs. Query Responsibilities

The storage component must support highly concurrent edge insertions and deletions as transactions acquire, wait for, and release locks. It must be lock-free or fine-grained to avoid becoming a bottleneck itself. The query component must answer the question does a cycle exist? and if so, where? efficiently. In centralized databases, this is an in-memory graph traversal. In distributed deadlock detection databases, storage is partitioned across nodes and queries require coordinated graph collection or probe-based algorithms like edge-chasing.

How It Works

The mechanism of a deadlock detection database can be broken into three continuous phases: capture, maintenance, and detection. During capture, the lock manager intercepts every lock request. If a transaction T1 requests a lock on resource R that is incompatible with a lock held by T2, the system does not immediately block T1 indefinitely. Instead, it records a wait edge T1 -> T2 in the deadlock detection database and suspends T1. This edge is annotated with metadata such as resource identifier, lock mode, timestamp, and transaction priority.

During maintenance, the graph is kept consistent as the system evolves. When T2 releases its lock on R, the edge T1 -> T2 is removed, and T1 is granted the lock and resumed. If T1 was waiting for multiple resources, it may have multiple outgoing edges. Similarly, when a transaction commits or aborts, all its incident edges are purged. The challenge is to make these updates atomic and visible to the detector without introducing latches that serialize lock operations. Most systems use an in-memory adjacency list protected by per-transaction latches or lock-free concurrent hash maps.

During detection, the system runs a cycle detection algorithm over the current snapshot of the WFG. The classic approach is depth-first search (DFS) with coloring: white for unvisited, gray for visiting, black for visited. If DFS encounters a gray node, a cycle is found. Because the graph is typically sparse and small relative to the number of transactions, DFS is highly efficient. Detection can be triggered periodically by a background daemon every 100ms to 1s, or incrementally on every edge insertion for low-latency resolution. Upon detecting a cycle, the detector extracts the involved transactions and invokes the victim selector.

Centralized vs. Distributed Detection

In a single-node database like PostgreSQL or MySQL InnoDB, the entire WFG resides in shared memory, making detection straightforward. In a distributed deadlock detection database spanning multiple shards or microservices, no single node has the full graph. Two primary strategies exist: centralized collection where each node periodically ships its local WFG to a coordinator for global analysis, and decentralized edge-chasing where probe messages follow wait edges across nodes to detect cycles without global collection. Edge-chasing reduces data movement but increases message complexity.

Query Semantics

The query layer exposes two logical operations: EXISTS-CYCLE and FIND-CYCLE. EXISTS-CYCLE is a boolean check optimized for the common case where no deadlock exists. FIND-CYCLE returns the actual cycle members for resolution. Advanced systems also support path queries such as find all transactions transitively waiting for T1, which is useful for deadlock prevention heuristics and lock escalation analysis.

Implementation

Implementing a deadlock detection database requires careful choice of storage structures and concurrency control. Below are production-inspired Python prototypes that illustrate the core storage and query logic. Note that a real DBMS would implement this in C++ or Rust with shared memory, but the algorithmic principles are identical.

Core In-Memory Wait-For Graph with DFS Detection

This implementation uses an adjacency list for storage and an iterative DFS for cycle detection. It supports concurrent edge updates and provides victim selection based on transaction cost.

from collections import defaultdict, deque
import time

class DeadlockDetectionDatabase:
    def __init__(self):
        # Storage: adjacency list {waiting_txn: set(holding_txns)}
        self.wfg = defaultdict(set)
        # Reverse index for fast cleanup: {holding_txn: set(waiting_txns)}
        self.reverse_index = defaultdict(set)
        # Transaction metadata: {txn_id: {priority, timestamp, cost}}
        self.txn_meta = {}

    def register_transaction(self, txn_id, priority=0, cost=1):
        """Register a new transaction with metadata for victim selection."""
        self.txn_meta[txn_id] = {
            'priority': priority,
            'timestamp': time.time(),
            'cost': cost
        }
        # Ensure node exists even with no edges
        if txn_id not in self.wfg:
            self.wfg[txn_id] = set()

    def add_wait_edge(self, waiting_txn, holding_txn, resource_id):
        """Storage operation: record that waiting_txn waits for holding_txn."""
        if waiting_txn == holding_txn:
            return False
        # Avoid duplicate edges
        if holding_txn in self.wfg[waiting_txn]:
            return False
        self.wfg[waiting_txn].add(holding_txn)
        self.reverse_index[holding_txn].add(waiting_txn)
        # Incremental query: check for cycle immediately after insertion
        cycle = self.detect_cycle_incremental(waiting_txn)
        return cycle

    def remove_wait_edge(self, waiting_txn, holding_txn):
        """Storage operation: remove edge when lock is granted or released."""
        if holding_txn in self.wfg.get(waiting_txn, set()):
            self.wfg[waiting_txn].remove(holding_txn)
            self.reverse_index[holding_txn].discard(waiting_txn)

    def remove_transaction(self, txn_id):
        """Cleanup all edges when transaction commits or aborts."""
        # Remove outgoing edges
        if txn_id in self.wfg:
            for holding in list(self.wfg[txn_id]):
                self.reverse_index[holding].discard(txn_id)
            del self.wfg[txn_id]
        # Remove incoming edges
        if txn_id in self.reverse_index:
            for waiting in list(self.reverse_index[txn_id]):
                self.wfg[waiting].discard(txn_id)
            del self.reverse_index[txn_id]
        self.txn_meta.pop(txn_id, None)

    def detect_cycle_incremental(self, start_txn):
        """Query operation: DFS from start_txn to find cycle quickly."""
        visited = set()
        rec_stack = set()
        parent = {}

        def dfs(node):
            visited.add(node)
            rec_stack.add(node)
            for neighbor in self.wfg.get(node, []):
                if neighbor not in visited:
                    parent[neighbor] = node
                    result = dfs(neighbor)
                    if result:
                        return result
                elif neighbor in rec_stack:
                    # Cycle found, reconstruct path
                    cycle = [neighbor]
                    cur = node
                    while cur != neighbor:
                        cycle.append(cur)
                        cur = parent.get(cur)
                        if cur is None:
                            break
                    cycle.append(neighbor)
                    cycle.reverse()
                    return cycle
            rec_stack.remove(node)
            return None

        return dfs(start_txn)

    def select_victim(self, cycle):
        """Choose victim with lowest cost/priority to minimize rollback work."""
        if not cycle:
            return None
        # Prefer lowest cost, then youngest transaction
        victim = min(cycle, key=lambda t: (
            self.txn_meta.get(t, {}).get('cost', 999),
            -self.txn_meta.get(t, {}).get('priority', 0)
        ))
        return victim

Persistent Storage with Relational Tables

For durability and observability, many systems mirror the in-memory WFG to relational tables. This allows DBAs to query deadlocks with SQL and enables post-mortem analysis. The following example shows the schema and query pattern.

import sqlite3

# Persistent deadlock detection database schema
def init_persistent_store(conn):
    cur = conn.cursor()
    # Storage table for wait edges
    cur.execute("""
        CREATE TABLE IF NOT EXISTS wait_for_graph (
            waiting_txn_id INTEGER NOT NULL,
            holding_txn_id INTEGER NOT NULL,
            resource_id TEXT NOT NULL,
            lock_mode TEXT NOT NULL,
            wait_start_ms INTEGER NOT NULL,
            PRIMARY KEY (waiting_txn_id, holding_txn_id, resource_id)
        )
    """)
    # Index for fast query: find all waits for a given holder
    cur.execute("""
        CREATE INDEX IF NOT EXISTS idx_holder 
        ON wait_for_graph(holding_txn_id)
    """)
    # Transaction table for victim selection
    cur.execute("""
        CREATE TABLE IF NOT EXISTS transactions (
            txn_id INTEGER PRIMARY KEY,
            priority INTEGER,
            undo_log_size INTEGER
        )
    """)
    conn.commit()

def add_persistent_edge(conn, waiting, holding, resource, mode):
    cur = conn.cursor()
    cur.execute("""
        INSERT OR IGNORE INTO wait_for_graph
        VALUES (?, ?, ?, ?, strftime('%s','now')*1000)
    """, (waiting, holding, resource, mode))
    conn.commit()
    # Query to detect cycle using recursive CTE (for small graphs)
    cur.execute("""
        WITH RECURSIVE path(waiting, holding, depth, path_str) AS (
            SELECT waiting_txn_id, holding_txn_id, 1,
                   waiting_txn_id || '->' || holding_txn_id
            FROM wait_for_graph WHERE waiting_txn_id = ?
            UNION ALL
            SELECT w.waiting_txn_id, w.holding_txn_id, p.depth+1,
                   p.path_str || '->' || w.holding_txn_id
            FROM wait_for_graph w JOIN path p 
              ON w.waiting_txn_id = p.holding
            WHERE p.depth < 10 AND instr(p.path_str, w.holding_txn_id) = 0
        )
        SELECT path_str FROM path WHERE holding = ?
        LIMIT 1
    """, (waiting, waiting))
    return cur.fetchone()

# Example usage
# conn = sqlite3.connect(":memory:")
# init_persistent_store(conn)
# cycle = add_persistent_edge(conn, 1, 2, "row:42", "X")

Periodic Background Detector

In production, detection is often decoupled from edge insertion to reduce latency on the lock path. A background thread snapshots the graph and runs a full DFS.

import threading

class BackgroundDetector:
    def __init__(self, detection_db, interval_ms=500):
        self.db = detection_db
        self.interval = interval_ms / 1000.0
        self.running = False
        self.thread = None

    def full_graph_scan(self):
        """Query operation: detect any cycle in entire graph."""
        visited = set()
        rec_stack = set()

        def dfs(node, path):
            visited.add(node)
            rec_stack.add(node)
            path.append(node)
            for neighbor in self.db.wfg.get(node, []):
                if neighbor not in visited:
                    result = dfs(neighbor, path)
                    if result:
                        return result
                elif neighbor in rec_stack:
                    # Extract cycle from path
                    idx = path.index(neighbor)
                    return path[idx:] + [neighbor]
            rec_stack.remove(node)
            path.pop()
            return None

        for txn in list(self.db.wfg.keys()):
            if txn not in visited:
                cycle = dfs(txn, [])
                if cycle:
                    return cycle
        return None

    def start(self):
        self.running = True
        def loop():
            while self.running:
                cycle = self.full_graph_scan()
                if cycle:
                    victim = self.db.select_victim(cycle)
                    print(f"Deadlock detected: {cycle}, victim: {victim}")
                    # In real DB: abort victim, remove its edges
                time.sleep(self.interval)
        self.thread = threading.Thread(target=loop, daemon=True)
        self.thread.start()

    def stop(self):
        self.running = False

Distributed Edge-Chasing Probe

For distributed deadlock detection databases, probes traverse the WFG across nodes without central collection.

from dataclasses import dataclass

@dataclass
class Probe:
    initiator: int
    path: list  # List of txn_ids visited
    timestamp: float

class DistributedDetectorNode:
    def __init__(self, node_id):
        self.node_id = node_id
        self.local_wfg = defaultdict(set)  # Only edges where waiter is local
        self.probes_sent = 0

    def on_wait_edge(self, waiting_txn, holding_txn, holding_node):
        """Storage: add edge and potentially initiate probe."""
        self.local_wfg[waiting_txn].add((holding_txn, holding_node))
        # If waiting_txn already in a wait chain, start edge-chasing
        probe = Probe(initiator=waiting_txn, path=[waiting_txn], timestamp=time.time())
        self.forward_probe(probe, holding_txn, holding_node)

    def forward_probe(self, probe, next_txn, next_node):
        """Query: forward probe along wait edge."""
        # In real system, this would be an RPC to next_node
        if next_txn in probe.path:
            # Cycle detected: probe returned to initiator
            print(f"Distributed deadlock: {probe.path + [next_txn]}")
            return True
        # Avoid infinite probe length
        if len(probe.path) > 10:
            return False
        probe.path.append(next_txn)
        # Simulate forwarding to next node's local edges
        # next_node.receive_probe(probe)
        self.probes_sent += 1
        return False

    def receive_probe(self, probe):
        """Handle incoming probe from another node."""
        last_txn = probe.path[-1]
        for (holder, holder_node) in self.local_wfg.get(last_txn, []):
            self.forward_probe(Probe(probe.initiator, list(probe.path), probe.timestamp),
                               holder, holder_node)

Step-by-Step Example

Consider three transactions in an e-commerce deadlock detection database handling inventory and orders. T1 wants to update inventory for product A and then create an order, T2 wants to create an order and then update inventory for product B, and T3 wants to update both inventories. Assume row-level exclusive locks.

Initially, the WFG is empty. At time t1, T1 acquires an exclusive lock on row A. At t2, T2 acquires an exclusive lock on row B. At t3, T3 acquires an exclusive lock on row C. No waits exist yet. At t4, T1 requests a lock on row B, which is held by T2. The lock manager denies the request, inserts edge T1 -> T2 into the deadlock detection database, and suspends T1. The graph is now {T1: {T2}}.

At t5, T2 requests a lock on row C held by T3. Edge T2 -> T3 is added. Graph becomes {T1: {T2}, T2: {T3}}. No cycle yet, as the graph is a linear chain. At t6, T3 requests a lock on row A held by T1. Edge T3 -> T1 is added. The graph is now {T1: {T2}, T2: {T3}, T3: {T1}}. This forms a cycle T1 -> T2 -> T3 -> T1.

Detection Walkthrough

Assume incremental detection is enabled. When edge T3 -> T1 is inserted, the detector runs DFS starting from T3. It visits T3 -> T1 -> T2 -> T3. When it tries to visit T3 again, it finds T3 is in the recursion stack gray set, confirming a cycle. The detector reconstructs the cycle by walking parent pointers: T3 -> T1 -> T2 -> T3.

Next, victim selection runs. Suppose T1 has undo log size 100, T2 has 500, and T3 has 50. The cheapest to rollback is T3. The system aborts T3, releases its locks on row C, and removes all edges incident to T3. T2 is now granted lock on C and resumes, then T1 is granted lock on B. The deadlock is resolved with minimal work lost. If periodic detection were used instead, the cycle would have persisted until the next 500ms tick, increasing tail latency but saving CPU on the hot lock path.

Querying the Persistent Store

After resolution, a DBA can query the persistent wait_for_graph table to analyze the deadlock. A query like SELECT * FROM wait_for_graph WHERE wait_start_ms > now - 60000 reveals recent waits. Joining with pg_locks or performance_schema.data_locks provides resource details. This observability is a key advantage of a deadlock detection database that maintains both in-memory and persistent storage.

Complexity Analysis

The performance of a deadlock detection database is dominated by graph operations. Understanding their asymptotic costs is essential for tuning detection frequency and storage structures.

Building the WFG is O(1) per edge insertion or deletion when using hash-based adjacency lists, as it involves constant-time set operations. However, maintaining auxiliary indexes like the reverse index doubles the constant factor. For distributed systems, building the global graph requires O(E) network messages where E is the number of cross-node edges.

Cycle detection via DFS is O(V + E) where V is the number of active transactions and E is the number of wait edges. In practice, V is in the hundreds and E is sparse, so this is very fast. Incremental detection starting from a single node is O(V + E) worst-case but often O(d) where d is the depth of the wait chain. The worst case occurs when the graph is dense, which is rare because a transaction typically waits for only one or two resources at a time.

Victim selection is O(k) where k is the cycle length, typically small. Periodic detection that scans the entire graph is O(V + E) per interval, while incremental detection amortizes to O(V + E) per deadlock but adds overhead to every lock wait.

Space complexity is O(V + E) for the in-memory adjacency list, which is optimal. Using an adjacency matrix would be O(V²) and is never used in practice due to sparsity. The persistent store adds O(E) disk space but is typically truncated aggressively. For large V, the recursion stack depth can cause stack overflow in recursive DFS, so iterative implementations with explicit stacks are preferred in production deadlock detection databases.

Variations and Optimizations

Several optimizations improve the basic deadlock detection database beyond naive DFS.

Wait-For Graph Compression and Timeouts

Instead of storing every wait edge, some systems compress edges by resource. If T1 and T2 both wait for T3 on the same resource, only one edge is needed for detection. Additionally, combining detection with timeouts provides a hybrid approach: short waits use detection, long waits are aborted via timeout to handle edge cases where detection is delayed. This prevents starvation when detection intervals are long.

Incremental and On-Demand Detection

Rather than scanning the entire graph periodically, incremental detection only checks the subgraph reachable from the newly added edge. This reduces average work dramatically. An even more optimized variant uses topological ordering maintenance: if the graph is kept topologically sorted, an edge that respects the order cannot create a cycle and requires no DFS. Only edges that violate the order trigger a search.

Priority and Cost-Aware Storage

Advanced deadlock detection databases store additional metadata to make victim selection smarter. Instead of simply aborting the youngest transaction, they consider undo log size, transaction priority, number of locks held, and whether the transaction is interactive. Some systems implement wound-wait or wait-die schemes within the detection framework: high-priority transactions wound low-priority holders by aborting them preemptively, avoiding the need for cycle detection in many cases.

Lock-Free and MVCC Optimizations

Modern MVCC databases reduce deadlocks by using non-blocking reads. The deadlock detection database then only tracks write-write conflicts, shrinking the graph significantly. Storage can be made lock-free using concurrent hash maps and atomic edge lists, allowing the lock manager to operate without latching the WFG. Another optimization is to partition the WFG by resource hash, enabling parallel detection on different partitions.

Real-World Applications

Deadlock detection databases are ubiquitous in systems requiring strong consistency under concurrency.

In relational databases such as PostgreSQL, MySQL InnoDB, Oracle, and SQL Server, the deadlock detector is a core component of the lock manager. PostgreSQL checks for deadlocks every one second and also on every lock wait exceeding deadlock_timeout. InnoDB performs immediate detection on every wait. These systems handle thousands of TPS with row-level locks, and without detection, deadlocks from foreign key checks and index updates would cause outages.

In distributed databases like Google Spanner, CockroachDB, and TiDB, distributed deadlock detection is essential. Spanner uses a combination of wound-wait and distributed detection for its TrueTime-based transactions. CockroachDB uses a distributed WFG with a centralized coordinator that collects intents. These systems must handle network partitions and clock skew, making probe-based algorithms more robust than global collection.

Beyond traditional databases, deadlock detection databases appear in operating system kernels for file locks, in Kubernetes for container volume attachment, and in microservice orchestration where sagas wait for compensating transactions. Even blockchain systems use similar graphs to detect circular dependencies in smart contract calls.

Choosing the right storage and query model depends on scale and latency requirements. In-memory detection offers microsecond latency but loses history on crash. Persistent storage enables auditing and ML-based prediction of deadlock-prone access patterns, allowing proactive reordering of queries.

Comparison with Alternatives

Deadlock detection is one of four classic strategies for handling deadlocks. Understanding its trade-offs against prevention, avoidance, and timeout-based approaches is crucial for system design.

Deadlock prevention statically prevents cycles by imposing a global ordering on resources and requiring transactions to acquire locks in order. It has zero runtime detection overhead but reduces concurrency and requires application changes. Deadlock avoidance uses the Banker's algorithm to check if granting a lock would lead to an unsafe state, requiring knowledge of future lock needs which is rarely available. Timeout-based schemes simply abort transactions that wait longer than a threshold, which is simple but causes false positives and long tail latencies.

A deadlock detection database offers the best concurrency and requires no prior knowledge of transaction behavior, at the cost of runtime overhead for graph maintenance and periodic queries. It is the preferred choice when workloads are unpredictable and throughput is paramount.

In practice, most production deadlock detection databases blend strategies: they use detection as the primary mechanism but add timeouts as a safety net for distributed deadlocks that probes might miss, and they use prevention for specific high-contention resources like catalog tables.

Common Mistakes and Best Practices

Building a robust deadlock detection database is error-prone. Common pitfalls can lead to missed deadlocks, false positives, or performance collapse.

A frequent mistake is using coarse-grained latching around the entire WFG. If every lock request must acquire a global latch to update the graph, the detector becomes a bottleneck that serializes all transactions. The best practice is to use fine-grained per-transaction latches or lock-free structures, and to perform detection on a snapshot rather than holding latches during DFS.

Another mistake is running full graph scans too frequently. Scanning a graph with thousands of nodes every 10ms can consume significant CPU, especially when no deadlocks exist. The solution is adaptive detection: use incremental checks on edge insertion for low latency, and periodic full scans at a lower frequency as a backup. Also, failing to clean up edges promptly after commit or abort leads to phantom cycles and false positives. Always remove edges in the same critical section that releases the lock.

Choosing a poor victim is also costly. Aborting a transaction that has done extensive work wastes resources and increases retry storms. Best practice is to select the victim with the smallest undo log, lowest priority, or fewest locks held. Some systems also consider transaction age to avoid starving old transactions.

• Do: Use iterative DFS to avoid recursion depth limits and stack overflow on long wait chains.
• Do: Persist deadlock events to a system table for post-mortem analysis and alerting.
• Do: Test with synthetic deadlock generators that create random wait patterns under load.
• Do: Combine detection with exponential backoff on retry to avoid immediate re-deadlock.
• Do not: Store the WFG in a single global adjacency matrix; it wastes memory and is slow for sparse graphs.
• Do not: Ignore distributed deadlocks; a local-only detector will miss cross-shard cycles.
• Do not: Abort without releasing all locks and cleaning up reverse indexes atomically.

Finally, observability is critical. Expose metrics such as wait edge count, detection latency, deadlock rate, and victim abort count via system views. This allows operators to identify hot resources and refactor application logic to access tables in a consistent order, reducing deadlocks at the source.

Interview Questions

1. How do you detect a deadlock in a database using the Wait-For Graph?

Answer: Maintain a directed graph where nodes are transactions and an edge T1 -> T2 means T1 waits for a lock held by T2. A deadlock exists iff the graph has a directed cycle. Detection is performed via DFS with three-color marking or via topological sort. If DFS encounters a gray node currently in the recursion stack, a cycle is found. The system then selects a victim to abort and breaks the cycle. Complexity is O(V + E) for a full scan and O(d) for incremental detection from the new edge.

2. What is the difference between deadlock detection, prevention, and avoidance?

Answer: Detection allows deadlocks to happen and then finds and resolves them by aborting a victim; it offers high concurrency but incurs runtime overhead. Prevention statically avoids deadlocks by imposing a global lock ordering, which eliminates runtime checks but reduces concurrency. Avoidance uses the Banker's algorithm to check if granting a lock keeps the system in a safe state, requiring knowledge of future needs and being too expensive for most databases. Most OLTP systems use detection with timeouts as a fallback.

3. How would you implement a deadlock detection database for a distributed system?

Answer: No single node has the full WFG, so you need either centralized collection where each node ships its local subgraph to a coordinator for global DFS, or decentralized edge-chasing where probes follow wait edges via RPCs. Edge-chasing is more scalable: when T1 waits for T2 on another node, a probe containing the path is forwarded along wait edges; if it returns to the initiator, a cycle is detected. You must handle probe expiration, duplicate suppression, and network partitions. Storage is partitioned by transaction or resource hash.

4. What data structure should you use to store the Wait-For Graph and why?

Answer: An adjacency list using hash maps of sets is optimal because the WFG is sparse; each transaction waits for few others. It gives O(1) edge insertion/deletion and O(V + E) traversal. An adjacency matrix would be O(V²) space and is wasteful. You should also maintain a reverse index from holder to waiters for fast cleanup when a transaction commits. For persistence, mirror edges to a relational table with indexes on holding_txn_id for fast queries.

5. How do you choose which transaction to abort when a deadlock is detected?

Answer: Victim selection aims to minimize wasted work and avoid starvation. Common policies include aborting the transaction with the smallest undo log or fewest locks held, the youngest transaction, or the lowest priority. Some systems use cost-based selection that considers CPU time, I/O, and whether the transaction has already been retried. In priority-based schemes like wound-wait, higher-priority transactions wound lower-priority ones preemptively. Always log the victim and cycle for analysis.