Wait-Die Protocol

The protocol's core logic is driven by transaction timestamps (e.g., a monotonically increasing start time). This establishes a global age-based hierarchy:

• Older transactions (lower timestamp) have priority over younger transactions (higher timestamp).
• This deterministic ordering prevents cyclic waits, which are the necessary condition for deadlock. The age-based rule ensures that conflicts are resolved in a consistent, predictable manner across the system.

When Transaction T_i requests a resource held by Transaction T_j, the system applies a single rule based on their timestamps:

• Wait: If T_i is older than T_j, then T_i is allowed to wait for the resource. The older transaction is patient.
• Die: If T_i is younger than T_j, then T_i is immediately aborted (it 'dies'). The younger transaction is restarted later with the same timestamp, preserving its age. This asymmetric rule guarantees that waits only flow from older to younger transactions, breaking potential cycles.

A key characteristic is that Wait-Die is non-preemptive. When an older transaction waits for a resource held by a younger one, it does not forcibly take the resource. The younger transaction continues to hold the resource until it completes or is aborted for another reason. This contrasts with the Wound-Wait protocol, where an older transaction can preempt (wound) a younger one. The non-preemptive approach simplifies rollback logic but can lead to older transactions waiting for extended periods if younger ones are long-lived.

The 'die' action is a form of victim selection. The younger transaction is always the victim. When aborted:

• It performs a full rollback, releasing all its held resources.
• It is restarted after a delay with its original timestamp unchanged. Maintaining the timestamp is crucial; if it were given a newer timestamp, it could repeatedly die in a cycle of conflicts with the same older transaction, causing starvation.
• This restart mechanism is predictable but can lead to resource waste if the same transaction repeatedly conflicts with older, long-running transactions.

The protocol's design mathematically prevents deadlock. A deadlock requires a circular wait (e.g., T1 waits for T2, T2 waits for T1). Under Wait-Die, waits are only permitted from older to younger transactions. Therefore, any potential wait cycle would require timestamps to simultaneously satisfy T1 < T2 and T2 < T1, which is impossible. This makes the system provably safe from deadlocks, a critical property for high-reliability systems, though it achieves this at the cost of potentially unnecessary aborts.

Wait-Die is most applicable in systems where:

• Transactions can be aborted and restarted without severe side effects.
• Assigning a global, meaningful timestamp is feasible.
• Preventing deadlock absolutely is more important than maximizing throughput. Primary Trade-off: It exchanges deadlock safety for potential throughput reduction due to aborts and waits. Performance degrades under high contention, as many young transactions may die. It favors older transactions, which can lead to starvation for younger ones in persistently busy systems. It is often compared with Wound-Wait and deadlock detection schemes.

The Wound-Wait protocol is the symmetric counterpart to Wait-Die, also using transaction timestamps for deadlock prevention. Its core rule is inverted: an older transaction can forcibly abort (wound) a younger transaction holding a needed resource, while a younger transaction must wait if it requests a resource held by an older one. This prioritizes older transactions through preemption rather than sacrifice.

• Mechanism: Older transactions wound younger ones; younger transactions wait for older ones.
• Key Difference: Wait-Die sacrifices the younger requester; Wound-Wait sacrifices the younger holder.
• Outcome: Both guarantee freedom from deadlock but differ in which transactions are aborted under conflict.

Deadlock prevention is a proactive design strategy that constrains resource requests to ensure one of the four necessary conditions for deadlock (Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait) can never hold. Wait-Die is a prevention algorithm.

• Goal: System design that makes deadlock impossible.
• Methods: Includes resource ordering, requiring all resources at once (negating Hold and Wait), or using protocols like Wait-Die/Wound-Wait.
• Trade-off: Prevention often reduces concurrency or system throughput compared to deadlock detection and recovery.

Deadlock detection is a reactive strategy that allows the four deadlock conditions to occur, periodically examines the system's resource allocation graph for cycles, and then invokes a recovery procedure. This contrasts with Wait-Die's preventive approach.

• Process: System runs normally; a detection algorithm is invoked at intervals to find circular waits.
• Recovery: Upon detection, the system recovers by aborting one or more transactions (victim selection) or preempting resources.
• Use Case: Preferred when deadlocks are infrequent, as it avoids the runtime overhead of prevention on every request.

The Banker's Algorithm is a deadlock avoidance algorithm that uses advance knowledge of maximum resource needs. Before granting any request, it performs a safety check to simulate allocation and ensure a sequence exists where all agents could still potentially finish. Wait-Die prevents deadlock; Banker's avoids it.

• Principle: Only grants requests that lead to a safe state.
• Requirement: Must know maximum future resource demands for all agents in advance.
• Context: A classic algorithm for systems with multiple resource types, but its conservative nature can limit resource utilization.

Timestamp Ordering (TO) is a concurrency control protocol in databases that, like Wait-Die, uses transaction timestamps to serialize execution order and ensure consistency. However, TO focuses on ensuring serializable schedules, not directly on deadlock prevention.

• Basic Rule: If Transaction Ti tries to read/write a data item written by a younger Transaction Tj, Ti is aborted and restarted.
• Relation to Wait-Die: Both use timestamps to establish a global priority order. Wait-Die applies this logic specifically to lock conflicts for deadlock prevention, while TO applies it to all read/write operations for serializability.
• Outcome: TO can also prevent deadlocks because it creates a total order of transactions.

Two-Phase Locking (2PL) is a fundamental concurrency control protocol that guarantees serializability by requiring transactions to acquire all locks in a growing phase and release them only in a subsequent shrinking phase. Wait-Die is often implemented on top of a locking system like 2PL to manage lock conflicts.

• Phases: Growing Phase (acquire locks, no releases) and Shrinking Phase (release locks, no acquires).
• Deadlock Potential: Basic 2PL can create deadlocks (circular wait on locks).
• Integration: Wait-Die and Wound-Wait are deadlock prevention schemes used to resolve lock conflicts within a 2PL framework, ensuring the system progresses without deadlock detection overhead.