Distributed Algorithms. Nancy A. Lynch (1993) (Distributed Algorithms. Nancy A. Lynch (1993).pdf), страница 75

Determine and L in terms of p for your algorithm.3. In the proofs of bounds for randomized generals algorithms, we used two denitions ofinformation level: level A(i k), and mlevel A (i k). Prove that for any A, i and k, thesetwo are always within 1 of each other.4. Be the Adversary!(a) Consider the algorithm given in class for consensus in the presence of processorstopping faults (based on a labeled tree). Suppose that instead of running forf + 1 rounds, the algorithm only runs for f rounds, with the same decision rule.Describe a particular execution in which the correctness requirements are violated.(Hint: a process may stop \in the middle" of a round, before completing sendingall its messages).(b) Now consider the algorithm given for consensus in the presence of Byzantinefaults. Construct an execution to show that the algorithm gives a wrong result ifit is run with either (i) 7 nodes, 2 faults, and 2 rounds, or (ii) 6 nodes, 2 faults,and 3 rounds.5.

Using the stopping fault consensus algorithm as a starting point, modify the correctnessconditions, algorithm and proof as necessary to obtain a consensus algorithm that isresilient to Byzantine faults, assuming that authentication of messages is available.3646. (optional) Consider the optimized version of the stopping fault consensus algorithm,where only the rst two messages containing distinct values are relayed. In this algorithm it isn't really necessary to keep all the tree information around. Can you reducethe information kept in the state while still preserving the correctness of the algorithm?You should sketch a proof of why your \optimized" algorithm works.3656.852J/18.437J Distributed AlgorithmsHandout 12October 1, 1992Homework Assignment 4Due: Thursday, October 8ReadingLynch and Tuttle, An Introduction to Input/Output Automata, CWI-Quarterly, 2(3), 1989.Exercises1.

Consider the network graph G depicted in Figure 25.9.bdfcegaFigure 25.9: the graph G is a 7-node, 2-connected communication graphShow directly (i.e., not by quoting the connectivity bound stated in class, but by aproof specic to this graph) that Byzantine agreement cannot be solved in G when 2processors are faulty.2. In class, a recursive argument was used to show impossibility of f -round consensusin the presence of f stopping failures.

If the recursion is unwound, the argumentessentially constructs a long chain of runs, where each two consecutive runs in thechain look the same to some process. How long is the chain of runs?Optional: Can you shorten this chain using Byzantine faults rather than stoppingfaults?3. Write \code" for a correct 3-phase commit protocol.4. Fill in more details in the inductive proof of mutual exclusion, for Dijkstra's algorithm.5. Describe an execution of Dijkstra's algorithm in which a particular process is lockedout forever.3666.852J/18.437J Distributed AlgorithmsHandout 17October 15, 1992Homework Assignment 5Due: Thursday, October 22Exercises1. Consider the Burns mutual exclusion algorithm.(a) Exhibit a fair execution in which some process is locked out.(b) Do a time analysis for deadlock-freedom.

That is, assume that each step outsidethe remainder region takes at most 1 time unit, and give upper and lower boundson the length of the time interval in which there is some process in T and noprocess in C (\upper bound" means analysis that applies to all schedules \lowerbound" means a particular schedule of long duration).2. Why does the Lamport bakery algorithm fail if the integers are replaced by the integersmod B , for some very large value of B ? Describe a specic scenario.3.

Design a mutual exclusion algorithm for a slightly dierent model in which there isone extra process, a supervisor process, that can always take steps. The model shoulduse single-writer-multi-reader shared variables. Analyze its complexity.4. Design an atomic read-modify-write object, based on lower-level multi-writer multireader read-write memory. The object should support one operation, apply (f ), wheref is a function. In the serial specication, the eect of apply (f ) on an object with valuev is that the value of the object becomes f (v), and the original value v is returned tothe user.

The executions can assumed to be fair.5. Consider the following variant of the unbounded-registers atomic snapshot object. Inthis variant, the sequence number is also incremented each time a snap is completed(rather than only in update). Does this variant preserve the correctness of the originalalgorithm?3676.852J/18.437J Distributed AlgorithmsHandout 19October 22, 1992Homework Assignment 6Due: Thursday, October 29Exercises1.

Why does the Lamport bakery algorithm fail if the integers are replaced by the integersmod B , for some very large value of B ? Describe a specic scenario.2. Programmers at the Flaky Computer Corporation designed the following protocol forn-process mutual exclusion with deadlock-freedom.Shared variables: x y. Initially y = 0.Code for pi :** Remainder Region **try iL:x := iif y 6= 0 then goto Ly := 1x := iif x 6= i then goto Lcrit i** Critical Region **exit iy := 0rem iDoes this protocol satisfy the two claimed properties? Sketch why it does, or showthat it doesn't. (If you quote an impossibility result to say that it doesn't satisfy theproperties, then you must still go further and actually exhibit executions in which theproperties are violated.)3683. Reconsider the consensus problem using read-write shared memory.

This time supposethat the types of faults being considered are more constrained than general stoppingfailures, in particular, that the only kind of failure is stopping right at the beginning(never performing any non-input steps). Is the consensus problem solvable? Give analgorithm or an impossibility proof.4. Let A be any I/O automaton, and suppose that is a nite execution of A. (a) Provethat there is a fair execution 0 of A (i.e., an extension of ). (b) If is any nite orinnite sequence of input actions of A, prove that there is a fair execution 00 of A,such that the sequnce of input actions of beh (00) is identical to .3696.852J/18.437J Distributed AlgorithmsHandout 21October 29, 1992Homework Assignment 7Due: Thursday, November 5Exercises1.

Let A be any I/O automaton. Show that there is another I/O automaton B with only asingle partition class that \implements" or \solves" A, in the sense that fairbehs (B ) fairbehs (A).2. Rewrite the Lamport bakery algorithm as an I/O automaton in precondition-eectsnotation.

While doing this, generalize the algorithm slightly by introducing as muchnondeterminism in the order of execution of actions as you can. (The preconditioneects notation makes it easier to express nondeterministic order of actions than doesthe usual ow-of-control notation.)3. (Warning: We haven't entirely worked this one out.) Consider a sequential timestampobject based on the sequential timestamp system discussed informally in class (theone with the 3n; values).

This is an I/O automaton that has a big shared variablelabel containing the latest labels (you can ignore the values) for all processes, and thathas two indivisible actions involving the label vector: (1) An action that indivisiblylooks at the entire label vector, chooses a new label according to the rule based onfull components, and writes it in the label vector. This is all done indivisibly. (2) Anaction that just snaps the entire label vector.1(a) Write this as an IOA.(b) Prove the following invariant: For any cycle, at any level, at most two of threecomponents are occupied.(c) Describe a similar sequential timestamp system based on unbounded real numbertimestamps.(d) Use a possibilities mapping to show that your algorithm of (a) implements youralgorithm of (c).(Plenty of partial credit will be given for good attempts.)3706.852J/18.437J Distributed AlgorithmsHandout 24November 5, 1992Homework Assignment 8Due: Thursday, November 12Exercises1.

Give example executions to show that the multiwriter multireader register implementation given in class (based on a concurrent timestamp object) is not correctly serializedby serialization points placed as follows.(a) For a read: at the point of the embedded snap operation. For a write: at thepoint of the embedded update operation.(b) For all operations: at the point of the embedded snap operation.Note that the embedded snap and update operations are embedded inside the atomicsnapshot out of which the concurrent timestamp object is built.2.