Self-stabilizing Byzantine Tolerant Replicated State Machine Based on Failure Detectors

Abstract

Byzantine Fault Tolerant (BFT) replication leverages highly available cloud services and can facilitate the implementation of distributed ledgers, e.g., the blockchain. Systems providing BFT State Machine Replication (SMR) work under severe system assumptions, for example, that less than a third of replicas may suffer a Byzantine failure. Infrequent arbitrary violations of such design assumptions, may lead the system to an unintended state, and render it unavailable thereafter, requiring human intervention. Self-stabilization is a highly desirable system property that can complement Byzantine fault tolerant systems, and allow them to both tolerate Byzantine-failures and automatically recovery from any unintended state that assumption violations may lead to.This paper contributes the first self-stabilizing State Machine Replication service that is based on failure detectors. We suggest an implementable self-stabilizing failure detector to monitor both responsiveness and the replication progress. We thus encapsulate weaker synchronization guarantees than the previous self-stabilizing BFT SMR solution. We follow the seminal paper by Castro and Liskov of Practical Byzantine Fault Tolerance and focus on the self-stabilizing perspective. This work can aid towards building distributed blockchain system infrastructure enhanced with the self-stabilization design criteria.