Consensus in the Presence of Partial Synchrony 317 be the decision value. This issue was not raised earlier because it is irrelevant to the results of Sections 3-5; that is, our protocols for the authenticated Byzantine case are designed to work even if the general does not sign the initial values, and our lower bound Theorem 4.4 is still valid if the general does sign the initial values. (If the general does sign the initial values, updating to the PROPER sets in Algorithm 2 can be simplified.) This distinction is important in the completely synchronous case: N-resilient strong unanimity is possible in the authenticated Byzantine case (column 1, row 3 of Table I) only if the general signs the initial values. This distinction also matters in this section of the paper. Consider the basic model with signals, with authenticated Byzantine faults, where the general signs the initial values and where N L 2t + 1. Then a slight variant of Algorithm 5 achieves consistency, strong unanimity, and termination for an arbitrary value domain. Algorithm 6. N L 2t + 1 The algorithm is identical to Algorithm 5, except that PROPER sets are used. Initially, the PROPER set of processor pi contains its initial value vi, which is signed by the general. Each processor piggybacks its initial value, signed by the general, on all messages. If pi ever receives a value different from vi that is also signed by the general, then pi puts all of V in its PROPER set. It is clear that a correct processor’s PROPER set always contains proper values. 6.2 DISTRIBUTED CLOCKS. Recall that in this section there is some known communication bound A that always holds. Because the previous clocks have limited resiliency, we first describe a distributed clock that is resilient to any number of fail-stop faults. The general form of the clock is similar to the clocks of Sections 5.1 and 5.2. As in Section 5.1, an i-tick is the message i, and an i-claim is the message “I have broadcast an i-tick.” The definitions of F-tick, i+-claim, broadcast an i-tick, and broadcast an i-claim are also the same as in Section 5.1. The clock protocol is given by TICK(b) and CLAIM(b), as in Figure 2. The master clock is C(s) = maximum j such that some processor has broadcast a j-tick by time s. The private clock ci is ci(S) = maximum j such that pi has received either a j’-claim or a (j + 1 )+-tick by time s. We claim that the new fail-stop clock and the authenticated Byzantine clock of Section 5.2, when used in the model of this section, have the following properties: (Al) For all s and all correct pi, ci(S) 5 C(S). (A2) For all s, x 2 0, C(s + x) i C(s) + x. (A3) Consider a run in which the processor bound + holds after time GST (in the unknown phi model, GST = 0 for uniformity as explained before), and let D = 3@ + A. There are constants al and a2 depending polynomially on N, A, and 9 such that (A3.1) for all correct pi and all s 2 GST + al, Cu 2 C(s) - D - 1; (A3.2) for all s 2 GST + al, C(s + a2) 2 C(s) + 1.