Consensus in the Presence of Partial Synchrony 315 transmission time that always holds (in particular, no messages are lost). Of course, the protocols of the previous section with their associated resiliencies work for such models, but by using the fact that communication is now synchronous, we can achieve higher resiliencies in some cases. It is convenient to base our consensus algorithms on another basic model, which we call the basic model with signals. In Section 6.1 we define this new basic model and give consensus algorithms that are designed to work in the basic model with signals. We then show how to use the eventual phi and unknown phi models to simulate the basic model with signals. As in Section 5, we use distributed clocks to give the processors some approximately common notion of time. The clocks are discussed in Section 6.2. Section 6.3 contains algorithms for the case in which phi holds eventually, and Section 6.4 contains algorithms for phi unknown. Section 6.5 contains lower bounds. 6.1 A BASIC MODEL WITH SIGNALS. The basic model with signals is just like the basic model, except that the Receive subround also includes the possible receipt of a signal by each processor. In any round r, the receipt of a signal by processor pi implies that all correct processors receive the round r messages sent to them by processor pi. The nonreceipt of a signal does not imply anything. At round GST and afterward, we assume that all correct processors receive signals at each round. The next two subsections, 6.1.1 and 6.1.2, give consensus protocols for the basic model with signals that are resilient to two types of faults. 6.1.1 Fail-Stop Faults. The next algorithm achieves strong unanimity for an arbitrary value domain V. Algorithm 4. N L t Each processor has a local variable VALUE, initialized at its initial value. We say that each round k = i mod N belongs to processor pi. Processing in an arbitrary round k is as follows: Processing for pi, where round k belongs to pi: Broadcast VALUE; If a signal is received, then decide on VALUE. Processing for pi, where round k does not belong to pj: If a message is received with contents v, then set VALUE := v. LEMMA 6.1. Assume that processor pi decides v at round k, and that this is the smallest numbered round at which a decision is made. Then no message containing value w # v is ever sent at any round 2 k. PROOF. Assume for the sake of contradiction that the lemma is false, and let h be the smallest numbered round L k when a message containing value w # v is sent. It is clear that h # k, since faults are fail-stop. Let pj be the processor that owns round h. Since processor pi receives a signal at round k, it must be the case that processor pj receives value v from processor pi at round k and therefore sets its VALUE to v. By assumption, no message with value different from v is sent at rounds after k and before h. Therefore, processor pi’s VALUE remains equal to v until the beginning of round h. This contradicts the assumption that processor pj sends w at round h. 0