C. DWORK ET AL. 310 eventually. For the model in which delta and phi are unknown, define GST = 0, for uniformity. The next few lemmas discuss the behavior of the clocks a short time after GST. Lemma 5.4 says that the private clocks increase at most a constant factor more slowly than real time. Lemmas 5.5 and 5.6 are technical lemmas used to prove the following lemma. Lemma 5.7 has two parts: The first says that, at any particular real time, the master clock exceeds the value of the private clocks by at most an additive constant. The second part of Lemma 5.7 says that the master clock runs at a rate at most a constant factor slower than real time. Let D = A + 3+. Note that, if a message is sent to a correct processor p at time s 2 GST, then p will receive the message by time s + D: The message will be delivered by time s + A, and within an additional time 3@, p will execute a Receive operation in the clock protocol. LEMMA 5.4. Assume s 1 GST, and let s’ = s + 12N+ + D. Let j be such that Ci(S) 2 j for all correct pi. Then Ci(S’) 2 j + 1 for all correct pi. PROOF. At time s, pi could be executing TICK(b) for some b < j. However, within time 6N9 after s, pi will call TICK(b’) or CLAIM(b’) for some b’ % j, and within an additional 6N@ steps, pi will broadcast a (j + l)-claim. Therefore, every correct processor will broadcast a (j + I)-claim by time s + 12N@. By time s’, each correct pi will receive at least 2t + l(j + l)+-claims, so Ci(S’) I j + 1. Cl LEMMA 5.5. Assume s L GST, and let s’ = s + 39N@ + 40. Then C(s’) 2 C(s) + 2. PROOF. Let j = C(s). By definition of the master clock, t + 1 correct processors have broadcast a j-tick by time s. These t + 1 processors send a tick or claim of size at least j to every processor within the first 3N@ steps after time s. Since these messages are sent after GST, they are received within D steps, so ci(S + 3N+ + D) z j - 1 for all correct pi. By three applications of Lemma 5.4, Ci(S’) 2 j + 2. So C(s’)rj+2byLemma5.1. Cl LEMMA 5.6. Let so be the minimum time such that C(so) r C(GST) + 2. (Time so exists by Lemma 5.5.) Let s 2 so + D. Then ci(s) 1 C(s - D) - 1 for all correct pi. PROOF. Let j = C(s - D). Then t + 1 correct processors broadcast a j-tick by s - D. By Lemma 5.2, the largest tick sent by a correct processor by GST is a (C(GST) + 1 )-tick. Since j 2 C(GST) + 2, the j-ticks from correct processors are broadcast entirely after GST, so they are received by time s. Thus, for all correct pi, Ci(S) 2 j - 1. Cl LEMMA 5.7. Let so be the minimum time such that C(so) I C(GST) + 2. (a) For all s L so + D andfor all correct processors pi, ci(s) > C(s) - D - 1. (b) For all s L so andfor s’ = s + 24N@ + 30, C(s’) 2 C(s) + 1. PROOF (a) Lemma 5.6 implies ci(s) > C(s - D) - 1. By Lemma 5.3, C(s) 5 C(s - D) + D I Ci(s) + 1 + D. Thus, Ci(S) 2 C(S) - D - 1. (b) Let x = s + D. Lemma 5.6 implies Ci(X) 2 C(S) - 1 for all correct pi. By two applications of Lemma 5.4, Ci(S’) L C(s) + 1. So C(s’) I C(s) + 1 by Lemma 5.1. 0