View article

The problem of reaching agreement in the presence of faults is one of the most fundamental problems in the field of distributed computing. A particularly interesting variant of this problem, introduced by Pease, Shostak and Lamport[PSL], allows Byzantine faults (namely, the faulty players may collaborate in any way). A standard formulation of this problem, called the Byzantine Agreement (BA) problem, follows: Design a protocol that allows the non-faulty players to agree on a common value. The agreed value should be the input value of one of the non-faulty players.

The BA problem was investigated in various models, characterized by several parameters(eg synchrony, privacy of the communication channels, computational power of the players). Of these, a key parameter is the synchrony of the network. Two important criteria for evaluating agreement protocols are resilience and time (“round”) complexity. Informally …