On the price of equivocation in byzantine agreement
Alexander Jaffe, Thomas Moscibroda, Siddhartha Sen · 2012
In the Byzantine agreement problem, a set of n processors, any f of whom may be arbitrarily faulty, must reach agreement on a value proposed by one of the correct processors. It is a celebrated result that unless n > 3f, Byzantine agreement is impossible in a variety of computation and communication models. This is due to the fact that faulty processors can equivocate, that is, say different things to different processors. If this ability is mitigated, for example by assuming a global broadcast channel, then n > 2f is sufficient. With very few exceptions, the literature on Byzantine agreement has been confined to the n > 2f and n > 3f paradigms.