292 C. DWORK ET AL. communication and processors possess the same type of partial synchrony; that is, either both @ and A are unknown, or both hold from some time GST on. Surprisingly, the bounds we obtain are exactly the same as for the case in which communication alone is partially synchronous; see column 4 of Table I. (The only difference is that in this case the polynomial bounds on time depend on N, A, and a.) In the earlier case the fact that @ was equal to 1 implied that each processor could maintain a local time that was guaranteed to be perfectly synchronized with the local times of other processors. In this case no such notion of time is available. We give two new protocols allowing processors to simulate distributed clocks. (These are fault-tolerant variations on the clock used by Lamport in [ 131.) One uses 2t + 1 processors and tolerates t fail-stop, omission, or authenticated Byzantine faults, while the other uses 3t + 1 processors and tolerates t unauthenticated Byzantine faults. When the appropriate clock is combined with each of our protocols for the case where only communication is partially synchronous, the result is a new protocol for the case in which both communication and processors are partially synchronous. 1.4 PARTIALLY SYNCHRONOUS PROCESSORS. In analogy to our treatment of partial communication synchrony, it is easy to define models where processors are partially synchronous and communication is synchronous (A exists and is known a priori). The last column of Table I summarizes our results for this case. Once again, time is polynomial (this time in N, A and @). The basic strategy used in constructing the protocols for this case also involves combining a consensus protocol that assumes processor synchrony with a distributed clock protocol. For fail-stop faults and Byzantine faults with authentication, either the distributed clock or the consensus protocol can tolerate more failures than the corresponding clock or consensus protocol used for the case in which both communication and processors are partially synchronous, so we obtain better resiliencies. Technical Remarks (1) Our protocols assume that an atomic step of a processor is either to receive messages or to send a message to a single processor, but not both; there is neither an atomic receive/send operation nor an atomic broadcast operation. We adopt this rather weak definition of a processor’s atomic step in this paper because it is realistic in practice and seems consistent with assumptions made in much of the previous work on distributed agreement. However, our lower bound arguments are still valid if a processor can receive messages and broadcast a message to all processors in a single atomic step. (2) The strong unanimity condition requires that, if all initial values are the same, say v, then v must be the common decision. Weak unanimity requires this condition to hold only if no processor is faulty. Unless noted otherwise, our consensus protocols achieve strong unanimity, and our lower bounds hold even for weak unanimity. In the case, however, of Byzantine faults with authentication and partially synchronous processors, the upper bound 2t + 1 in the last column of Table I holds for strong unanimity only if the initial values are signed by a distinguished “sender.” This assumption is also used in the algorithm of [3] for the completely synchronous case. (For weak unanimity, the upper bound 2t + 1 in the last column holds even without signed initial values.) We discuss this further in Section 6, which is the first place where the issue of whether the initial values are signed has any effect on our results. (3) Our consensus protocols are designed for an arbitrary value domain V, whereas our lower bounds hold even for the case 1 Vl = 2.