T_i requests a lock on a data item that is already locked by T_j

• The WAIT-DIE rule:
• IF ts(Ti) < ts(Tj) 
• THEN Ti waits
• ELSE Ti dies (abort and restart with same timestamp)
• The WOUND-WAIT rule:
• IF ts(Ti) < ts(Tj)
• THEN Tj is wounded (aborts and restarts with same timestamp)
• ELSE Ti waits

Note: WOUND-WAIT pre-empts active transactions 

1. Study the GWFG for cycles (detection)
2. Break cycles by aborting transactions (resolution)

Selecting minimum total cost sets of transactions to abort is NP-compelte

Three main approaches to deadlock detection:

• Centralized
• Hierarchical 
• Distributed

• One site is designed as the deadlock detector (DD) for the system
• Each site sends its LWFG (or changes to its LWFG) to the DD at intervals
• DD constructs the GWFG and looks for cycles

• Each site has a DD, which looks in the site's LWFG for cycles
• Each site sends its LWFG at the next level, which merges the LGFW to the DD at the next level, which merges the LWFGs send to it and looks for cycles
• These DDs send the merged WFGs to the next level and so on

• Responsibility for detecting deadlocks is delegated to sites
• LWFGs are modified to show relationships between local transactions and remote transactions
• LWFG containsa  cycle not involving external edges (local deadlocks, resolve locally)
• LWFG contains a cycle involving external edges
• Potential deadlock - communicate to other sites
• Sites must then agree on a victim transaction to abort

• Non distributed databases aim to maintain atomicity and durability of transactions
• Atomicity: A transaction is either performed completely or not at all
• Durability: Once a transaction has been committed, changes should not be lost because of failure
• As with parallel databases, distributed databases use the two phase commit protocol (2PC) to preserve atomicity

• Distinguish between global transaction and local transactions into which the global transaction is decomposed

1. Voting
• Coordinator sends "prepare T" message to all participants
• Participants respond with either "vote-commit T" or vote-abort T"
• Coordinator waits for participants to respond with a timeout period
2. Decision
• If all participants return "vote-commit T" (to commit), send "commit T" to all participants. Wait for acknowledgements within timeout period.
• If any participant returns "vote-abort T", send "abort T" to all participants. Wait for all acknowledgements within timeout period
• When all acknowledgements received, trnsaction is completed
• If a site does not acknowledge, resend global decision until it is acknowledged

[image]

• If coordinator or participant fails during commit, two things happen:
• The other sites will time out while waiting for the next message from the failed site and invoke a termination protocol
• When the failed site restarts, it tries to work out the state of the commit by invoking a recovery protocol
• The behaviour of the sites under these protocols depends on the state they were in when the site failed

• Timeout in WAIT
• Coordinator is waiting for participants to vote on whether they're going to commit or abort
• A missing vote means that the coordinator cannot commit the global transaction
• Coordinator may abort the global transaction
• Timeout in COMMIT/ABORT
• Coordinator is waiting for participants to acknowledge successful commit or abort
• Coordinator resends global decision to participants who have not acknowledged

• Timeout in INITIAL
• Participant is waiting for a "prepare T"
• May unilaterally abort the transaction after a timeout
• If "Prepare T" arrives after the unilateral abort, either:
• Resend the "volte-abort T" message or
• ignore (coordinator then times out in WAIT)
• Timeout in READY
• Participant is waiting for the instruction to commit or abort - blocked without further information
• Participant can contact other participants to find one that knows the decision - cooperative termination protocol

• Failure in INITIAL
• Commit not yet begun, restart commit procedure
• Failure in WAIT
• Coordinator not yet begun, restart commit procedure
• Recovery restarts commit procedure by resending "prepare T"
• Failure in COMMIT/ABORT
• If coordinator has received all "ack" messages, complete successfully
• Otherwise, terminate

• Failure in INITIAL
• Participant has not yet voted
• Coordinator cannot have reached a decision
• Participant should unilaterally abort by sending "vote-abort T"
• Failure in READY
• Participant has voted, but doesn't know what the global decision was
• Cooperative termination protocol
• Failure in COMMIT/ABORT
• Resend "Ack" message

• First phase from the coordinator to the participants
• Second phase from the participants to the coordinator
• Participants may unilaterally abort

[image]

• Linear 2PC involves fewer messages
• Centralised 2PC provides opportunities for parallelism
• Linear 2PC has worse reponse time performance

• The Consistency-Availability-PartitionTolerance theorem is an example of the trade-off between safety and liveness in an unreliable system
• Safety: nothing bad ever happens
• Liveness: Eventually something good happens
• We can only manage two of the three form C, A, P (Typically we sacrifice either availability (liveness) or consistency (safety)
• In any distributed system, there is a tradeoff between:
• Consistency - Each server always returns the correct response to each request
• Availability - Each request eventually receives a response
• Partition tolerance - Communication may be unreliable (messages delayed, lost, servers partitioned into groups that cannot communicate with each other) but the system as a whole should continute to function