Wait-Die Protocol

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.

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.