Consensus in the Presence of Partial Synchrony 295 in C is allowed by the fault type F, the protocol achieves: -Consistency. No two different processors in C decide differently. -Termination. If R is infinite, then every processor in C makes a decision. -Unanimity. There are two types: Strong unanimity: If all initial values are v and if any processor in C decides, then it decides v. Weak unanimity: If all initial values are v, if C contains all processors, and if any processor decides, then it decides v. In models where messages cannot be lost, such as the models where delta is unknown, our protocols can be easily modified so that all correct processors can halt soon after sufficiently many correct processors have decided. However, we do not require halting explicitly in the termination condition because, as can be easily shown, if messages can be lost before GST in the model where delta holds eventually and if the protocol is l-resilient to fail-stop faults, then there is some execution in which some correct processor does not halt. Further discussion of the issue of halting is given in Section 4.2, Remark 2, after the protocols have been described. 3. The Basic Round Model In this section we define the basic round model and present preliminary versions of our algorithms in this model. In the following sections we show how each of our models can simulate the basic model. 3.1 DEFINITION OF THE MODEL. In the basic round model, processing is divided into synchronous rounds of message exchange. Each round consists of a Send subround, a Receive subround, and a computation subround. In a Send subround, each processor sends messages to any subset of the processors. In a Receive subround, some subset of the messages sent to the processor during the correspond- ing Send subround is delivered. In a computation subround, each processor executes a state transition based on the set of messages just received. Not all messages that are sent need arrive; some can be lost. However, we assume that there is some round GST, such that all messages sent from correct processors to correct processors at round GST or afterward are delivered during the round at which they were sent. As explained in the Introduction, loss of a message before GST does not necessarily make the sender or the receiver faulty. Although all processors have a common numbering for the rounds, they do not know when round GST occurs. The various kinds of faults are defined for the basic model as for the earlier models. 3.2 PROTOCOLS IN THE BASIC ROUND MODEL. In the remainder of this section, we show how the consensus problem can be solved for the basic model, for each of the fault types. To argue that our protocols achieve strong unanimity, we use the notion of a proper value defined as follows: If all processors start with the same value v, then v is the only proper value; if there are at least two different initial values, then all values in Vare proper. In all protocols, each processor will maintain a local variable PROPER, which contains a set of values that the processor knows to be proper. Processors will always piggyback their current PROPER sets on all messages. The way of updating the PROPER sets will vary from algorithm to