C. DWORK ET AL. 318 (A4) For all s at which the correct processor pi executes a Receive operation in the clock protocol, C(S) - (A + 1) I Ci(S). To be technically precise, in the fail-stop case in Section 6 we consider a processor to be “correct” up until the time it fails (assuming that it does fail). In particular, the four properties above hold for all processors up until the time they fail. For the authenticated Byzantine clock, we have already proved (Al), (A2), and (A3) in Lemmas 5.1, 5.3, and 5.7, respectively, with modifications as described in the proof of Lemma 5.8. To prove that these properties hold for the fail-stop clock, we first note that Lemmas 5.1-5.4 hold for the fail-stop clock; the proofs are very similar to the proofs given in Section 5.1 and are left to the reader. Lemma 5.5 is not needed. Since A always holds, we can prove a stronger version of Lemma 5.6 for the fail-stop clock. LEMMA 5.6’. For all s > GST + D and all correct pi, Ci(S) 2 C(S - D) - 1. PROOF. Letj = C(s - D). By definition of the master clock, some processor has broadcast a j-tick by time s - D, so every correct processor will receive a j+-tick by time s. Therefore, ci(s) 2 j - 1, by definition of the private clock. 0 Now Lemma 5.7 follows from Lemma 5.6’ and previous lemmas as before. (However, we only need s 2 GST + D for part (a) and s 2 GST for part (b)). The proof of (A4) is similar for both clocks. Let j = C(s - A). A j-tick has been broadcast by time s - A, so processor pi, by time s, will receive a j+-tick. For the authenticated Byzantine clock, this j’-tick contains t + 1 (j - I)+-claims. For either clock, by definition of the private clock and by property (A2), ci(s)Zj-l=C(s-A)-lZC(s)-A-1. 6.3 UPPER BOUNDS WHEN PHI HOLDS EVENTUALLY. The only improvements over the case in which both phi and delta hold eventually are for fail-stop faults and authenticated Byzantine faults (the latter either for weak unanimity or for strong unanimity, with a general signing the initial values). Fix one of these fault models. We show that, if there is a t-resilient protocol in the basic model with signals, then there is one in the model where phi holds eventually. Fix A and a’, and assume algorithm A works for the basic model with signals. Define A ’ as follows. Two out of every three steps of each processor are used to maintain a distributed clock, and the other step is used to simulate algorithm A. For fail-stop faults, we use the new fail-stop clock of Section 6.2, while for authenticated Byzantine faults we use the authenticated Byzantine clock. Message buffers are maintained as in Section 5.3. Fix R = 3N@ + (20 + 2) + (A + I), where, as before D = A + 3@. Each processor determines the current round being simulated and conducts the rest of the simu- lation exactly as in Section 5.3. We must describe how signals are simulated. If a processor pi has sent all its messages for a particular round r, performed a Receive operation in the clock protocol, and updated its private clock, and if the clock then satisfies Ci < rR - (2A + I), then pi acts in A ’ as pi would act in A if it had received a signal for round r. For any run e’ of A ‘, we define a corresponding run e of A. Again, faults are preserved. Since the R in this section is larger than the R used in Section 5.3, it