298 C. DWORK ET AL. It is easy to see that all correct processors make decisions by round GST + 4(N + 1). 3.2.2 Byzantine Faults with Authentication. The second algorithm achieves strong unanimity for an arbitrary value set I’, in the case of Byzantine faults with authentication. Algorithm 2. N 2 3t + 1 Initially, each processor’s PROPER set contains just its own initial value. Each processor attaches its PROPER set and its initial value to every message it sends. If a processor p ever receives 2t + 1 initial values from different processors, among which there are not t + 1 with the same value, then p puts all of V (the total value domain) into its PROPER set. (Of course, p would actually just set a bit indicating that PROPER contains all of V.) When a processor p receives claims from at least t + 1 other processors that a particular value v is in their PROPER sets, then p puts v into its own PROPER set. It is not difficult to check that each PROPER set for a correct processor always contains only proper values. Processing is again divided into alternating trying and lock-release phases, with phases numbered as before and of the same length as before. At various times during the algorithm, processors may lock values. In Algorithm 2, not only is a phase number associated with every lock, but also a proof of acceptability of the locked value, in the form of a set of signed messages, sent by N - t processors, saying that the locked value is acceptable and in their PROPER sets at the beginning of the given phase. 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 = 4k - 3 be the first round of phase k, and assume k = i mod N. At round s, each processor pj (including pi) sends a list of all its acceptable values that are also in its PROPER set to processor pi, in the form Ej(list, k), where Ej is an authentication function. Just after round S, processor pi attempts to choose a value to propose. In order for processor pi to propose v, it must have heard that at least N - t processors 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 Ei(lock v, k, proof), where the proof consists of the set of signed messages Ej(list, k) received from the N - t processors that found v acceptable and proper. If any processor receives an Ei(lock v, k, proof) message at round s + 1, it decodes the proof to check that N - t processors find v acceptable and proper at phase k. If the proof is valid, it locks v, associating the phase number k and the message Ej(lock v, k, proof) with the lock, and sends an acknowledgment 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. The entire message Ei(lOck v, k, proof) is said to be a valid lock on v at phase k. 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 round s + 3 = 4k. Processors broadcast messages of the form Ei(lock v, h, proof), indicating that the sender has a lock on v with associated phase h and the given associated proof, and that processor pi sent the message at phase h, which caused the lock to be placed. If any processor has a lock on some value v with associated phase h and receives a properly signed message