Byzantine Agreement

Tags:

Byzantine Agreement

One of the fundamental problems in fault tolerant distributed computing is the Byzantine agreement problem. Byzantine agreement requires a set of parties in a distributed environment to agree on a value even if some of the parties are corrupted.

A number of solutions to the Byzantine agreement protocol exist. Unfortunately, the fundamental impossibility result of [FLP85] demonstrates that there is no deterministic algorithm for achieving agreement in the asynchronous setting even against benign failures. One solution which overcomes this problem, first introduced by Rabin [Rab83] and Ben-Or [Ben83], is to use randomization.

A randomized protocol uses random assignment, for example electronic coin tossing, and its termination is therefore probabilistic. The requirements for a randomized agreement protocol are:

Validity: If all parties have the same initial value, then any party that decides must decide on this value.

Agreement: Any two parties that decide must decide on the same value.

Probabilistic Termination: With probability 1, all initialized and non-corrupted parties eventually decide.

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *