The Byzantine generals problem involves n processors (generals) reaching agreement on some value through exchange of messages despite the existence of faulty processors (traitors). Of course, any solution of the problem depends upon an assumption that the number of faulty processors not exceed a known upper bound t. In this paper, the authors carefully formulate a certain version of the problem and derive a lower bound (in terms of n and t) on the number of rounds of message passing required to reach agreement. They also describe an algorithm that achieves these lower bounds provided n is sufficiently large compared to t .

More precisely, a round is modeled as a directed labeled graph with n + 2 vertices representing the n processors, a source, and a sink. One node, called the origin, receives an input value from the source, and the n processors are each to eventually send an output value to the sink. The graph is assumed to have all possible edges, where each edge is labeled by a value or a message or the empty label. An alternative representation would be to give the graph edges corresponding to values and messages only, and thus avoid empty labels.

In round 0, the only nonempty label is the input value, and it occurs on the edge from the source to the origin node. An edge from a processor p to the sink is labeled with a value (the output value) in at most one subsequent round; otherwise such an edge has the empty label. Once a processor has produced its output, it ceases activity. This condition is represented by the requirement that in any subsequent round, all edges emanating from this process have the empty label.

An algorithm orders the edges emanating from a processor p and assigns a label to each, making use of the results of previous rounds as they pertain to p (the labels on all edges entering and leaving p). A history is an infinite sequence of rounds. Two types of agreement are distinguished. Eventual Byzantine agreement (EBA) means that all correct processors output the same value and, if the origin is correct, that value is the input value. Simultaneous Byzantine agreement (SBA) requires, in addition, that all correct processors give their output in the same round.

The first theorem shows that an algorithm guaranteeing SBA for each history with at most t orderly crash faults requires at least min ( n - 1 , t + 1 ) rounds to reach SBA in any serial history. Two terms require explanation. First, in this theorem, only orderly crash faults are allowed: each faulty processor is assumed to behave correctly until a certain point, after which it fails to send any messages or values. A serial history is one in which for each positive integer k ≤ t, no more than k processors fail in the first k rounds, and no processor fails after round t.

The second theorem shows that for an algorithm guaranteeing EBA for each history with at most t crash faults, and a number f ≤ t, a history with f faults exists in which at least min ( n - 1 , t + 1 , f + 2 ) rounds are required to reach EBA. Note that in this case, a weaker condition is placed on the behavior of a faulty processor; it may fail to send some or all of its messages or values in a certain round, and it need not respect the ordering imposed by the algorithm. As in the earlier situation, however, it must behave correctly before that round and remain silent after it.

Finally, the authors present an algorithm guaranteeing EBA that will tolerate t faulty processors with no restriction on their behavior. The only requirement is that n > max ( 4 t , 2 t ² - 2 t + 2 ). Agreement is reached within min ( f + 2 , t + 1 ) rounds, where f ≤ t is the actual number of faulty processors.

Although the proofs are long and complicated, they are done carefully with a reasonable amount of motivation and explanation to help the reader.