Asynchronous Byzantine Consensus: Complexity, Resilience and Authentication
Partha Sharathi Dutta, Rachid Guerraoui, Marko Vukolić · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · 2004
We present a consensus algorithm that tolerates Byzantine process failures and arbitrarily long periods of network asynchrony. Our algorithm is the first to match the general time-complexity lower bound of [14], for which we give a complete proof. When the necessary conditions for optimal communication latency are not met, our algorithm gracefully degrades and retains the time-complexity of previously known Byzantine consensus algorithms, albeit covering a wider range of system configurations. We prove that this graceful degradation cannot be achieved without using public-key cryptography (authentication) or tolerating less failures. While doing so, we state the first trade-off between the time-complexity of consensus, the underlying resilience, and authentication.