300 C. DWORK ET AL. polynomial time complexity and polynomial message lengths. The modification is done by using a minor variation of a broadcast primitive, introduced by Srikanth and Toueg [20], which simulates the crucial properties of authentication. We first state these properties, then give the broadcast primitive, and finally describe the new agreement protocol. The broadcast primitive (and hence the agreement algorithm that uses the broadcast primitive) is defined in terms of superrounds, where each superround consists of two normal Send-Receive rounds. Superround GST occurs at the earliest super-round, when both of its Send-Receive rounds occur at or after round GST. The primitive gives an algorithm for a processor p to BROADCAST a message m at superround k and also gives conditions under which a processor will accept a message m from p (which is not to be confused with our definition of an “acceptable value”). The crucial properties of broadcasting that are used in the (authenticated) Algorithm 2 are as follows: (1) Correctness. If a correct processor p BROADCASTS m in superround k L GST, then every correct processor accepts m from p in superround k. (2) Unforgeubility. If a correct processor p does not BROADCAST m, then no correct processor ever accepts m from p. (3) Relay. If a correct processor accepts m from p in superround r, then every other correct processor accepts m from p in superround max(r + 1, GST) or earlier. The description of the BROADCAST primitive is given in Figure 1. The proof that the primitive has the Correctness and Unforgeability properties is identical to the proof of Srikanth and Toueg [20]. We give the proof of the Relay property since it is slightly different than in [20]. Say the correct processor q accepts m from p in superround Y. Therefore, q must have received (echo, p, m, k) from at least N - t processors by the end of the second round of superround r, so at least N - 2t correct processors sent (echo, p, m, k). By definition of BROADCAST, if a correct processor sends (echo, p, m, k) at some round h, it continues to send (echo, p, m, k) at all rounds after h. Therefore, every correct processor will receive (echo, p, m, k) from at least N - 2t processors by the end of the first round of superround max(r + 1, GST). Hence, every correct processor will send (echo, p, m, k) at the second round of max(r + 1, GST). So every correct processor will receive N - t (echo, p, m, k) messages by superround max(r + 1, GST) or earlier, and will accept m from p. The only difference between the protocol of Figure 1 and that of Srikanth and Toueg [20] is in the relaying of an (echo, p, m, k) message after N - 2t (echo, p, m, k) messages have been received. In our case, the echo message continues to be sent at every round after the N - 2t echoes are received, whereas in [20] the echo is sent only once. Since messages can be lost before GST in our model, the resending seems to be needed to get the Relay property. Although resending the echoes makes message length grow proportionally to the round number (since a new invocation of BROADCAST could be started at each round), message length is still polynomial in N and GST. In models where messages cannot be lost, such as the unknown delta model, each (echo, p, m, k) need be sent only once by each correct processor, resulting in shorter messages. Next follows the new algorithm for the unauthenticated Byzantine case in the basic model. It is patterned after the authenticated algorithm. In particular, hand- ling of PROPER sets is done exactly as in Algorithm 2.