Consensus

Consensus follows the algorithm described by "the latest gossip on BFT consensus". It includes two modifications: fast forwarding and rebasing.

The algorithm described by "the latest gossip on BFT consensus" assumes that process will eventually see all messages. This allows the algorithm to restrict its cases to messages that are bound for the Hₚ (the current of the honest process). However, this is not true in practice, since honest processes may find themselves crashing unexpectedly, or on the wrong side of a network partition.

For example, an honest process could become unavailable at height Hₚ and not become available again until Hₚ+N. At this point, none of the cases described by "the latest gossip on BFT consensus" will be triggered. Ideally, such an honest process is able to fast forward to Hₚ+N without relying on other honest processes relaying all missing messages.

We introduce the case:

upon (PROPOSAL, H, Round, V, *) and 2F+1 (PRECOMMIT, H, Round, id(V)) while H > Hₚ do
  if valid(V) then
    Decisionₚ[Hₚ] = V
    Hₚ = H + 1
    reset LockedRoundₚ, LockedValueₚ, ValidRoundₚ, and ValidValueₚ to initial values and empty message log
    startRound 0

In practice, the (PROPOSAL, H, Round, V, *) and (PRECOMMIT, H, Round, id(V)) messages required to trigger this case are optionally sent as part of a new (PROPOSAL, H+N, *, *, *) message (where honest processes will set N=1).