-
Each process starts with an input from a fixed set V = {0,1}. The goal is for the players to eventually output decisions from the set V upholding the following conditions, even in the presence of an adversary that can Byzantinely corrupt up to any t of the n players:
-
Agreement: All non faulty processes decide on the same value
-
Validity: If all non-faulty processes start with the same initial value, then u=v.
-
Termination: All non faulty processes eventually decide
The procedure consists of exchange of messages, followed by computation of interactive consistency vector on the basis of result of exchange.
-
Two round of information exchange is required:
-
In the first round the processors exchange their input values.
-
In the second round they exchange all the values obtained in the first round.
-
Processes are supplemented with “magical powers” to authenticate their communication – Digital Signatures.
-
Pease et. al. showed that using authentication, fault tolerance can be increased to t < n
-
Player k maintains a set Wik. Initially Wkk={s} where s is player k’s input value.
-
Repeat the following steps for 2 rounds:
-
Receive values from neighbors and for each received value do:
-
If the message is properly signed, he append its content to the set Wik
-
Sends i, Wik to his neighbors.
-
He deletes Wik if | Wik |1.
-
Since all remaining Wik’s are singleton, he takes majority over all values. If a majority exists he decides on it, else decides on the default value.
- In a (synchronous) P2P network of n nodes, t of which are (Byzantine) faulty, consensus/agreement is possible only if the network is (2t + 1)-connected
- With cryptography: (t + 1)-connectivity is sufficient.
- In a (synchronous) P2P network of n nodes, t of which are (fail-stop / Byzantine) faulty, consensus requires > t rounds, in the worst case