304 C. DWORK ET AL. (c) For the unauthenticated Byzantine fault model, if N 2 3t + 1, then Algo- rithm 3’ achieves consistency, strong unanimity, and termination for an arbitrary value domain. It is easy to see that Algorithms 1’ and 2’ guarantee that decisions are reached by all correct processors within time 4(N + l)(N + A) after GST. The corresponding bound for Algorithm 3’ is 6(N + l)(N + A). Thus, the time for Algorithms l’-3’ is bounded above by GST plus a polynomial in N and A. Remark 1 at the end of Section 3 shows how these time bounds can be improved. As mentioned in the Introduction, these bounds also give the time after GST when A can stop holding again. 4.2 UPPER BOUNDS FOR DELTA UNKNOWN. Now we consider the model in which delta is unknown. Fix any of the four possible fault models. We show that, if there is a t-resilient protocol in the basic model, then there is one in the model in which delta is unknown. Let algorithm A work for the basic model. As before, we define A ’ from A so that every execution of A ’ is a simulation of an execution ofA. Let R, = N + r. Each processor in A’ divides its steps into groups so that its rth group contains exactly R, steps. As before, the processor uses each group to simulate its own actions in a single round of algorithm A. Thus, the processor uses the first N steps of group r to send its round r messages to the N processors, one processor at a time, and uses the last r steps to perform Receive operations. The round r state transition is simulated at the last step of group r. Again, each processor always attaches a round identifier (number) to messages, and any message sent during a round r that arrives late during some round r’ > r is ignored. Now consider any run e’ of A ‘, and assume that the communication bound A holds in e’. As before, it is easy to define a corresponding run e of A. The number of steps in e’ that are allotted for the simulation of any round r 2 A is sufficient to allow all messages that are sent during round r to get received. Thus, e is an allowable run of A (with A as its GST round). Since A is assumed to be a t-resilient consensus protocol for the basic model, consensus is eventually reached in e, and so in e’, as needed. By applying this transformation to Algorithms l-3, we obtain Algorithms 12-32, respectively, and immediately obtain the following result: THEOREM 4.2. In the model in which processors are completely synchronous (a = 1) and communication is partially synchronous (delta is unknown), claims (a)-(c) of Theorem 4.1 hold for Algorithms 1 2-32, respectively. We now bound the time required by Algorithms 12-32. Consider Algorithm 12, for example, and fix any execution e with corresponding message bound A. Then round A is the GST for the execution of Algorithm 1 simulated by e. It requires at most time A(N + A) for processors to complete their simulations of the first A rounds of Algorithm 1 (A rounds, with N + A as the maximum time to simulate a single round). Then an additional 4(N + 1) rounds, at most, must be simulated. These additional rounds require at most time 4(N + l)(N + A + 4(N + l)), where the term (N + A + 4(N + 1)) represents the maximum time to simulate one of these rounds (the last and largest one). Thus the total time is bounded by A(N + A) + 4(N + l)(N + A + 4(N + I)), or O(N2 + A’). The same bound holds for Algorithm 22. The corresponding bound for Algorithm 32 is A(N + A) + 6(N + l)(N + A + 6(N + 1)). Thus the time for Algorithms 12-32 is bounded above