ECE 428/CS 425/CSE 424 (Fall 2005)
Distributed Systems

Homework 2

Assigned 9/13/05
Due by start of class on 9/20/05  (extended to 9/22/05)


(a) This question is related to sections 11.3.1 and 11.3.2 of 4th
    edition (or 10.3.1 and 10.3.2 of 3rd edition). As noted, the
    optimum bound that can be achieved on clock skew when synchronizing
    N clocks is u(1-1/N). While this may be the optimum bound, in an
    actual execution of a clock synchronization, fortuitously, the actual
    clock skew may turn out to be smaller. 

    Consider the clock synchronization algorithm below for N processors,
    each with its own hardware clock. Construct a scenario for N = 2
    such that the actual skew at the end of the algorithm matches the above
    bound. If such a scenario cannot be constructed, explain why.

    Code below is to be performed at the i-th processor Pi, 0 <= i <= N-1.
    HC denotes the hardware clock at the processor executing the code.
    d denotes the worst-case message delay, and u is the uncertainty in the
    message delay.

	initially diff[i] = sum = 0;

	At first computation step,
		send own hardware clock HC value to all other processors

	Upon receiving message containing clock value T from some Pj:
	{
		diff[j] = T + d - u/2 - HC   
		sum = sum + diff[j]
		if a message has been received from every other processor
		then
			adj = sum / N
	}
	adjusted software clock = HC + adj


	(Suggested exercise: Try the above problem with N = 3.)


(b) Consider the attached figure. Let us name the processes as P1, P2
    P3 and P4, from top to bottom. If process P4 in this figure
    initiates the Chandy-Lamport snapshot algorithm after event e14, but
    before event e15, what are the latest times at which each of the
    remaining processes may save their state? Assume that there are no
    application messages beyond those shown in the figure.

(c) Consider the following two consensus algorithms for N processes.
    Assume that at most a single process may fail anytime during
    the execution of the algorithms.

	(i) Algorithm I

		Each process sends its value to all other processes;
		Each process waits for time duration T (say, 1 hour);
		Each process decides on the majority of values received
			during the T time duration (including its own value)

 
	(ii) Algorithm II

		Each process Pi sends its value to all other processes
		After receiving a value from at least N-1 process,
			 process Pi decides on the plurality value
			 among the received values, ties being broken
			 in favor of the largest value  

	
     For each of the above algorithms, state whether the algorithm
     can achieve consensus in an asynchronous distributed system.
     If you answer no, construct a scenario in which either the processes
     decide on different values, or the algorithm does not terminate.