296 C. DWORK ET AI,. algorithm. If only weak unanimity is desired, the PROPER sets are not needed, and the protocols can be simplified somewhat; we leave these simplifications to the interested reader. 3.2.1 Fail-Stop and Omission Faults. The first algorithm is used for either fail-stop or omission faults. It achieves strong unanimity for an arbitrary value domain V. Algorithm 1. N 2 2t + 1 Initially, each processor’s set PROPER contains just its own initial value. Each processor attaches its current value of PROPER to every message that it sends. Whenever a processor p receives a PROPER set from another processor that contains a particular value v, then p puts v into its own PROPER set. It is easy to check that each PROPER set always contains only proper values. The rounds are organized into alternating trying and lock-release phases, where each trying phase consists of three rounds and each lock-release phase consists of one round. Each pair of corresponding phases is assigned an integer, starting with 1. We say that phase h belongs to processor pi if h = i(mod N). At various times during the algorithm, a processor may lock a value v. A phase number is associated with every lock. If p locks v with associated phase number k = i mod N, it means that p thinks that processor pi might decide v at phase k. Processor p only releases a lock if it learns its supposition was false. A value v is acceptable to p if p does not have a lock on any value except possibly v. Initially, no value is locked. We now describe the processing during a particular trying phase k. Let s = 4k - 3 be the number of the first round in phase k, and assume k = i mod N. At round s each processor (including pi) sends a list of all its acceptable values that are also in its proper set to processor pi (in the form of a (list, k) message). (If V is very large, it is more efficient to send a list of proper values and a list of unacceptable values. Given these lists, the proper acceptable values are easily deduced.) Just after round s, that is, during the computation subround between rounds s and s + 1, processor pi attempts to choose a value to propose. In order for processor pi to propose v, it must have heard that at least N - t processors (possibly including itself) find value v acceptable and proper at the beginning of phase k. There might be more than one possible value that processor pi might propose; in this case processor pi will choose one arbitrarily. Processor pi then broadcasts a message (lock v, k) at round s + 1. If any processor receives a (lock v, k) message at round s + 1, it locks v, associating the phase number k with the lock, and sends an acknowledgment to processor pi (in the form of an (ack, k) message), at round s + 2. In this case any earlier lock on v is released. (Any locks on other values are not released at this time.) If processor pi receives acknowledgments from at least t + 1 processors at round s + 2, then processor pi decides v. After deciding v, processor pi continues to participate in the algorithm. Lock-release phase k occurs at round s + 3 = 4k. At round s + 3, each processor p broadcasts the message (v, h) for all v and h such that p has a lock on v with associated phase h. If any processor has a lock on some value v with associated phase h, and receives a message (w, h ‘) with w # v and h ’ 2 h, then the processor releases its lock on v. LEMMA 3.1. It is impossible for two distinct values to acquire locks with the same associated phase.