Consensus in the Presence of Partial Synchrony 321 Consider Scenario CP, where the processors in P U (b) have initial values 0, wake up at time 1, and run fast in the interval [ 1, m), and where the other processors are initially dead. By t-resiliency, the processors in P make some decision within some finite time Tp. We claim the decision must be 0. For if it were 1, we could modify the scenario to one in which all initial values are 0, and the processors in Q U (r-1 are correct but do not wake up until after time Tp. The processors in P still decide 1 in the modified scenario, which contradicts weak unanimity. Consider the analogous Scenario CQ where the processors in P U (r) are initially dead, and the processors in Q U lb] wake up at time 1 with initial values 1 and run fast in the interval [ 1, m). Therefore, the processors in Q decide 1 after some finite time TQ. Consider the following Scenario BP: Processors in P U (6) are Byzantine. The processors in P have value 0, and b has both 0 and 1 (so the general is Byzantine). They wake up at time 1, with b acting as if its value is 0, and they run fast in the interval [ 1, Tp]. They send the same messages to r as are sent in Scenario CP, but no messages are sent to Q. After time Tp, the processors in P die. The processors in Q are correct. They wake up at time Tp + 1 and run fast thereafter. Starting at time Tp + 1, the Byzantine processor b starts behaving toward Q and r excactly as it does in Scenario CQ, as if its value were 1, except that a message sent at real time s in Scenario CQ is sent at time Tp + s in Scenario BP. Since Q has received no messages from P, the processors in Q decide 1 at time Tp + TQ, and they all behave exactly as in Scenario CQ, except that everything happens Tp real- time steps later. At time Tp + TQ + 1, the correct processor r wakes up and runs fast thereafter. The initial value of r is irrelevant. Note that at most t processors are faulty in this run. In the model where phi is unknown, the processor bound + = Tp + TQ + 1 holds in this run; in the model where phi holds eventually, the processor bound @J = 1 holds after GST = Tp + TQ + 1. Since the correct processors in Q have already decided 1 before r wakes up, r must decide 1 at some real time T,. Consider now Scenario BQ: The processors in P are correct and begin with value 0. They run fast in the interval [ 1, Tp] but take no more steps until after time T,. In the time interval [ 1, Tp], the Byzantine processor b behaves toward P and r exactly as it does in Scenario CP, acting as if it had initial value 0. Therefore, at time Tp the processors in P decide 0. The processors in Q are Byzantine. They wake up at time Tp + 1 with value 1 and behave with respect to r exactly as they do in Scenario BP; that is, the messages that have been sent from P to Q during the interval [ 1, Tp] are ignored by Q. At time Tp + 1, b starts acting toward r exactly as it does in Scenario BP, as if it had initial value 1. The correct processor r wakes up at time Tp + TQ + 1 and runs fast thereafter. It is easy to see that the messages received by r between time Tp + TQ + 1 and time T, are exactly the same in Scenario BQ as in Scenario BP. Therefore, r decides 1 at time T,, which is a contradiction because the correct processors in P decided 0. Cl In the preceding proof, note that the processors in P and Q exhibit only omission faults: P fails to send messages to Q in Scenario BP, and Q fails to receive messages from Pin Scenario BQ. Processor b is the only one that exhibits Byzantine behavior stronger than omission faults. Therefore, it can be checked that the same proof can be carried out for omission faults with three groups of processors, P, Q, and (r-1, where P and Q each contain at least 1 and at most t - 1 processors. This proves the following, which shows that the resiliency of Theorems 5.1 and 5.2, part (a), when applied to the case of omission faults and partially synchronous processors, cannot be improved by more than 1.