Two-Phase Locking (2PL)

The protocol's core rule mandates that every transaction must execute in two consecutive, non-overlapping phases:

• Growing Phase: The transaction may acquire locks on data items (read or write locks) but cannot release any locks.
• Shrinking Phase: The transaction may release locks but cannot acquire any new locks.

Once a lock is released, the transaction enters the shrinking phase and is prohibited from obtaining further locks, which guarantees the transaction's operations can be serialized relative to others.

2PL is a sufficient condition for conflict serializability. By enforcing the two-phase rule, it creates an ordering where all of a transaction's lock points (the moment it acquires its final lock) define a global serialization order. If all transactions follow 2PL, any resulting schedule is guaranteed to be serializable, meaning it is equivalent to some serial execution of those transactions, preserving database consistency.

Basic 2PL can lead to cascading rollbacks. Variants strengthen the protocol:

• Strict 2PL: A transaction holds all its exclusive (write) locks until it commits or aborts. This prevents uncommitted data from being read or overwritten by other transactions, eliminating cascading rollbacks.
• Rigorous 2PL: A transaction holds all locks (both shared and exclusive) until commit/abort. This is the most common implementation in database systems.
• Conservative 2PL (Static 2PL): Requires a transaction to pre-declare and acquire all needed locks at once before execution begins. This prevents deadlock but is often impractical.

2PL does not prevent deadlock. Deadlocks arise from the hold-and-wait condition inherent in the growing phase. Example: Transaction T1 holds lock A and requests lock B, while Transaction T2 holds lock B and requests lock A. This circular wait results in a deadlock, which the system must resolve via deadlock detection (using a wait-for graph) and recovery (e.g., aborting a victim transaction).

2PL's behavior depends on the lock manager's rules:

• Compatibility Matrix: Shared (read) locks are typically compatible with other shared locks but conflict with exclusive (write) locks. Exclusive locks conflict with all other locks.
• Lock Granularity: Locks can be applied at different levels (e.g., table, page, row, field). Fine-grained locking (e.g., row-level) increases concurrency but raises lock management overhead. Coarse-grained locking (e.g., table-level) reduces overhead but severely limits concurrency.
• Intention Locks: Used in hierarchical locking schemes (e.g., database -> table -> row) to efficiently manage locks at multiple granularities.

The principles of 2PL extend beyond databases to multi-agent systems and heterogeneous fleet orchestration, where agents (robots, vehicles) contend for spatial resources (intersections, charging stations, warehouse bins).

• Agents as Transactions: Each agent's planned path is a transaction requiring locks on spatial zones.
• Growing Phase: The agent reserves all zones along its planned path.
• Shrinking Phase: The agent releases zones as it physically vacates them. This prevents two agents from being scheduled into the same physical space simultaneously, ensuring collision-free schedules but introducing the risk of gridlock (spatial deadlock).

A design strategy that ensures at least one of the four necessary conditions for deadlock cannot hold, making deadlocks impossible. Unlike detection or recovery, prevention is proactive.

• Conditions Prevented: Strategies target Mutual Exclusion, Hold and Wait, No Preemption, or Circular Wait.
• Comparison to 2PL: Strict Two-Phase Locking can lead to deadlocks, requiring complementary prevention or detection schemes.
• Example Protocols: The Wait-Die and Wound-Wait protocols use timestamps to prevent circular wait.

A runtime strategy where the system only grants resource requests if the resulting state is guaranteed to be safe, dynamically preventing future deadlock.

• Core Mechanism: Requires advance knowledge of maximum resource needs (a claim).
• Banker's Algorithm: The classic algorithm for deadlock avoidance. It simulates allocations to test for safe sequences before committing resources.
• Contrast with 2PL: 2PL manages locks but does not inherently avoid deadlock; avoidance algorithms like Banker's can be layered on top of a locking protocol.

A directed graph used to model dependencies between processes or agents, where an edge from P_i to P_j indicates P_i is waiting for a resource held by P_j.

• Primary Use: The central data structure for deadlock detection algorithms.
• Cycle Detection: A cycle in the WFG indicates a deadlock. Algorithms continuously or periodically scan the graph for cycles.
• Relation to 2PL: In a database using 2PL, transactions holding and waiting for locks map directly to nodes and edges in a system-wide WFG.

A non-preemptive, timestamp-based deadlock prevention scheme. It prevents the circular wait condition by imposing a strict ordering on how processes can wait.

• Rule: If process P_i requests a resource held by P_j, P_i is allowed to wait only if it is older (has a smaller timestamp) than P_j. If P_i is younger, it is aborted (it dies).
• Non-Preemptive: The holder P_j keeps the resource; the requester P_i is terminated.
• Context: Often contrasted with the Wound-Wait protocol. Both provide deadlock-free execution but with different abort/preemption characteristics.

The process of identifying deadlocks in a system where processes and resources are distributed across multiple nodes, requiring coordination via message passing.

• Challenge: No single node has a complete, global view of the Wait-For Graph.
• Edge-Chasing Algorithms: Methods like the Chandy-Misra-Haas algorithm where special probe messages traverse the distributed WFG to detect cycles.
• Relevance: Essential for distributed databases or multi-agent fleets where agents on different physical systems may become mutually blocked.

A scheduling anomaly where a high-priority task is blocked waiting for a resource held by a lower-priority task. This can cause unbounded blocking and deadlock-like scenarios in real-time systems.

• Mechanism: A medium-priority task can preempt the low-priority task holding the resource, indirectly blocking the high-priority task indefinitely.
• Solution - Priority Inheritance Protocol: Temporarily raises the priority of the low-priority holder to that of the highest-priority waiter, allowing it to finish and release the resource.
• Connection to Locking: A direct consequence of priority-based scheduling combined with mutual exclusion locks, a common issue in robotic and embedded systems using concurrency control.