I am currently reading through this http://research.microsoft.com/en-us/people/philbe/chapter7.pdf chapter about distributed recovery. The chapter focuses on 2 phase atomic commit (2PC) and 3 phase atomic commit (3PC). Two related questions have me stumped.

7.11: In the 2PC protocol the coordinatorfirst decides Commit (by writing a commit record to its site’s DT log) and then sends COMMIT messages to the participants. Suppose the order of these two steps is reversed. Show that this variation of 2PC is non-blocking if

a. there are no communication failures and at most one process can fail,


b. there are no communication failures and processes have the ability to broadcast messages atomically (i.e., so that either all recipients get it or no recipient does).

How does this variation of 2PC affect the recovery procedures? Give recovery procedures that work for the modified 2PC protocol.

7.22: In 3PC, does the relative order of sending COMMIT messages and writ- ing a commit record in the DT log matter? What about the relative order of sending ABORT messages and writing an abort record?

The first does not seem particularly hard, but I am unsure of how to actually prove that a program is non-blocking. The second question is a bit more complex. My intuition is that 3PC has enough built in safeguards with the PRE-COMMIT phase that changing the order wouldn't matter, but again I am uncertain of what a proof of this would look like.

  • $\begingroup$ could there be a way to build the 3PC proof out of the 2PC proof ie as a generalization or extension? 2PC is widespread and 3PC sounds rather unconventional. it might help to include short defns of 2PC and 3PC. $\endgroup$ – vzn Apr 14 '13 at 16:06
  • $\begingroup$ try this can 3PC guarantee atomicity stackoverflow $\endgroup$ – vzn Apr 14 '13 at 16:11
  • 1
    $\begingroup$ This question is part of a homework assignment which the professor has explicitly requested to be an individual effort. The fact that it's being asked here not only violates the school's honor code but also is personally offensive to all other students that are abiding by the rules laid out by the professor. Please refrain from posting answers to this question until Monday, April 15th, 2013 at 3:15 EST. $\endgroup$ – COMP735Student Apr 14 '13 at 16:57
  • $\begingroup$ @comp735student what school? and by the way "individual effort" does not necessarily preclude using the internet or violate an honor code. however its true that homework questions are discouraged on cstheory.se although this is probably acceptable on cs.se $\endgroup$ – vzn Apr 15 '13 at 1:05
  • $\begingroup$ @vzn: I thought it would be fairly obvious that asking someone on the internet the answer to the question precludes individual effort. $\endgroup$ – Dave Clarke Apr 15 '13 at 17:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy