CPSC 668 Fall 2002, Homework

CPSC 668
Fall 2002
Homework

General Instructions:

Write clearly and legibly -- if you have bad handwriting, then type your solutions. Grading will be based on correctness, clarity, and whether your solution is of the appropriate length.
Justify/explain/prove all your answers, unless otherwise instructed.

Homework 5, due Monday, Dec 9, 2002:

(N) This problem is to fill in some of the gaps in the correctness proof of the algorithm that implements a k-valued (k > 2) single-reader single-writer shared register out of k binary-valued single-reader single-writer shared registers.
1. Prove that the reader will always find a 1 when it scans the array of binary registers.
2. In the corrected proof in the handout, Case 2.2, last sentence, expand on the proof that R will read 1 in B[v''] during its upward scan.
(O) Consider the algorithm for simulating a shared register with a single reader and a single writer on top of message passing in the presence of failures (Alg. 10.6-10.8 in the textbook). Show that the algorithm does not guarantee linearizability with multiple readers -- show an example of two readers that experience a new-old inversion of the values read.
(P) Show that no simulation of single-reader single-writer shared register on top of an asynchronous message passing system is possible if half or more of the processors can crash.
(Q) Prove that there is no wait-free renaming algorithm for n processors with new name space of size n. Follow the ideas used to prove that there is no wait-free algorithm for solving consensus.
** This is the complete assignment. **

Homework 4, due Monday, Nov 18, 2002:

(L) Refer to reference [122] by Gopal and Toueg (available on-line from the ACM Digital Library).
1. What are inconsistency and contamination (in the context of broadcast) and why are they a problem?
2. Describe in your own words an algorithm to implement totally ordered broadcast (what [122] calls atomic broadcast) that prevents inconsistency. Explain briefly why it is correct.
3. Prove Theorem 9 (p. 264 of [122]).
4. Explain informally why the two results mentioned at the end of Section 11 are true.
(M) Consider a shared object (data type) specification with the following property: there exists a sequence rho of operations and two operations op1 and op2, such that (a) op1 and op2 are both instances of the same type op (i.e., the only difference is the parameters), (b) the sequence rho op1 op2 and rho op2 op1 are both legal, and (c) there exists a sequence gamma of operations such that the sequence rho op1 op2 gamma is legal but rho op2 op1 gamma is not legal. The idea is that after the sequence rho, op1 and op2 can be done in either order, but there is a subsequent sequence of operations that can "tell" which order they were done in. For example, let rho be anything, op1 = write(3), op2 = write(4), and gamma = read(4).
1. Prove that in any linearizable implementation of this data type, the worst-case time for op is at least u/2. Assume that at least two processors can perform operations of type op and there is a third processor that can perform the operations in rho and gamma.
2. What, if anything, does this result imply about the worst-case time for linearizable implementations of stacks and queues? Explain your answer.
*** this is the complete assignment ***

Homework 3, due Monday, Oct 28, 2002:

(G) A different validity condition for consensus is: every decision value of a nonfaulty processor is the input of some nonfaulty processor. This problem investigates some of the consequences of using this validity condition instead of the original. You may want to refer to paper [189].
1. Show that the new validity condition is at least as strong as the original one, by showing that any algorithm satisfying the new condition also satisfies the original one.
2. Show that to solve the consensus problem with this new validity condition, when there are n processors and up to f Byzantine failures, n must be greater than max(3,m)*f, where m is the size of the input set.
3. Assuming n is sufficiently large, modify the phase king algorithm to solve the consensus problem with the new validity condition. Prove the correctness of your algorithm.
(H) In the transaction commit problem for distributed databases, each of n processors forms an independent opinion whether to commit or abort a distributed transaction. The processors must come to a consistent decision such that if even one processor's opinion is to abort, then the transaction is aborted, and if all processors' opinions are to commit, then the transaction is committed. This problem explores whether this problem is solvable in asynchronous systems with crash failures.
1. Show that there is no wait-free solution in a shared memory system. Hint: The interesting part is to show the existence of a bivalent initial configuration.
2. Prove whether or not there a 1-resilient solution in shared memory.
3. What happens in message passing?
(I) A variation on the consensus problem with Byzantine failures is often called the Byzantine general's problem: there is one distinguished processor, the "general", and the rest are the "lieutenants". The conditions to be satisfied are
- Termination: Every nonfaulty lieutenant must eventually decide.
- Agreement: All nonfaulty lieutenants must have the same decision.
- Validity: If the general is nonfaulty, then the common nonfaulty decision value is the general's input.
In the synchronous message passing case (with Byzantine failures), show how to transform a solution to the consensus problem into a solution for the Byzantine general's problem, and vice versa. What are the message and round overhead of your transformations?
(J) Recall that <>P (diamond P, the eventually perfect failure detector) guarantees that eventually each processor's suspected list contains exactly the faulty processors.
Consider the following fault-tolerant leader election problem (for a general network, not just a ring): there exists a nonfaulty processor L such that eventually every nonfaulty processor p identifies L as its leader.
Can you use diamond-P to solve the fault-tolerant leader election problem? Can you use a solution to the fault-tolerant leader election problem to implement diamond-P? Either give algorithms or give impossibility proofs. Assume a message passing system with crash failures.
(K) Consider a failure-free fully connected network (clique) in which message delays are within the range [d-u,d], and hardware clocks are rho-bounded as defined in class. Come up with the best upper and lower bounds on the skew achievable by a clock synchronization algorithm in this case. If you need to make any simplifying assumptions, be sure to state them.

Homework 2, due Friday, Oct 4, 2002:

(D) Consider the problem of measuring the running time of asynchronous shared memory algorithms.
1. Explain why it wouldn't be very informative to count the number of steps taken by the processes.
2. Suggest a method that is analogous to the definition for time complexity for asynchronous message passing algorithms.
3. Using your method from part (2), calculate how long a processor waits, in the worst case, since entering the entry section until entering the critical section for Algorithm 4.6 (tournament algorithm in the handout and on slide 81). Assume each execution of the critical section takes at most one time unit. You may want to set up your function as a recurrence relation whose argument is the current tree level.
4. Literature Search: Find a recent paper on adaptive shared memory mutual exclusion algorithms and explain what time complexity measure is used in it. Compare and contrast this measure with that in part (2).
(E) This problem concerns Lamport's fast mutual exclusion algorithm (slide 92).
1. Prove the rest of the cases for showing it satisfies mutual exclusion.
2. Prove that it satisfies no-deadlock.
3. Prove that it does not satisfy no-lockout (give an execution that violates no-lockout).
4. Show that it is not adaptive, by showing an execution with two contending processors in which they must access Theta(n) shared variables to enter the critical section.
(F) Design a consensus algorithm for crash failures with the early stopping property: if f' processors fail in an execution, then the algorithm terminates in O(f') rounds. In other words, when f' is significantly smaller than f, the algorithm does not need to run for f+1 rounds, instead it runs for a smaller number of rounds that is approximately f'. Hint: Processors may decide in different rounds.

Homework 1, due Friday, Sep 13, 2002:

(A) Code the algorithm on slide 24 (DFS spanning tree with known root) using the formal model presented in class, with each node represented as a state machine. Be sure to indicate the initial and terminated states, as well as all the transitions, for each node.
Explain why the message and time complexities are O(m). Are they the same in the synchronous and asynchronous cases?
(B) Literature Search: What is the best known algorithm for leader election in a ring? Here, "best" means the smallest message complexity, taking into account constant factors. Give the reference to the paper that you find with the best algorithm and give a *brief* summary (in your own words of course!) of the algorithm and its analysis.
(C) Consider an anonymous ring where processors start with binary inputs.
1. Prove there is no uniform synchronous algorithm for computing the AND of the input bits. Hint: Assume for contradiction there is such an algorithm and consider the execution on a ring of size n with all inputs 1; then embed this ring in a much larger ring with a single 0.
2. Describe an asynchronous non-uniform algorithm for computing the AND of the input bits that sends O(n^2) messages in the worst case. Explain why it is correct and has the required message complexity.
3. Prove that Omega(n^2) is a lower bound on the message complexity of any asynchronous algorithm that computes the AND.
4. Describe a synchronous algorithm for compouting the AND that sends O(n) messages in the worst case. Explain why it is correct and has the required message complexity.