Consensus in the Presence of Partial Synchrony 301 BROADCAST of m by p at superround k: N 2 3t + 1 Superround k: First round: p sends (init, p, M, k) to all; Second round: Each processor executes the following for any message m: if received (init, p, m, k) from p in the first round and received only one init message from p in the first round, then send (echo, p, m, k) to a& if received (echo, p, m, k) from at least N - t distinct processors in this round, then accept m from p; All subsequent rounds: Each processor executes the following for any message m: if received (echo, p, m, k) from at least N - 2t distinct processors in previous rounds, then send (echo, p, m, k) to all; if received (echo, p, m, k) from at least N - t distinct processors in this or previous rounds, then accept m from p. FIG. 1. The BROADCAST primitive. Algorithm 3. N L 3t + 1 Processing is again divided into trying and lock-release phases, with phases numbered as before. Each trying phase takes three superrounds, that is, six ordinary rounds. Lock-release phase k is done during the third superround of trying phase k. As before, a value v is acceptable to p if p does not have a lock on any value except possibly v. We now describe the processing during a particular trying phase k. Let s = 3k - 2 be the first superround of phase k, and assume k = i mod N. At superround s, each processor pj (including pi) BROADCASTS a list of all its acceptable values that are also in its PROPER set in the form (list, k). Just after superround s, processor pi attempts to choose a value to propose. In order for processor pi to propose v, it must have accepted messages from at least N - t processors stating that they find value v acceptable and proper at phase k. Again, if there is more than one possible value that processor pi might propose, then it will choose one arbitrarily. Processor pi then BROADCASTS a message (lock v, k) during super- rounds+ 1. If any processor q has by superround s + 1 accepted a message (lock v, k) from pi and also accepted messages (list, k) from N - t processors stating that they find v acceptable and proper at the first superround of phase k, then q locks v, associating the phase number k with the lock, and sends an acknowledgment (ack, k) to processor pi. In this case any earlier lock on v is released. (Any locks on other values are not released at this time.) If the processor should receive such messages for more than one value v, it handles each one similarly. We say that q accepts a valid lock on v with phase k if it has accepted a message (lock v, k) from pi and accepted N - t messages (list, k) as just described. These messages do not all have to be accepted at the same round. If processor pi receives acknowledgments from at least 2t + 1 processors, then processor pi decides v. After deciding v, processor pi continues to participate in the algorithm. Lock-release phase k occurs at the end of the third superround of phase k. In this algorithm the lock-release phase does not send any messages. If a processor q has a lock on some value v with associated phase h and q has accepted, at this