AGREEMENT PROTOCOLS
Three Agreement Problems
- Byzatine Agreement Problem : In this problem one processor initiates
the value and the value agreed upon is the value of the source. If the
source processor is non-faulty then the value agreed upon should be
the value of the source.
- Consensus Agreement Problem: All the processors broadcasts their
values to all the other processors. All the non-faulty processors
should agree on one single value.
- Interactive Consistency Problem : All the processors broadcasts their
values to the other processors. All the non-faulty processors should
agree on the same vector of values.
In all the three cases, it is irrelevant what the faulty processors
agree upon.
The three agreement problems are closely related. The interactive
consistency problem can be solved if each of the n-processors run a copy
of the Byzantine agreement solution and the consensus problem can be solved by
choosing a majority value from the solution of the interactive consistency
problem.
Oral Message Algorithm OM(m)
The three agreement problems can be solved by the Oral Message Algorithm OM(m).
This algorithm is valid only under the condition n > = 3m + 1, where n is
the total number of processors and m is the total number of faulty processors.
Illustrating this algorithm using an example, consider the case of four
processors, with one faulty processor as shown in the figure below.
Processor P0 acts as the source and intiates algorithm OM(1) and broadcasts
its value to the other three processors.
On receiving this value, each of the three processors P1, P2 and P3 execute
algorithm OM(0) and exchange the received value with the other two processors.
P2, being the faulty processor, sends different values to P1 and P3.
At the end of the algorithm, the values received by the processors are :
P1 (1,1,1), P2 (1,1,1), P3 (1,1,0). In the final step the majority value is selected by all the three processors. Therefore the agreement problem can be solved.
Oral Message algorithm is recursive with complexity O(n^m).