Reaching Consensus in the Byzantine Empire: A Comprehensive Review of BFT Consensus Algorithms

1 INTRODUCTION

• The taxonomy groups surveyed algorithms as more efficient, more robust, or more available, with subcategories reflecting distinct characteristics.The categories cover replication efficiency, security and fairness, and availability or responsiveness under different network conditions.Source: §1 · pp. 1–2
• Varied failure and network assumptions, inconsistent complexity criteria, and scarce intuitive protocol descriptions make BFT algorithms increasingly difficult to understand.The survey aims to help readers understand, analyze, and evaluate state-of-the-art approaches.Source: §1 · p. 2
• Each survey describes system models and service properties, distinctive features, and leader-based or leaderless consensus workflows.Leader-based approaches are divided into replication and leadership consensus; leaderless approaches into replication and conflict resolution.Source: §1 · p. 3
• The paper focuses on core consensus mechanisms, unlike earlier surveys spanning blockchain platforms, Proof-of-X protocols, or broader BFT topics.It also compares message and time complexities and supplies visual workflow summaries for the surveyed protocols.Source: §1 · pp. 2–3

2 BACKGROUND

• The comparison table notes that Zyzzyva has O(n) message complexity only on its optimal path and O(n^2) otherwise.DAG-Rider and Narwhal have a minimum time complexity of five rounds.Source: §2 · p. 4
• Consensus coordinates multiple state machines so they compute the same result and provide a unified system view despite failures.State machines model replicas providing services through state variables and commands.Source: §2 · pp. 3–4
• BFT servers may behave arbitrarily, including changing messages or state, and faulty servers may collude.This differs from benign failures, where message content is immutable and state changes are detectable.Source: §2 · p. 4
• A Byzantine quorum certificate collects identical messages, and its minimum size is 2f+1 among n=3f+1 nodes.The quorum must retain at least f+1 non-faulty nodes even if f faulty nodes are included.Source: §2 · p. 4
• Synchronous networks have known delivery and clock bounds, asynchronous networks have neither, and partial synchrony uses bounds that are unknown or known only after GST.Message complexity counts messages; time complexity counts message-passing rounds.Source: §2 · p. 5
• An f-resilient BFT consensus algorithm must satisfy termination, agreement, and validity; correctness is also framed as safety and liveness.Termination means non-faulty servers eventually decide; agreement excludes conflicting decisions, while safety and liveness describe what must not and must happen.Source: §2 · p. 5

3.1.3 The view-change protocol

• Figure 2 depicts PBFT message passing during normal operation and view changes in a four-replica system.The view change begins when a backup’s timer expires after it waits for a request to commit.Source: Figure 2 · p. 6, §3.1.3 · p. 8

3.1.1 System model and service properties

• PBFT provides safety with at most f faulty replicas among n=3f+1 without network synchrony, but liveness requires bounded message delays.The survey’s efficient-algorithm coverage also includes approaches reducing message complexity, using multiple leaders, or enabling DAG-based pipelines.Source: §3 · p. 5, §3.1.1 · p. 6

3.1.2 The replication protocol

• PBFT replication commits each request through ordered phases, quorum predicates, client replies, and periodic checkpoints.A client can rebroadcast a timed-out request to replicas when its link to the primary is unreliable, increasing request-phase messaging from O(1) to O(n); stable checkpoints allow stale log entries to be discarded.Source: §3.1.2 · pp. 6–8

3.1.3 The view-change protocol

• After a primary failure, PBFT advances to a new view; replicas’ differing asynchronous replication states create difficult view-change corner cases.The new primary selects a checkpoint and carries forward uncommitted requests seen by a quorum, after which backups validate the decision before normal operation resumes.Source: §3.1.3 · p. 8

3.1.4 Pros and cons

• PBFT influenced later BFT algorithms and was adopted by permissioned blockchains, but its quadratic messaging complexity hinders large-scale use.Faulty clients using inconsistent request authenticators may also trigger repeated view changes without progress.Source: §3.1.4 · p. 8

