C. DWORK ET AL. 308 what ticks have been sent to which processors. We therefore introduce a second type of message, called a claim, in which processors make assertions about the ticks they have sent. An i-tick is the message i. An i+-tick is a j-tick for any j 2 i. We say p has broadcast an i-tick if it has sent an i+-tick to all N processors. An i-claim is the message “I have broadcast an i-tick.” An P-claim is a j-claim for any j 2 i. We say p has broadcast an i-claim if it has sent an i’-claim to all N processors. We adopt the convention that all processors have exchanged ticks and claims of size 0 before time 0. These messages are not actually sent, but they are considered to have been sent and received. When we say that a certain event, such as the receipt of a certain message, has occurred “by time s,” we mean that the event has occurred at some real-time step 5s. The master clock, C: N + N, is defined at any real time s by C(s) = maximum j such that t + 1 correct processors have broadcast a j-tick by time s. Since all processors are assumed by convention to have broadcast a O-tick before time 0, C(0) = 0. Note that C(s) is a nondecreasing function of s. For each processor pi, the private clock, Ci: N + N, is defined by ci(S) = maximum j such that, by time s, pi has received either ( 1) messages from 2 t + 1 processors, where each message is a j+-claim, or (2) messages from t + 1 processors, where each message is either a (j + l)+-tick or a (j + I)+-claim. Since pi is assumed to have received O-claims from all N processors before time 0, Ci(0) = 0 for all correct pi. Note that ci(S) is nondecreasing for all correct pi. Let pi be a correct processor. In sending ticks, pi’s goal is to increment the master clock, so ideally we would like pi to send a (C(s) + l)-tick at time s. However, knowing C(s) requires global information. Instead, pi uses ci, its view of C, to compute its next tick, sending a (Ci(S) + l)-tick at time s. We show in Lemma 5.1 that Ci(S) 5 C(s), so pi will never force the master clock to skip a value. We also show that, “soon” after GST for the GST model, the value of the master clock exceeds those of the private clocks by at most a constant amount, so that pi will not be pushing the master clock far ahead of the private clocks of the other processors. Each processor pi repeatedly cycles through all N processors, broadcasting, in different cycles, either ticks or claims. The private clock of pi is stored in a local variable Ci. Processor pi updates its private clock every time it executes a Receive operation in the clock protocol by considering all the ticks and claims it has received and updating its private clock according to the definition of the private clock given above (thus the private clock is updated every second clock step, i.e., every third step, that pi takes). The following two programs describe how ticks and claims are sent during the sending steps of the clock protocol. A processor begins the distributed clock protocol by setting Ci to 0 and calling TICK(O), where TICK(b) is the protocol shown in Figure 2. Note that the value of Ci may change during an execution of TICK(b), but only a (b + I)-claim (rather than a (ci + I)-claim) is sent during execution of CLAIM(b). This is consistent with our definition of what it means to have broadcast a (b + I)-tick.