Massachusetts Institute of Technology Handout 6 6.852: Distributed Algorithms Prof. Nancy Lynch September 24, 2009 Problem Set 2, Part a Due: Thursday, October 8, 2009 Reading: Section 5.1, Chapter 6 of Distributed Algorithms Aguilera, Toueg paper, listed in Handout 3 (Optional) Keidar, Rajsbaum paper Reading for next week: Chapter 7 (especially 7.1) Chapter 8 Problems: 1. Exercise 5.2. 2. Modify the FloodSet algorithm of Section 6.2.1 by adding a local early decision test condition, in order to obtain the following additional early decision time bound property: If the execution has only f� ≤ f failures, then all nonfaulty processes decide (but don’t halt) by the end of round f� + 2. Prove that your algorithm works, that is, that it solves the stopping agreement problem for stopping failures, and that it has the additional time bound property. Note: Recall that we require the uniformity property, which says that all processes that decide (even if they later fail), decide on the same value. 3. Section 6.3.3 contains a simple algorithm (TurpinCoan) for Byzantine agreement on an arbitrary value domain V . This algorithm uses a Byzantine agreement algorithm for bits as a “subroutine”. At the cost of two extra rounds, this algorithm manages to substantially reduce the bit complexity, over the standard Exponential Information Gathering Byzantine Agreement algorithm for V . (a) Read the description of this algorithm, and its correctness proof. (b) Do Exercise 6.22, which asks you to generalize the algorithm slightly. 4. Exercise 6.33. 5. Consider a different kind of process failure model for synchronous systems: a “transient failure” model. In this model, a process may fail at a particular round, which means that it sends an arbitrary subset of the messages it is supposed to send (perhaps all of them), and does not perform its state transition. A process that exhibits a transient failure at a round r continues as if nothing is wrong at the following round r + 1. Permanent failure of a process at round r is modeled by transient failure at all rounds greater than or equal to r. For this problem, we assume that, at each round, at most one process exhibits a transient failure. We do not assume an overall bound on the number of processes that ever exhibit a transient failure during an execution. Now consider the agreement problem in this transient failure model: each process that does not fail permanently should eventually decide, subject to the usual agreement condition for stopping agreement, and the strong validity condition (every process’ decision is some process’ initial value).2 Handout 6: Problem Set 2, Part a Is this problem solvable in the given model? If so, describe an algorithm and sketch a proof that it works. If not, try to prove impossibility (carefully), using techniques like the ones in the Aguilera-Toueg paper.MIT OpenCourseWarehttp://ocw.mit.edu 6.852J / 18.437J Distributed Algorithms Fall 2009 For information about citing these materials or our Terms of Use, visit:
View Full Document
Unlocking...