3.2.1 System model and service properties.

• SBFT tolerates f Byzantine and c crashed or straggler servers with 3f + 2c + 1 servers, using threshold signatures for linear messaging.Its fast path applies with no failures in a synchronous network; otherwise it switches to linear-PBFT.Source: §3.2.1 · p. 9

3.2.2 The replication protocol.

• SBFT’s fast path assigns phase coordination to primary, commit-collector, and execution-collector roles, aggregating replies with threshold signatures.The proposing client receives one confirmation message, versus f + 1 messages in PBFT.Source: §3.2.2 · p. 9

3.2.3 The view-change protocol.

• SBFT view changes collect state digests across the outstanding window before the new primary broadcasts a new view for replicas to accept or adopt safe values.A view change can incur O(n^2) messages; the window bounds the slots considered despite differing stable sequence numbers.Source: §3.2.3 · p. 10

3.2.4 Pros and cons.

• SBFT achieves linear messaging in normal operation, but faulty clients can trigger unnecessary view changes by sending requests to f + 1 replicas excluding the primary.Those replicas may time out and initiate a change that replaces a correct primary.Source: §3.2.4 · p. 10

3.3.1 System model and service properties.

• HotStuff tolerates up to f Byzantine servers among 3f + 1, with safety independent of synchrony and liveness under partial synchrony.It offers optimistic responsiveness, rotates primaries for chain quality, and can require O(f*n) rounds in the worst case of cascading failed primaries.Source: §3.3.1 · p. 10

3.3.2 The replication protocol.

• HotStuff’s four replication phases use 2f + 1 votes to form quorum certificates before replicas decide and execute a request.The phases are prepare, pre-commit, commit, and decide; replicas also update viewNum and send confirmation to the client.Source: Figure 4 · p. 10, §3.3.2 · p. 11

3.3.3 The view-change protocol.

• HotStuff rotates the primary each view; the next primary gathers 2f + 1 new-view messages and extends the highest preceding view represented by their prepareQCs.If it cannot gather the quorum in time, replicas time out and initiate another rotation.Source: §3.3.2 · p. 11, §3.3.3 · p. 11

3.3.4 Pros and cons.

• HotStuff’s threshold-signature pipelining supports linear message transmission, but frequent primary rotation can sharply reduce throughput when assigned primaries fail.Each failed server cannot achieve consensus when assigned primary duties.Source: §3.3.4 · pp. 11–12

3.4.1 System model and service properties.

• ISS’s multi-leader protocol achieves throughput 37×, 56×, and 55× higher than PBFT, Chained HotStuff, and Raft, respectively.It assumes partial synchrony and tolerates up to f Byzantine nodes among 3f + 1.Source: §3.4.1 · p. 12

3.4.2 The replication protocol.

• ISS partitions sequence numbers into epoch segments assigned to leaders, with requests sorted into buckets so a request is proposed only once.Each leader proposes only within its segment, while multiple associated Sequenced Broadcast instances run in parallel.Source: §3.4.2 · pp. 12–13

3.4.3 Multiple Leader Selection.

• ISS permits a customizable leader-selection policy if each bucket is assigned to a segment with a correct leader infinitely often.Its described implementation uses BFTMencius; detected faulty leaders are removed and replaced under the selection policy.Source: §3.4.3 · p. 13

3.4.4 Pros and cons.

• ISS trades higher throughput and faster client responses for additional consensus latency and possible throughput setbacks after leader failures.Requests are sent to and hashed at all nodes; a failed leader must be replaced and re-propose uncommitted requests, with unbalanced request distribution worsening setbacks.Source: §3.4.4 · p. 13

3.5 DAG-Rider: All You Need is DAG

