Need of transaction; phantom deadlock

Why transactions are necessary

A transaction is a sequence of operations on shared data that the system treats as one indivisible unit of work: either all operations take effect or none does. It is described by the ACID properties:

• Atomicity: all or nothing.
• Consistency: it moves the data from one consistent state to another.
• Isolation: concurrent transactions do not see each other's intermediate results (appear serial).
• Durability: once committed, results survive crashes (stored in permanent storage).

Without transactions, concurrent access to shared data can give lost updates and inconsistent retrievals, and a crash in the middle of an operation (e.g. debit done, credit not done) leaves the data inconsistent. A transaction gives reliable, correct processing in the presence of concurrency and failures. Example: transfer of Rs 100 from account A to B must debit A and credit B together.

Deadlock

A deadlock is a state in which each transaction in a set is waiting for a lock held by another transaction in the set, so none can proceed. It is shown by a cycle in the wait-for graph (nodes are transactions, an edge T → U means T waits for U).

A distributed deadlock occurs when the wait-for cycle spans several servers. Each server sees only a part of the graph (a local wait-for graph without a local cycle), but the global graph has a cycle.

Example: T holds a lock on A at server X, and U holds a lock on B at server Y. T now requests B at Y (so T waits for U), and U requests A at X (so U waits for T).

Server X: U -> T  (U waits for T on A)
Server Y: T -> U  (T waits for U on B)
Global:   T -> U -> T   (cycle = deadlock)

Phantom deadlock

A phantom deadlock is a deadlock that is detected but does not really exist. It arises in distributed detection because the information gathered from different servers is not from the same instant: a transaction may release its lock (and finish) after its local graph was sent but before the global graph is built. The coordinator then sees a cycle that is no longer present and may abort a transaction unnecessarily. Example: server X reports the edge T → U and server Y reports U → T. Before the coordinator builds the global graph, U is aborted (e.g. by a lock timeout) and releases its locks, so T no longer waits for U. The coordinator, working from the stale edges, still sees the cycle T → U → T and may abort T unnecessarily.