Consensus in the Presence of Partial Synchrony 291 TABLE I. SMALLEST NUMBER OF PROCESSORS Nmi. FOR WHICH A I-RimxiT CONSENSUS PROTOCOL EXISTS Partially syn- Partially syn- Partially syn- chronous pro- chronous com- chronous cessors and munication and communica- synchronous Failure type Syn- Asyn- synchronous tion and pro- communica- chronous chronous processors cessors tion Fail-stop t Ca 2t-k 1 2t+ 1 t Omission t m 2t+ 1 2t+ 1 [2t, 2t + l] Authenticated Byzantine t m 3t+ 1 3t+ 1 2t+ 1 Byzantine 3t+1 m 3t+ 1 3t+ 1 3t+ 1 cation, we show that t-resilient consensus is possible iff N 2 3t + 1. (The “only if” direction in this case follows immediately from the result for the completely synchronous case in [ 151.) For all four types of faults, the time required for all correct processors to reach consensus is (1) a polynomial in N and A, for the model in which A is unknown; and (2) GST plus a polynomial in N and A, for the GST model. All of our protocols that reach consensus within time polynomial in parameters such as iV, A, and GST also have the property that the total number of message bits sent is also bounded above by a polynomial in the same parameters. Table I shows the maximum resiliency in various cases and compares our results with previous work. The results where communication is partially synchronous and processors are synchronous are shown in column 3 of the table; the results in columns 4 and 5 will be explained shortly. In each case, the table gives Nmin, the smallest value of N (N L 2) for which there is a t-resilient protocol (t > 1). (Some of the lower bounds on Nmin in the last column of the table have slightly stronger constraints on t and N, which are given in the formal statements of the theorems.) Results in the synchronous column are due to [3], [5], and [ 151, and those in the asynchronous column are due to [4] and [lo]. The table entry that is the closed interval [2t, 2t + I] means that 2t 5 iVmin 5 2t + 1. It is interesting to note that, for fail-stop, omission, and Byzantine faults with authentication, the maximum resiliency for partially synchronous communication lies strictly between the maximum resiliency for the synchronous and asynchronous cases. It is also interesting to note that, for partially synchronous communication, authentication does not improve resiliency. Our protocols use variations on a common method: A processor p tries to get other processors to change to some value v that p has found to be “acceptable”; p decides v if it receives sufficiently many acknowledgments from others that they have changed their value to v, so that a value different from v will never be found acceptable at a later time. Similar methods have already appeared in the literature (e.g., see [2], [ 191). Reischuk [ 171 and Pinter [ 161 have also obtained consensus results that treat message and processor faults separately. 1.3 PARTIALLY SYNCHRONOUS COMMUNICATION AND PROCESSORS. It is easy to extend the models described in Section 1.2 to allow processors, as well as com- munication, to be partially synchronous. That is, + (the upper bound on relative processor speed) can exist but be unknown, or 9 can be known but actually hold only from some time GST onward. We obtain results that completely characterize the resiliency in cases in which both communication and processors are par- tially synchronous, for all four classes of faults. In such cases we assume that