• DAG-based approaches pipeline transactions in parallel and often have a throughput advantage over PBFT and HotStuff, but separation of dissemination from consensus raises latency.The survey gives DAG message complexity as O(n^3 log(n) + nM) and minimum time complexity O(5) for a strong path.Source: §3.5 · p. 14, §3.5.4 · p. 16

3.5.1 System model and service properties.

• DAG-Rider is an asynchronous Byzantine Atomic Broadcast protocol with post-quantum safety and optimal time and message complexity.Its two layers are a round-based structured DAG for reliable dissemination and a zero-overhead protocol for independently determining message order without extra communication.Source: §3.5.1 · p. 14

3.5.2 The DAG Pipelining.

• Each node builds a round-based DAG of transaction vertices linked by strong or weak edges, advancing after receiving 2f + 1 vertices in a round.Reliable broadcast ensures DAGs eventually converge among correct nodes, and every vertex broadcast by a correct process is eventually included in their DAGs.Source: §3.5.2 · pp. 14–15

3.5.3 Consensus in DAGs.

• For each four-round wave, nodes use a perfect coin to select a leader vertex; 2f + 1 strong edges in the next round establish the leader for commitment.Vertices in the leader’s causal history are delivered in deterministic order, so a later committed leader can bring earlier linked vertices into the commit.Source: §3.5.3 · pp. 15–16

3.5.4 Pros and cons.

• The DAG serves both message dissemination and agreement, with expected commit every one and a half waves; reliable broadcast helps correct processes converge on a consistent DAG.Parallel pipelining brings throughput benefits, while the separate consensus stage increases latency.Source: §3.5.4 · p. 16

3.6 Narwhal and Tusk: A DAG-based Mempool and Efficient BFT Consensus

• Narwhal separates transaction dissemination from ordering in a DAG-based Mempool, leaving consensus to sequence a small amount of metadata; Tusk manages consensus.The Mempool handles reliable transaction dissemination, while Tusk works with Narwhal for consensus under faults or asynchrony.Source: §3.6 · p. 16

3.6.1 System model and service properties.

• With n=3f+1 nodes, Narwhal tolerates up to f failures; its Mempool provides integrity, block availability, containment, 2/3-causality, and 1/2-chain quality.Block availability means a read after a successful write at a correct party eventually returns that block.Source: §3.6.1 · p. 16

3.6.2 The DAG replication protocol.

• Narwhal adapts DAG-Rider-style block propagation but replaces Bracha broadcast with a DAG-based reliable-broadcast implementation and certificates of availability backed by 2f+1 signatures.A validator creates the certificate after collecting 2f+1 acknowledge signatures for its block, then stops broadcasting the original block.Source: §3.6.2 · pp. 16–17
• Narwhal and Tusk use three-round waves with overlapping first and third rounds of consecutive waves, yielding 4.5 rounds of consensus time complexity.Tusk selects a random leader block using the same interpretation as DAG-Rider.Source: §3.6.2 · p. 17

3.6.3 Pros and cons.

• Narwhal and Tusk show a throughput advantage over PBFT and HotStuff, but unordered Mempool delivery can raise transaction latency while blocks await multiple rounds.Transactions that have not met delivery criteria wait for more waves before the system commits a block.Source: §3.6.3 · p. 17

4.1 Aardvark: Making Byzantine fault-tolerant systems tolerate Byzantine failures

• Aardvark [24] combines signed client requests, resource isolation, and regular view changes to limit performance degradation during uncivil executions.Its rule requiring a primary to sustain at least 90% of throughput over prior views can burden correct replicas and trigger unnecessary view changes, especially under dynamic workloads.Source: §4.1.1 · p. 18, §4.1.4 · p. 19

4.2 Pompe: Byzantine ordered consensus without Byzantine oligarchy

• Pompe [102] democratically selects command order from replica preferences before using a standard consensus protocol to commit batches, adding ordering fairness to linearizability.The ordering phase selects the median timestamp from a quorum of 2f+1 preferred orders; Pompe leaves consensus and view changes to the applied protocol, making safety and liveness under some integrations unclear.Source: §4.2.2 · p. 20, §4.2.4 · pp. 20–21

