A Byzantine Fault Tolerant Distributed Commit Protocol
📜 Abstract
In this paper, we present a Byzantine fault tolerant distributed commit protocol for transactions running over untrusted networks. The traditional two-phase commit protocol is enhanced by replicating the coordinator and by running a Byzantine agreement algorithm among the coordinator replicas. Our protocol can tolerate Byzantine faults at the coordinator replicas and a subset of malicious faults at the participants. A decision certificate, which includes a set of registration records and a set of votes from participants, is used to facilitate the coordinator replicas to reach a Byzantine agreement on the outcome of each transaction. The certificate also limits the ways a faulty replica can use towards non-atomic termination of transactions, or semantically incorrect transaction outcomes.
✨ Summary
The paper proposes BFTDC, a Byzantine fault-tolerant extension of two-phase commit for distributed transactions operating over untrusted networks. Instead of relying on a single coordinator, it replicates the coordinator across 3f + 1 replicas and tolerates up to f Byzantine coordinator failures. Coordinator replicas execute an adapted Byzantine agreement protocol for each transaction, while participants accept a commit or abort decision only after receiving at least f + 1 matching signed decisions, ensuring that at least one decision came from a correct coordinator replica. (arxiv.org)
The central mechanism is a decision certificate containing signed participant-registration records and signed participant votes. The certificate binds the proposed outcome to a particular transaction and allows backup replicas to verify that the primary’s proposal is consistent with the known participant set and votes. The protocol combines this certificate with Byzantine-agreement phases analogous to pre-prepare, prepare, and commit. The authors provide informal arguments for three safety properties: a committed transaction must include all correct participants and their commit votes; correct coordinator replicas must agree on one outcome; and correct participants must terminate atomically.
The protocol assumes authenticated communication and unforgeable digital signatures. It places stronger restrictions on the initiator and on the behavior that can be tolerated from participants than on coordinator replicas: arbitrary Byzantine coordinator faults are addressed, whereas only selected participant behaviors—such as sending conflicting votes—are covered. Liveness additionally depends on bounded message and processing delays, with increasing timeouts used during view changes. The implementation integrates the protocol with the Kandula WS-AtomicTransaction framework, Apache Axis, and WSS4J. In the reported 20-server testbed, the prototype added approximately 200–400 milliseconds of latency as the number of participants increased from two to ten, while end-to-end latency increased by roughly 20–30% relative to the signed-message 2PC comparison.
The paper was published in DASC 2007, held in Columbia, Maryland, on September 25–26, 2007. (dblp.org) A closely related academic follow-on is Honglei Zhang’s 2007 Cleveland State University thesis, which expands the approach into a broader Byzantine-fault-tolerant coordination framework covering transaction activation, registration, completion, and distributed commit; it retains the decision-certificate idea and incorporates the mechanisms into a WS-AT framework. (engagedscholarship.csuohio.edu) Another later research effort, “Azvasa,” investigates Byzantine-fault-tolerant distributed commit with proactive recovery and proposes reducing agreement phases and message overhead. (scixplorer.org) The search found evidence of continued academic development of Byzantine-tolerant transaction coordination, but no reliable evidence of direct production-industry adoption of this specific BFTDC protocol.