Bridging the Gap of Timing Assumptions in Byzantine Consensus
Open Access
- 27 November 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 178-191
Abstract
Asynchronous Byzantine Fault-Tolerant (BFT) consensus protocols maintain strong consistency across nodes (i.e., ensure safety) and terminate probabilistically (i.e., ensure liveness) despite unbounded network delay. In contrast to protocols under partial synchrony, asynchronous counterparts pay no extra timing assumptions for electing a special role, and thus is more robust to network issues. To formally study this feature, we propose a new classification method for consensus and accordingly categorize relevant work: timing-balanced protocols are those that do not introduce strictly stronger timing-related assumptions for liveness, compared to ones required by safety. We further propose ThemiX, a novel timing-balanced protocol under the hybrid model: either there is no corrupt node, or the number of correct and online nodes constitute a majority. ThemiX tolerates f Byzantine faults with a total of n = 2f + 1 nodes, achieving optimal resilience. If every node is honest or benign, ThemiX is an asynchronous protocol. Otherwise, ThemiX relies on timing assumptions for ensuring safety and probabilistic termination. No leader or any special role is elected. To boost performance, we further integrate two practical mechanisms that respectively allow ThemiX to proceed at the pace of actual network speed and bypass the expensive coin-tossing phase (i.e., randomization). Large-scale experiments on Amazon EC2 platform show that ThemiX achieves up to 86% reduction in latency compared to the consensus component of HoneyBadgerBFT and provides sustainable performance under simulated network faults.Keywords
This publication has 41 references indexed in Scilit:
- Paxos made live2007
- Resilient-optimal interactive consistency in constant timeDistributed Computing, 2003
- Practical byzantine fault tolerance and proactive recoveryACM Transactions on Computer Systems, 2002
- Implementing fault-tolerant services using the state machine approach: a tutorialACM Computing Surveys, 1990
- Consensus in the presence of partial synchronyJournal of the ACM, 1988
- Asynchronous Byzantine agreement protocolsInformation and Computation, 1987
- Asynchronous consensus and broadcast protocolsJournal of the ACM, 1985
- Impossibility of distributed consensus with one faulty processJournal of the ACM, 1985
- Authenticated Algorithms for Byzantine AgreementSIAM Journal on Computing, 1983
- Reaching Agreement in the Presence of FaultsJournal of the ACM, 1980