Byzantine Agreement

Functionality Description

Byzantine agreement is a classical problem concerned with reaching agreement on a single bit of data in a network of $n$ players, out of which $t$ players may be faulty. Each player starts with an input bit $b_{i}$ and the objective is that all non-faulty players to output the same bit $d$ (agreement), under the constraint that $d=b_{i}$ for some node $i$ (validity). The difficulty of this task depends on the failure model of the faulty players. In Byzantine agreement, the faulty players are allowed to behave arbitrarily (including actively breaking the protocol, colluding etc). Byzantine agreement is an important problem in classical distributed systems, used to guarantee consistency among distributed data structures.

Tags: Quantum Enhanced Classical Functionality, Multi Party Protocols, Specific Task, consensus task, failure-resilient distributed computing.

Protocols

• Fast Quantum Byzantine Agreement: (Fault-tolerant) Quantum computing network stage

Properties

A Byzantine Agreement protocol is formally defined to satisfy the criteria agreement, validity and termination. Agreement simply requires every non-faulty player to output the same bit. Validity excludes the trivial solution of always outputting a specific bit, by requiring that the agreement value is at least proposed once. Termination means that any protocol is required to eventually finish. Formally, Byzantine agreement is achieved if

• Agreement: Every non-faulty player outputs the same bit $d$.

• Validity: The agreement value $d$ is proposed by at least one node, i.e. $d=b_{i}$ for some node $i$.

• Termination: The protocol will eventually terminate.

In Byzantine Agreement, node failures are modeled as Byzantine Failures. In this failure model, the failed nodes are allowed to behave arbitrarily, including maliciously trying to prevent the non-faulty nodes from reaching agreement. In particular, failed nodes can collude together.

Further Information

• Agreement problems are also studied in weaker failure models such as crash-failures.
• Byzantine agreement is equivalent to the closely related problems of Byzantine Generals (in which only one player gets an input bit, which must be correctly communicated to all non-faulty players) and Interactive Consistency (in which all non-faulty players must correctly know the received input bit of each non-faulty player).
• It is known that no protocol can solve Byzantine Agreement if the number of failures $t>n/3$.

*contributed by Bas Dirke