Consensus in the Presence of Partial Synchrony 319 follows as in Section 5.3 that, within a short time after GST, the number of ticks in e’ that are allotted for the simulation of any round r is sufficient to allow all round r messages to be sent and received. It remains to show that signals behave correctly: (a) Whenever a correct processor pi receives a signal at any round r, it means that all of the messages sent by processor pi at round r to correct processors actually get received. (b) Within a short time after GST, all correct processors receive signals at all rounds. We first show (a). Assume that correct processor pi receives a signal at round r, that pi sends a message to correct processor pj at round r, and that s is the real time when the message is sent. Then the message arrives at processor pj by real time s + A. Processor pj might not actually receive the message at this time, since it is not executing a Receive operation at this time. However, the key fact for the simulation is that the message will be received the next time that pj executes a Receive operation, and that, when this Receive occurs, pj has not yet started any round greater than r. That is, we must show that Cj(S + A) < rR. To show this, first note that, since processor pi receives a signal for round r, there must be a real time s ’ with s ’ > s such that pi executes a Receive operation in the clock protocol at time s’ and Ci(S’) < rR - (2A + 1). Now, Cj(S + A) = C(S + A) (by (Al)) sC(s’+A) (since s’ > s) s C(s’) + A (by 042)) s Ci(S’) + 2A + 1 (by (A4)) < rR (by the condition defining simulation of signaling). Next, we show (b). Fix some round r after GST, and let s be the earliest time at which p;s private clock reaches or exceeds (r - 1)R. Processor pi can broadcast a message to all processors and execute a Receive operation in the clock protocol within 3(N + I)@ steps after s. Therefore, we must show that Ci(S + 3(N + l)@) C rR - (2A + 1). This is true because Ci(S + 3(N + I)@) 5 C(S + 3(N + l)@) (by (Al)) 5 C(s - 1) + 3(N + l)@ + 1 (by b42N 5 Ci(S - 1) + 3(N + l)@ + D + 2 (by (A3.1)) < (r - 1)R + 3(N + l)@ + D + 2 (by assumption) 5rR-(2A+ 1) (by calculation). By applying this transformation to Algorithms 4, 5, and 6, we obtain Algo- rithms 4’, 5’, and 6’, respectively. THEOREM 6.3. Assume that communication is synchronous and processors are partially synchronous (phi holds eventually).