Continuity: A deterministic Byzantine fault tolerant asynchronous consensus algorithm

TR Number
Date
2021-11-09
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract

In 1985, Fischer, Lynch, and Patterson presented the FLP Impossibility Theorem which states that it is impossible for an asynchronous system to reach consensus if at least one node fails; asynchrony prevents distinguishing between process crashes and delays. Traditionally, asynchronous consensus algorithms implement protocol adaptations to handle delays and prevent indefinite runs (e.g. coordination protocols in the form of ordered rounds). In this paper, we present a deterministic Byzantine fault tolerant asynchronous consensus algorithm called Continuity. Within this system, processes do not begin by supporting a possible decision value. Instead, Continuity utilizes logical monotonicity to build an initial configuration that is necessarily univalent, thus eliminating the assumed initial conditions of the FLP Impossibility Theorem. As such, Continuity achieves consensus in a wait-free manner.

Description
Keywords
FLP, Byzantine fault tolerant, Asynchronous consensus
Citation