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.
Byzantine Agreement
Tags:
Leave a Reply