4.3 Spin: Byzantine fault tolerance with a spinning primary

• Spinning rotates the primary for every client request and blacklists suspected faulty replicas, countering deliberate slowdowns that avoid triggering backup timeouts.With f faulty replicas among 3f+1, frequent rotation can theoretically reduce throughput by 33%; a merge after failure costs O(n^2) messages, though rotation also distributes coordination workload and mitigates a single-primary bottleneck.Source: §4.3 · p. 21, §4.3.3 · p. 22, §4.3.4 · p. 22

4.4.3 The view-change protocol

• Prosecutor uses escalating computation penalties in leadership competitions to suppress repeatedly misbehaving candidates while retaining linear message complexity for consensus.Candidates perform PoW-like hash computations before voting; strong computational capability among faulty replicas can prolong the period without a correct leader.Source: §4.4.1 · p. 22, §4.4.3 · p. 23, §4.4.4 · p. 23

4.5 RBFT

• RBFT [4] runs parallel PBFT instances, assigning each replica a primary role in one instance while backup instances monitor the master for slow or unfair processing.Instances initiate a master change when performance crosses configured speed or client-latency thresholds; 2f+1 instance-change messages with the same counter select a new master.Source: §4.5.1 · p. 24, §4.5.2 · p. 24, §4.5.3 · pp. 24–25

4.5.4 Pros and cons.

• RBFT’s redundancy raises its message complexity to O(2|M|(n^3 + n^2 + n)) for |M| requests, while PBFT-like O(n^2) complexity already hinders large-scale applications.Each replica runs a PBFT-like instance after the propagate phase.Source: §4.5.4 · p. 25
• In geo-distributed applications, latency differences between clients and replicas can cause a correct master to miss fairness requirements, prompting unnecessary instance changes.Backups may then replace the correct master.Source: §4.5.4 · p. 25

5 TOWARD MORE AVAILABLE BFT CONSENSUS

• Leader-based BFT can face a primary single point of failure, requiring failure detection and a view change before a replacement primary is selected.Primary servers may also become system-wide bottlenecks because they handle interactions with both clients and other servers.Source: §5 · p. 25
• Asynchronous BFT protocols are developed to operate across scenarios with varying levels of synchrony.Source: §5 · p. 25
• The section introduces reliable broadcast and binary Byzantine agreement, then surveys DBFT, Honeybadger, and the BEAT family as predominantly leaderless approaches.Source: §5 · p. 25

5.1.1 Reliable broadcast.

• Reliable broadcast proceeds through initial, echo, and ready messages; replicas deliver after n−f ready messages, with f+1 ready messages also triggering a ready broadcast.Source: §5.1.1 · p. 26, Figure 13 · p. 26
• Bracha’s reliable broadcast ensures correct replicas deliver a correct proposer’s value, or, for a faulty proposer, all deliver the same value or none deliver it.Source: §5.1.1 · p. 26

5.1.2 Binary Byzantine agreement.

• Binary agreement’s first phase rebroadcasts estimates after f+1 matching messages and records a value after 2f+1; replicas then send aux messages for their recorded values.Source: §5.1.2 · p. 26, Figure 14 · p. 27
• After receiving n−f aux messages with the same value, a replica flips a coin to decide or set its estimate for the next round; this phase requires no message exchange.Source: §5.1.2 · pp. 26–27
• When replicas propose conflicting values, their aux messages may contain both values, so no decision is made and multiple rounds may be needed.Source: §5.1.2 · p. 27
• Binary Byzantine agreement provides validity and agreement, and randomized replicas reach termination with probability 1 as the number of rounds grows.Source: §5.1.2 · p. 27

5.2.4 Pros and cons.

