The system model contains a collection of nn processes that ff processes may exhibit Byzantine behavior, i.e., nfn-f processes are non-faulty.

For the Byzantine failure model, the agreement and validity conditions are slightly different from those we defined in this definition :Conditions_for_consensus_problem of the fail-stop failure model, while the termination property stays the same.

Correctness conditions for the Byzantine agreement problem

There are nn processes, of which at most ff might exhibit Byzantine behavior, i.e., at least nfn-f processes are correct, and any non-faulty process pip_{i} starts with an initial input value vi{0,1}=Vv_{i} \in\{0,1\}=V. The non-faulty processes must decide on one of those values, satisfying the following properties:

  1. Termination: Every non-faulty process ii eventually irreversibly decides on a value di{0,1}d_{i} \in\{0,1\} in finite time.
  2. Agreement: All non-faulty processes decide for the same value, i.e., no two non-faulty processes decide differently.
  3. Validity: If all non-faulty processes started by proposing the same initial value v{0,1}v \in\{0,1\}, then any non-faulty process in the decided state has chosen that value vv, i.e., di=vd_{i}=v for all non-faulty processes ii.

Note: Since the set of initial values only consists of binary values {0,1}\{0,1\}, this kind of agreement is also called the Binary Byzantine agreement. Any algorithm that solves the Byzantine agreement for binary values can be used as a subroutine for solving the general Byzantine agreement.

According to Lynch (1996)Nancy A. Lynch. Distributed Algorithms. The Morgan Kaufmann Series in Data Management Systems. San Francisco, California, 1996. Elsevier Science., the modified properties of this definition “reflect the fact that in the Byzantine model, it is impossible to impose any limitations on what the faulty processes might start with or what they might decide.”

While only non-crashing processes are able to reach the decided state in the fail-stop model and hence every correct process decided for the same value at the end, faulty processes are able to state an incorrect decision variable at the end of the agreement process in the Byzantine failure model.

Get hands-on with 1200+ tech skills courses.