The Byzantine Agreement in Synchronous Systems

Overview

The Byzantine agreement is different from the fail-stop consensus since a process may fail not just by stopping, but by exhibiting arbitrary behavior. We have already concluded that this is the most difficult case of failure, hence increasing the complexity of its consensus protocol since such a protocol must be resilient to every possible error that can occur. Thus, we do not aim to provide any agreement algorithm, but rather we want to present the main research results of this failure model.

We’ll see that the common property of all these protocols without authentication, is that the number of processes they need is more than three times the failures, i.e., $n>3 f$. This is different from the crash failure case from this lesson, where no special requirements for the relationship between $n$ and $f$ had to be made. This new property is a direct consequence of the increased complexity of the Byzantine failure model.

The Byzantine Generals problem

The consensus problem was first adumbrated by Pease, Shostak, and Lamport (1980)Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. J. ACM, 27(2):228-34, April 1980., whereas processes were able to exhibit arbitrary failures. In their subsequent paper, The Byzantine Generals Problem (1982)Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, July 1982., they expressed the problem of processes that can send conflicting information in the following way:

“Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system. This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach an agreement.”

Hence, they introduced the term Byzantine General in order to describe a faulty process that may possibly act maliciously. As a consequence of the wide influence of this work, the term Byzantine has been widely adopted for describing arbitrary or malicious failure types.

In the Byzantine Generals problem, the generals must decide upon a common plan of action, meaning the honest generals must attack the city simultaneously in order to succeed. According to Lamport et al. (1982)Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, July 1982., the generals need an algorithm that guarantees that “A. All loyal generals decide upon the same plan of action. $[\ldots]$ B. A small number of traitors cannot cause the loyal generals to adopt a bad plan.”

Byzantine Generals problem

A commanding general must send an order to his $n-1$ lieutenant generals such that

1. All loyal lieutenants obey the same order.
2. If the commanding general is loyal, then every loyal lieutenant obeys the order he sends.

An example of such a structure is shown in Figure 1 and Figure 2. In Figure 1, Lieutenant 2 is a traitor and thus sends a conflicting message to Lieutenant 1. However, the commander does not need to be loyal as shown in Figure 2.

Figure 1