Consensus in the Presence of Partial Synchrony 305 by a polynomial in N and A. Again, these bounds can be improved using the ideas in Remark 1 at the end of Section 3. Remark 2. If we strengthen the model where delta holds eventually to require that no messages are ever lost, but that messages sent before GST can arrive late, then we can modify Algorithms l ’-3’ to allow processors to terminate. Specifically, we use the ideas described in Remark 1 at the end of Section 3. In the present case, however, each processor need only broadcast a single “Decide v” message, at the time when it decides v. This message is not tagged with a round number, and other processors should accept a “Decide v” message at any time. For fail-stop or omission faults, a processor can stop participating in the algorithm immediately after it broadcasts its “Decide v” message. Further, it can decide v immediately after receiving a “Decide v” message. For Byzantine faults, a processor can decide v after receiving t + 1 “Decide v” messages, but it cannot stop participating in the algorithm until after it has broadcast its “Decide v” message and received “Decide v” messages from a total of 2t + 1 processors. If messages can be lost before GST, it is not hard to argue that, in any consensus protocol resilient to one fail-stop fault, there is some execution in which at least one correct processor must continue sending messages forever. The argument is similar to those for Theorems 4.3 and 4.4 in the next subsection. All that is needed to ensure halting in practice, however, is that each correct processor be able to reliably deliver a “Decide v” message to every other correct processor; in the absence of network partition, this could be done by repeated sending. Remark 3. All the results of this section have assumed 9 = 1. If processors are synchronous with + > 1 and communication is partially synchronous, we would hope to obtain the same results. We show that this extension holds by proving a more general set of results: In Section 5 we show that the resiliency achieved by the protocols of this section can also be achieved if both processors and commu- nication are partially synchronous. These stronger results imply that the same resiliency is achievable if communication is partially synchronous and processors are synchronous with @ > 1. 4.3 LOWER BOUNDS. In this section we give our lower bound results for partially synchronous communication and completely synchronous processors. The first lower bound shows that the resiliency of Theorems 4.1 and 4.2, part (a), cannot be improved, even for weak unanimity and a binary value domain. THEOREM 4.3. Assume the model with fail-stop or omission faults, where the processors are synchronous and communication is partially synchronous (either delta holds eventually or delta is unknown). Assume 2 5 N I 2t. Then there is no t-resilient consensus protocol that achieves weak unanimity for binary values. PROOF. The proof is the same for both definitions of partially synchronous communication. Assume the contrary, that there is an algorithm immune to fail- stop faults satisfying the required properties. We shall derive a contradiction. Divide the processors into two groups, P and Q, each with at least 1 and at most t processors. First consider the following Scenario A: All initial values are 0, the processors in Q are initially dead, and all messages sent from processors in P to processors in P are delivered in exactly time 1. By t-resiliency, the processors in P must reach a decision; say that this occurs within time TA. The decision must be 0. For if it were 1, we could modify the scenario to one in which the processors in Q are alive but all messages sent from Q to P take more than time TA to be