Consensus in the Presence of Partial Synchrony 297 PROOF. In order for two values v and w to acquire a lock at trying phase k, the processor to which phase k belongs must send conflicting (lock v, k) and (lock w, k) messages, which it will never do in this fault model. Cl LEMMA 3.2. Suppose that some processor decides v at phase k, and k is the smallest numbered phase at which a decision is made. Then at least t + 1 processors lock v at phase k. Moreover, each of the 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. It is clear that at least t + 1 processors lock v at phase k. Assume that the second conclusion is false. Then let 1 be the first phase at which one of the locks on v set at phase k is released without immediately being replaced by another, higher numbered lock on v. In this case the lock is released during lock-release phase 1, when it is learned that some processor has a lock on some w # v with associated phase h, where k 5 h I 1. Lemma 3.1 implies that no processor has a lock on any w # v with associated phase k. Therefore, some processor has a lock on w with associated phase h, where k < h 5 1. Thus, it must be that w is found acceptable to at least N - t processors at the first round of some phase numbered h, k c h 5 1, which means that at least N - t processors do not have v locked at the beginning of that phase. Since t + 1 processors have v locked at least through the first round of 1, this is impossible. Cl LEMMA 3.3. 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. 0 THEOREM 3.1. Assume the basic model with fail-stop or omission faults. Assume N 2 2t f 1. Then Algorithm 1 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 phase k, and this is the smallest numbered phase at which a decision is made. Then Lemma 3.2 implies that, at all times after phase k, at least t + 1 processors have v locked. Consequently, at no later phase can any value other than v ever be acceptable to N - t processors, so no processor will ever decide any value other than v. Next, we argue strong unanimity. If all the initial values are v, then v is the only value that is ever in the PROPER set of any processor. Thus, v is the only possible decision value. Finally, we 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 round GST. We claim that processor pi will reach a decision at trying phase k (if it has not done so already). By Lemma 3.3, 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 sufficient communication has occurred by the beginning of trying phase k so that v is in the PROPER set of each correct processor. Moreover, any initial value of a correct processor is in the PROPER set of each correct processor at the beginning of trying phase k. Since there are at least N - t 2 t + 1 correct processors, 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. Cl