Byzantine Agreement: Difference between revisions

Byzantine agreement is a classical problem concerned with reaching agreement on a single bit of data in a network of <math>n</math> players, out of which <math>t</math> players may be faulty (untrusted). Each player starts with an input bit <math>b_i</math> and the objective is that all non-faulty players to output the same bit <math>d</math> (''agreement''), under the constraint that <math>d = b_i</math> for some node <math>i</math> (''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.