Problem Definition

Overview

The system model contains a collection of $n$ processes that $f$ processes may exhibit Byzantine behavior, i.e., $n-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 $n$ processes, of which at most $f$ might exhibit Byzantine behavior, i.e., at least $n-f$ processes are correct, and any non-faulty process $p_{i}$ starts with an initial input value $v_{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 $i$ eventually irreversibly decides on a value $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 \in\{0,1\}$, then any non-faulty process in the decided state has chosen that value $v$, i.e., $d_{i}=v$ for all non-faulty processes $i$.

Note: Since the set of initial values only consists of binary values $\{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.