302 C. DWORK ET AL. round or earlier, a valid lock on w with associated phase h ‘, and if w # v and h ’ 2 h, then q releases its lock on v. LEMMA 3.7. It is impossible for correct processors to accept valid locks on two distinct values with associated phase k tfphase k belongs to a correct processor. PROOF. Suppose that the lemma is false. By the Unforgeability property, the processor pi to which phase k belongs must BROADCAST conflicting (lock v, k) and (lock w, k) messages, which correct processors can never do. Cl LEMMA 3.8. Suppose that some correct processor decides v at phase k, and k is the smallest numbered phase at which a decision is made by a correct processor. Then at least t + 1 correct processors lock v at phase k. Moreover, each of the correct processors that locks v at phase k will, from that time onward, always have a lock on v with associated phase number at least k. PROOF. Since at least 2t + 1 processors send an acknowledgment that they locked v at phase k, it is clear that at least t + 1 correct processors lock v at phase k. The rest of the proof is similar to the proofs of Lemmas 3.2 and 3.5, using the Unforgeability property to argue that, if a correct processor q accepts a valid lock on value w # v with associated phase h, then w is found acceptable to all but at most t of the correct processors at the first round of phase h. 0 LEMMA 3.9. Immediately after any lock-release phase that occurs at or after GST, the set of values locked by correct processors contains at most one value. PROOF. Straightforward from the lock-release rule and the Relay property. Cl THEOREM 3.3. Assume the basic model with Byzantine faults without authen- tication. Assume N 2 3t + 1. Then Algorithm 3 achieves consistency, strong unanimity, and termination for an arbitrary value domain. PROOF. The proof is virtually identical to the proof of Theorem 3.2, using the Correctness and Relay properties after GST to argue termination. 0 An upper bound on the number of rounds required is GST + 6(N + 1). Remark 1. Algorithms l-3 have the property that all correct processors make a decision within O(N) rounds after GST. The time to reach agreement after GST can be improved to O(t) rounds by some simple modifications. The bound O(t) is optimal to within a constant factor, since t + 1 rounds are necessary even if communication and processors are both synchronous and failures are fail-stop [7, 91. A modification to all the algorithms is to have a processor repeatedly broadcast the message “Decide v” after it decides v. For Algorithm 1 (fail-stop and omission faults), a processor can decide v when it receives any “Decide v” message. For Algorithms 2 and 3 (Byzantine faults), a processor can decide v when it receives t + 1 “Decide v” messages from different sources. Easy arguments show that the modified algorithms are still correct and that all correct processors make a decision within O(t) rounds after GST; these arguments are left to the reader. 4. Partially Synchronous Communication and Synchronous Processors In this section we assume that processors are completely synchronous (a = 1) and communication is partially synchronous. We show how to use these models to simulate the basic model of Section 3.1 and thus to solve the same consensus problem.