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.

Commit

Fast forwarding requires us to define an abstract message that represents consensus on some value V. A natural definition for such a message is:

〈COMMIT H Round V〉=〈PROPOSAL H Round V _〉&& 2f+1〈PRECOMMIT H Round (id V)〉

By definition, the existence of a COMMIT message implies that no other value V' can be can be committed at height H and at least 2f+1 processes are at height H' >= H.