Consensus in the Presence of Partial Synchrony 299 E’(lock w, h ‘, proof’) with w # v and h ’ 2 h, then the processor releases its lock on v. LEMMA 3.4. It is impossible for two distinct values to acquire valid locks at the same trying phase if that phase belongs to a correct processor. PROOF. In order for different values v and w to acquire valid locks at trying phase k, the processor pi to which phase k belongs must send conflicting Ei(lOck v, k, proof) and Ei(lock w, k, proof’) messages, which correct processors can never do. 0 LEMMA 3.5. 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. Assuming that the second conclusion is false, the remaining proof by contradic- tion is identical to the proof of Lemma 3.2. Cl LEMMA 3.6. 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. Cl THEOREM 3.2. Assume the basic model with Byzantine faults and authentica- tion. Assume N r 3t + 1. Then Algorithm 2 achieves consistency, strong unanimity, and termination for an arbitrary value domain. PROOF. The proofs of consistency and strong unanimity are as in the proof of Theorem 3.1. To argue termination, consider any trying phase k belonging to a correct processor pi that is executed after a lock-release phase, both occurring at or after GST. We claim that processor pi will reach a decision at trying phase k (if it has not done so already). By Lemma 3.6, there is at most one value locked by correct processors at the start of trying phase k. If there is such a locked value v, then v was found to be proper to at least N - t processors, of which N - 2t L t + 1 must be correct. Therefore, by the beginning of trying phase k, these t + 1 correct processors have communicated to all correct processors that v is proper, so by the way the set PROPER is augmented every correct processor will have v in its PROPER set by the beginning of trying phase k. Next, consider the case in which no value is locked at the beginning of trying phase k (so all values are acceptable). If there are at least t + 1 correct processors with the same initial value v, then v is in the PROPER set of each correct processor at the beginning of trying phase k. On the other hand, if this is not the case, then all values in the value set are in the PROPER set of all correct processors at the beginning of trying phase k. It follows that a proper, acceptable value will be found for processor pi to propose, and that the proposed value will be decided on by processor pi at trying phase k. 0 As in the previous case, GST + 4(N + 1) is an upper bound on the number of rounds required for all the correct processors to reach decisions. 3.2.3 Byzantine Faults without Authentication. In this section we modify Al- gorithm 2 to handle Byzantine faults without authentication, while maintaining the same requirement, N 2 3 t + 1, on the number of processors and maintaining