It is a common belief that Byzantine fault-tolerant solutions for consensus are significantly slower than their crash fault-tolerant counterparts. Indeed, in PBFT, the most widely known Byzantine fault-tolerant consensus protocol, it takes three message delays to decide a value, in contrast with just two in Paxos. This motivates the search for fast Byzantine consensus algorithms that can produce decisions after just two message delays in the common case, e.g., under the assumption that the current leader is correct and not suspected by correct processes. The (optimal) two-step latency comes with the cost of lower resilience: fast Byzantine consensus requires more processes to tolerate the same number of faults. In particular, 5f+1 processes were claimed to be necessary to tolerate f Byzantine failures. In this paper, we present a fast Byzantine consensus algorithm that relies on just 5f-1 processes. Moreover, we show that 5f-1 is the tight lower bound, correcting a mistake in the earlier work. While the difference of just 2 processes may appear insignificant for large values of f, it can be crucial for systems of a smaller scale. In particular, for f=1, our algorithm requires only 4 processes, which is optimal for any (not necessarily fast) partially synchronous Byzantine consensus algorithm.

The parallel chip-firing game is an automaton on graphs in which vertices “fire” chips to their neighbors. This simple model contains much emergent complexity and has many connections to different areas of mathematics. In this work, we study firing sequences, which describe each vertex's interaction with its neighbors in this game. First, we introduce the concepts of motors and motorized games. Motors both generalize the game and allow us to isolate local behavior of the (ordinary) game. We study the effects of motors connected to a tree and show that motorized games can be transformed into ordinary games if the motor's firing sequence occurs in some ordinary game. Then, we completely characterize the periodic firing sequences that can occur in an ordinary game, which have a surprisingly simple combinatorial description.