Fast Byzantine Agreement

Nicolas Braud-Santoni, Rachid Guerraoui, Florian Huc

Abstract: This paper presents the first probabilistic Byzantine Agreement algorithm whose communication and time complexities are poly-logarithmic. So far, the most effective probabilistic Byzantine Agreement algorithm had communication complexity O*(sqrt n), and time complexity O*(1). Our algorithm is based on a novel, unbalanced, almost everywhere to everywhere Agreement protocol which is interesting in its own right.

Guest: Florian Huc
Host: Stefan Schmid

On the Price of Equivocation in Byzantine Agreement

Alexander Jaffe, Thomas Moscibroda, and Siddhartha Sen


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 > 3 f , 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 > 2 f is sufficient. With very few exceptions, the literature on Byzantine agreement has been confined to the n > 2 f and n > 3 f paradigms.
We bridge the gap between these two paradigms by assuming partial broadcast channels among sets of three processors, observing that equivocation is fundamentally an act involving three parties: a faulty processor that lies (inconsistently) to two correct processors. We characterize the conditions under which Byzantine agreement is possible for all n = 2 f +h, h an integer in [1.. f ], by giving asymptotically tight bounds on the number of necessary and sufficient partial broadcast channels. We prove these bounds by
a reduction to a problem in extremal combinatorics, which itself is a natural generalization of a well-studied hypergraph coloring problem. Algorithmically, we show that deciding whether a given set of broadcast channels enables Byzantine agreement is co-NP complete. Although partial broadcast channels have been studied in prior work, the bounds obtained on the number of required channels were sub-optimal by up to a factor of . Moreover, this work has been confined to the synchronous model. In contrast, we apply our results to several distinct models and provide stronger motivation for using partial broadcast channels in practice, drawing from recent work in the systems community.


Guest: Siddhartha Sen
Host: Shantanu Das