Fast Quantum Byzantine Agreement: Difference between revisions

The classical problem of Byzantine agreement [[Quantum Byzantine Agreement#References|(8)]] is about reaching agreement in a network of <math>n</math> players out of which <math>t</math> players may be faulty. Each player starts with an input bit <math>b_i</math> and the goal is for all correct players to output the same bit <math>d</math> [[agreement]], under the constraint that <math>d = b_i</math> at least for some node <math>i</math> [[validity]]. The hardness of this task depends on the failure model of the faulty (sometimes called adversary) players. In Byzantine agreement, the faulty players are assumed to show the most severe form of failure known as Byzantine failures. In this model, faulty players behave arbitrarily, can collude and even act maliciously trying to prevent correct players from reaching agreement. Byzantine agreement is an important problem in classical distributed systems, used to guarantee consistency amongst distributed data structures.