Orcaella: Hybrid Fault Tolerance with Client-Selectable Finality Latency
2026-07-06 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster ComputingCryptography and Security
AI summaryⓘ
The authors study how to make replicated systems that can continue working correctly even when some computers crash or behave maliciously. They focus on protocols that commit decisions quickly, in just two messages, while handling a mix of crash faults and faulty malicious replicas. They prove the exact number of replicas needed to guarantee safety and liveness under these conditions and introduce a more resilient mode that requires slightly more communication but tolerates more faults. Their work details the trade-offs between speed and fault tolerance in these systems.
Byzantine fault tolerancestate machine replicationpartially synchronousPBFTcommit pathequivocationlivenesssafetycrash faultsfault tolerance
Authors
Lefteris Kokoris-Kogias, Alberto Sonnino
Abstract
Classical partially synchronous state machine replication, as in PBFT, tolerates f Byzantine replicas among n at least 3f+1 using three communication steps per request. Recent protocols such as Minimmit achieve two-message-delay decisions under stronger size assumptions, notably n at least 5f+1 when any silent replica must be counted as a potential equivocator. Hydrangea and Kudzu treat mixed Byzantine and crash faults, focusing on providing a fast-path under optimistic conditions while maintaining a fall-back commitment path similar to PBFT. In this paper, we also consider a mixed model, but focus on studying the fault tolerance of the 2-message-delay commit. For this, we prove a tight bound of n at least 5f+3c+1. Extending this result, we also show that there exists a more resilient commit path that allows an extra f_abc < n-3f-2c alive-but-corrupt faults at 4-message-delays. Core liveness is claimed in executions with at most f equivocators; if this regime is violated (e.g., AbC-induced forks), the protocol enters synchronous recovery, where only the resilient-path safety guarantee is preserved. As a result, for f=16, c=6, and n=99, we obtain a commit path that tolerates 22% of replicas failing for liveness, 16% equivocating for 1-RTT safety, and 54% equivocating for 2-RTT safety.