CSE 223a Fall 2004
Homework 2
Due 1 November, 2004

Please submit your answers by the beginning of class (6:30 pm) on Monday, 1 November 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., CSE223a Homework 2 solutions Ivan Ivanov).
  1. This problems is concerned with voting on inputs that are sensor values.

    Consider a sensor reading that is an interval [min, max] where min is less than or equal to max. If the sensor reading is accurate, then the actual physical value is some value between min and max. The precision of the sensor reading is max - min. For example, let [18, 20] and [17.5, 18.5] be two temperature readings. Assume that the actual temperature is 19.5. The second reading is more precise than the first, but only the first reading is accurate.

    Assume that you have n independent sensor readings, all taken at the same time. You know that no more than t of them can be inaccurate. That is, at least n- t of the readings are accurate. You are not told, however, which readings are accurate. Give an algorithm that computes an accurate sensor reading from this set of n sensor readings. The reading you compute should be as precise as possible. It should also be the case (which you should prove of your algorithm) that if n > 2t, then the precision of the result is as least as precise as the least precise input.

  2. The following is written in Fred B. Schneider's State Machine Approach paper:

    ... If processors experience only failstop failures, then an ensemble containing t + 1 replicas suffices, and the output of the ensemble can be the output produced by any of its members.

    Argue that for this statement to be true, a uniform failstop agreement protocol is needed to disseminate the commands to the state machine. If (nonuniform) failstop agreement is used instead, what should the output of the ensemble be as a function of the outputs of the members? The points you receive will depend on the degree of repliation you require; having n closer to t is better.