Prof Philippas Tsigas Distributed Computing and Systems Research Group

• Prof Philippas Tsigas

• Distributed Computing and Systems Research Group

Picture from Computers and Intractability, by Garey and Johnson

• Picture from Computers and Intractability, by Garey and Johnson

Picture from Computers and Intractability, by Garey and Johnson

• Picture from Computers and Intractability, by Garey and Johnson

Picture from Computers and Intractability, by Garey and Johnson

• Picture from Computers and Intractability, by Garey and Johnson

transaction atomicity requires that at the end,

• transaction atomicity requires that at the end,

• either all of its operations are carried out or none of them.

• in a distributed transaction, the client has requested the operations at more than one server

• one-phase atomic commit protocol

• the coordinator tells the participants whether to commit or abort
• what is the problem with that?
• this does not allow one of the servers to decide to abort – it may have discovered a deadlock or it may have crashed and been restarted

• two-phase atomic commit protocol

• is designed to allow any participant to choose to abort a transaction
• phase 1 - each participant votes. If it votes to commit, it is prepared. It cannot change its mind. In case it crashes, it must save updates in permanent store
• phase 2 - the participants carry out the joint decision

Failure model for transactions

• Failure model for transactions

• this applies to the two-phase commit protocol

• Commit protocols are designed to work in

• synchronous system, system failure when a msg does not arrive on time.
• servers may crash but a new process whose state is set from information saved in permanent storage and information held by other processes.
• messages may NOT be lost.
• assume corrupt and duplicated messages are removed.
• no byzantine faults – servers either crash or they obey their requests

• 2PC is an example of a protocol for reaching a consensus.

• Chapter 11 says consensus cannot be reached in an asynchronous system if processes sometimes fail.
• however, 2PC does reach consensus under those conditions.
• because crash failures of processes are masked by replacing a crashed process with a new process whose state is set from information saved in permanent storage and information held by other processes.

participant interface- canCommit?, doCommit, doAbort coordinator interface- haveCommitted, getDecision

• participant interface- canCommit?, doCommit, doAbort coordinator interface- haveCommitted, getDecision

Phase 1 (voting phase):

• Phase 1 (voting phase):

• 1. The coordinator sends a canCommit? request to each of the participants in the transaction.
• 2. When a participant receives a canCommit? request it replies with its vote (Yes or No) to the coordinator. Before voting Yes, it prepares to commit by saving objects in permanent storage. If the vote is No the participant aborts immediately.

• Phase 2 (completion according to outcome of vote):

• 3. The coordinator collects the votes (including its own).
• (a)If there are no failures and all the votes are Yes the coordinator decides to commit the transaction and sends a doCommit request to each of the participants.
• (b)Otherwise the coordinator decides to abort the transaction and sends doAbort requests to all participants that voted Yes.
• 4. Participants that voted Yes are waiting for a doCommit or doAbort request from the coordinator. When a participant receives one of these messages it acts accordingly and in the case of commit, makes a haveCommitted call as confirmation to the coordinator.

canCommit?

• canCommit?

canCommit?

• canCommit?

canCommit?

• canCommit?

canCommit?

• canCommit?

if there are no failures, the 2PC involving N participants requires

• if there are no failures, the 2PC involving N participants requires

• N canCommit? messages and replies, followed by N doCommit messages.
• the cost in messages is proportional to 3N, and the cost in time is three rounds of messages.
• The haveCommitted messages are not counted
• there may be arbitrarily many server and communication failures
• 2PC is is guaranteed to complete eventually, but it is not possible to specify a time limit within which it will be completed
• delays to participants in uncertain state
• some 3PCs designed to alleviate such delays
• they require more messages and more rounds for the normal case

Recall Fig 13.1b, top-level transaction T and subtransactions T1, T2, T11, T12, T21, T22

• Recall Fig 13.1b, top-level transaction T and subtransactions T1, T2, T11, T12, T21, T22

• A subtransaction starts after its parent and finishes before it

• When a subtransaction completes, it makes an independent decision either to commit provisionally or to abort.

• A provisional commit is not the same as being prepared: it is a local decision and is not backed up on permanent storage.
• If the server crashes subsequently, its replacement will not be able to carry out a provisional commit.

• A two-phase commit protocol is needed for nested transactions

• it allows servers of provisionally committed transactions that have crashed to abort them when they recover.