C. DWORK ET AL. 316 THEOREM 6.1. Assume the basic model with signals, with fail-stop faults. Assume N L t. Then Algorithm 4 achieves consistency, strong unanimity, and termination for an arbitrary value domain. PROOF. First, we show consistency. Suppose that some correct processor pi decides v at round k, and this is the smallest numbered round at which a decision is made. Then Lemma 6.1 implies that no message containing value w # v is ever sent at any round 2 k. But a processor can decide on a value w only if it first sends out messages containing w. Therefore, no processor ever decides on a value w # v. Strong unanimity is obvious, since a message with contents v is only sent if v was the initial value of some processor. Since a signal is received by each correct processor at every round on or after GST, by definition of the basic model with signals, it is obvious that each round on or after GST results in a decision for its owner if that owner has not already decided. 0 6.1.2 Authenticated Byzantine Faults. The next algorithm, Algorithm 5, achieves weak unanimity for an arbitrary value domain. Algorithm 5. N 2 2t + 1 The protocol is similar to Algorithm 2 of Section 3.2.2, with a few changes as indicated below. Because we are only dealing with weak unanimity, the PROPER sets are not used. This time, the rounds are divided into trying phases of two rounds each and lock-release phases of one round each. A trying phase of Algorithm 5 is the same as the first two rounds of the corresponding trying phase of Algorithm 2, except that, if a processor, during one of its trying phases, is choosing a value to propose and if several values are acceptable, the processor chooses its own initial value if that value is acceptable or chooses arbitrarily otherwise. The third round is omitted; processor pi does not wait for messages from others claiming that they have responded to a message Ei(lock v, k, proof) by locking v. Instead, it checks that a signal has been received at the second round of the trying phase. If a signal is received, then processor pi decides v. In Algorithm 2, processor pi needed at least 2t + 1 acknowledgment messages to conclude that at least t + 1 correct processors actually locked v at phase k. Now we can argue that, if a signal is received, then all correct processors will have actually locked v at phase k, and since N 2 2t + 1, there are at least t + 1 correct processors. The proof of the following theorem is very similar to that of Theorem 3.2 (the result about Algorithm 2), and details are left to the reader. THEOREM 6.2. Assume the basic model with signals, with authenticated Byzan- tine faults. Assume N 2 2t + 1. Then Algorithm 5 achieves consistency, weak unanimity, and termination for an arbitrary value domain. One version of the consensus problem studied in the literature supposes that a distinguished processor, called the “general,” gives the initial values vi to all processors. In the case of Byzantine faults with authentication, it is usually assumed that the general signs these initial values with its own unforgeable signature. Thus, if the general is correct, there is a single value v such that the general gives a signed v to every processor; in this case, strong unanimity requires that v is the value decided by all correct processors. If the general is faulty, the general can give out different values and can even give two different values, both signed, to the same processor; in this case, strong unanimity does not require any particular value to