Approaches to avoid distributed deadlock

A deadlock happens when transactions wait for each other's locks in a cycle. It can be prevented by breaking one of its necessary conditions (mutual exclusion, hold and wait, no pre-emption, circular wait). The alternative approaches are:

1. Lock all objects at the start (no hold and wait): a transaction acquires all its locks at the start in one atomic step. It is simple but wastes concurrency, and the required objects are often not known in advance.
2. Ordering of resources (no circular wait): lock objects in a fixed global order. A transaction cannot request an earlier object while holding a later one. This is hard to apply across many servers.
3. Timeouts: a lock is valid for a limited time. After the time limit, the lock is vulnerable; if another transaction wants it, the holder is aborted. Easy, but it aborts transactions that were only slow, and the timeout value is hard to choose.
4. Timestamp-based prevention (each transaction has a unique timestamp, older = smaller):
   • Wait-die (non-pre-emptive): if the requester is older than the holder, it waits; if younger, it dies (aborts and restarts with the same timestamp).
   • Wound-wait (pre-emptive): if the requester is older, it wounds (aborts) the holder; if younger, it waits. In both, waiting goes in only one direction (by age), so no cycle can form, and there is no starvation because a restarted transaction keeps its original timestamp.
5. Optimistic or timestamp ordering concurrency control: no locks, so no deadlock.

If avoidance is too restrictive, detection and recovery (wait-for graph, edge chasing, abort a victim) are used instead.