• DBFT tolerates f Byzantine replicas among at least 3f + 1 replicas in a partially synchronous network, but unlike HoneyBadgerBFT and BEAT it does not support asynchronous networks.Psync’s fast path can decide a binary value without the last two BA rounds and random coin flip, but DBFT still requires O(f) delays when there are f Byzantine replicas.Source: §5.2.1 · p. 27, §5.2.4 · p. 29

5.2.2 The binary Byzantine consensus, Psync.

• Psync adds phase timeouts, a weak coordinator in Phase 2 to resolve conflicts, and a Phase 3 termination condition to the underlying BA protocol.The weak coordinator is selected round-robin; if it cannot coordinate in time, replicas still send aux messages and may need another round.Source: §5.2.2 · pp. 27–28

5.2.3 DBFT protocol based on Psync.

• DBFT combines Bracha’s RBC instances for proposed values with n Psync instances that help replicas decide whether to accept the proposed data.A replica can join the corresponding Psync fast path after RBC delivery; after an instance delivers 1, replicas choose the accepted data with the smallest replica ID.Source: §5.2.3 · p. 28
• 6 rounds is DBFT’s best-case time complexity; conflicts require at least 4 extra rounds, and total message complexity is O(n^3).The best case assumes no faulty replicas and a synchronous network; it uses one RBC and n parallel fast-path Psync instances.Source: §5.2.1 · p. 27, §5.2.3 · p. 29

5.3.1 System model and service properties.

• HoneyBadgerBFT tolerates f Byzantine replicas among 3f + 1 replicas in asynchronous networks, avoiding reliance on timeout-based failure detection.The protocol uses threshold encryption to defend against censorship attacks; its stated time complexity is O(log n).Source: §5.3.1 · p. 29

5.3.2 Efficient reliable broadcast for large messages.

• Erasure coding reduces large-message RBC communication complexity from O(|B|n^2) to O(|B|n), with B denoting a data batch.The protocol uses Reed-Solomon-coded blocks and Merkle-tree checksums; a replica needs n−2f distinct echo messages to decode the batch.Source: §5.3.2 · pp. 29–30

5.3.3 Binary Byzantine Agreement with Cryptographic Common Coin.

• HoneyBadgerBFT modifies BA with a threshold-signature common coin and an additional termination condition in Phase 3.The common coin uses signature shares from at least f + 1 replicas; its share-broadcast messaging complexity is O(n^2), with O(1) rounds.Source: §5.3.3 · p. 30

5.3.4 Asynchronous common subset.

• Its asynchronous common subset runs up to n modified RBC instances and n modified BA instances in parallel, then delivers the data blocks accepted by the BA instances.Replicas wait for at least n−f BA instances to deliver 1 before setting 0 for instances without an input, and wait for completion.Source: §5.3.4 · pp. 30–31

5.3.5 The complete protocol of HoneyBadgerBFT.

• The complete protocol has three epochs: encrypt a transaction batch, agree on encrypted data through ACS, then decrypt the accepted batches using shares.Replicas retrieve each batch after collecting f + 1 decryption shares.Source: §5.3.5 · p. 31

5.3.6 Messaging complexity and batch sizes.

• The survey estimates HoneyBadgerBFT messaging complexity as O(|M|n + |c|n^3 log n), treating the O(|s|n^3) decryption-share term as negligible.It states that setting global batch size M = Ω(|c|n^2 log n) eliminates the additional per-replica overhead and achieves best throughput performance.Source: §5.3.6 · p. 32

5.3.7 Pros and cons.

• HoneyBadgerBFT reports throughput above tens of thousands of transactions per second among a hundred replicas, but latency exceeds 10s when n > 48.The survey also notes that the erasure-coding library limits n to 128 and that the protocol sacrifices latency for throughput.Source: §5.3.7 · p. 32

5.4.1 System model and service properties.

• BEAT consists of five leaderless asynchronous BFT protocols, BEAT0 through BEAT4, each targeting goals such as throughput, latency, bandwidth use, or BFT storage.The protocols draw inspiration from HoneyBadgerBFT and make performance improvements.Source: §5.4.1 · p. 32

5.4.2 BEAT0.

• BEAT0 uses labeled threshold encryption, a threshold coin clipper, and Jerasure 2.0; the latter is reported to scale beyond 128 replicas.The survey says replacing HoneyBadgerBFT’s pairing-based cryptography with TDH2 reduces encryption latency.Source: §5.4.2 · p. 32

5.4.3 BEAT1 and BEAT2.

• BEAT1 and BEAT2 use Bracha’s RBC for lower broadcast latency; BEAT2 moves labeled threshold encryption to clients and uses anonymous communication to hide client identities.The survey says BEAT2’s ordering guarantee is causal order preservation, weaker than linearizability.Source: §5.4.3 · p. 32

5.4.4 BEAT3.

• AVID-FP does not ensure every correct replica eventually receives the original data, but clients can reconstruct it from f + 1 fragments and verify it with the cross-checksum.The protocol guarantees that f + 1 correct replicas eventually receive f + 1 encoded fragments, and all correct replicas deliver the checksum.Source: §5.4.4 · p. 33
• BEAT3 outperforms HoneyBadgerBFT on throughput, latency, scalability, network bandwidth, and storage overhead in the reported evaluation.AVID-FP reduces storage from O(n|M|) to O(|M|), while its broadcast circulates data fragments only initially and then the smaller global cross-checksum.Source: §5.4.4 · p. 33

5.4.5 BEAT4.

• BEAT4’s pyramid codes support partial data recovery; the survey reports 50% bandwidth savings for read requests with approximately 10% additional storage.Latency is higher than HoneyBadgerBFT when f = 1, while BEAT4 outperforms it on all performance metrics when f > 1.Source: §5.4.5 · pp. 33–34

5.4.6 Discussion.

• BEAT0, BEAT1, and BEAT2 suit general state machine replication, whereas BEAT3 and BEAT4 are more suitable for BFT storage services.The survey qualitatively compares the protocols with HoneyBadgerBFT across throughput, latency, bandwidth, scalability, and storage space.Source: §5.4.6 · p. 34

Scalability.

• Scalability remains a practical challenge despite linear protocols, as systems must balance throughput and latency while supporting blockchain deployments across thousands of nodes.The survey identifies maintaining high throughput and low latency at large scale as an ongoing research need.Source: §6 · pp. 34–35

Ordering fairness.

• Ordering fairness matters because faulty leaders can manipulate request processing, including by favoring colluding clients and enabling front-running.The survey connects fair transaction handling to trust and impartiality in BFT applications.Source: §6 · p. 35

Post-quantum safe BFT consensus.

• Post-quantum BFT research must address consensus protocols’ reliance on cryptography and the potential vulnerability of traditional RSA and ECC to quantum computers.The survey points to post-quantum cryptography and reducing message passing as research directions.Source: §6 · p. 35

Interoperability.

• Interoperability research could support cross-chain consensus and data and asset transfer as blockchain networks and distributed systems proliferate.The survey frames scalability, robustness, and operability as practical needs for real-world BFT applications.Source: §6 · p. 35

BFT consensus for machine learning.

• Distributed and multi-agent machine learning create BFT challenges because malicious or erroneous behavior can compromise training data integrity and model updates.The survey identifies high-performance, robust BFT as relevant to defending against malicious agents and behavior.Source: §6 · p. 35

• The survey covers selected prominent algorithms from academia and industry, categorizes them as efficient, robust, or available, and qualitatively compares their time and message complexities.Source: §7 · p. 35
• Diagrams depict the message-passing workflow for a complete consensus instance.Source: §7 · p. 35
• A common survey structure explains normal operation, view changes, robustness improvements, conflict resolution, and each algorithm’s strengths and weaknesses.Source: §7 · p. 36