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

Homework 4

Assigned 10/4/05
Due by start of class on 10/11/05


(a) Problem 12.19 from 4th edition (or 11.19 from 3rd edition)

(b) For a synchronous system, design an election algorithm using a
    mutual exclusion algorithm, without knowing how the mutual exclusion
    algorithm is implemented.

(c) In attached figure, assume that the timelines correspond to
    processes P1, P2, P3 and P4 from top to bottom in the figure.
    In each of the two cases below, determine the maximum recoverable
    state. Present your answer in two forms: (i) as a cut drawn on the
    figure, and (ii) in the form of the dependency matrix for the maximum
    recoverable state. Assume that potentially there may be more
    messages sent as the time progresses beyond the maximum time shown
    in the figure.

    (1) Assume that messages A, B, C, D, G and H have been recorded,
        no checkpoints are taken. 

    (2) Assume that messages A, B, C, D, G and H have been recorded,
	and process P1 has taken a checkpoint after event e4, but
        before event e5. No other checkpoints are taken.

    By definition, maximum recoverable state must also be consistent.
    This question will require information from the thesis by Johnson
    (see readings listed on Lectures page).