CSE 223a Winter 2004
Homework 1
Due January 16, 2004

Please submit your answers by 2pm on January 16 via e-mail to marzullo@cs.ucsd.edu. Use as a subject line your name and that the message is a solution to this homework (e.g., Paolo Rossi CSE223a Homework 1 solutions).
  1. A threshold model for failures assumes that, given n components, no more than t can fail. The threshold t is usually bounded from above by a fraction of n. For example, a voter that takes n inputs and returns the majority value masks faulty inputs when n > 2t. The avalability of such a system is the probability that t or less of the components can fail.
Assume a system that has n processes and that can tolerate t faulty processes where n > kt. The processes have identical probabilities p of failing and they fail independently. Show that, for some values of k and n, the availability decreases when n in increased by one. That is, the availibility of the system can become worse by increasing the replication.
  1. Consider the Chandy/Lamport snapshot algorithm. Suppose that, once a process records its local state and the channel states, it appends these recorded values to a log on local disk rather than sending them back to the originating snapshot process.
Describe what happens when (a) two processes p1 and p2 concurrently start a snapshot and (b)  process p2 starts a snapshot causally after process p1 starts a snapshot.
  1. Given two consistent cuts c1 and c2, we will define c1 » c2 to mean that there is an event e1 in c1 and an event e2 in c2 such that e1 --> e2, and there is no event f1 in c1 and  f2 in c2 such that f2 is not in c1 and f2 --> f1.
Given an event e, consider all of the consistent cuts F(e) that contain e. Show that F(e) contains a maximal and a minimal element with respect to ». Using vector clocks, give a characterization of the minimal and maximal cuts of F(e).

You can assume that each process starts off by executing an initial event and that the history is finite.