PaperlayerView exact revision on arXiv

Source-linked AI summary

Byzantine Agreement, Broadcast and State Machine Replication with Near-optimal Good-case Latency

Ittai Abraham, Kartik Nayak, Ling Ren, Zhuolun Xiang

arXiv:2003.13155v4cs.CRcs.DC

TL;DR

The paper studies good-case latency for Byzantine agreement, broadcast, and state machine replication, where existing Byzantine protocols face a lower bound of ∆. It introduces 1∆ protocols achieving ∆+2δ latency and extends the approach to weaker synchronous models.

  • Problem

    The paper addresses how to achieve low good-case latency for BA, BB, and SMR while tolerating Byzantine faults beyond n/3; BA and BB have a ∆ lower bound at that resilience.

    Source: §1 · pp. 2–3

  • Method

    The paper proposes non-lock-step 1∆ protocols for BA, BB, and SMR, then extends them to mobile link failures and mobile sluggish faults.

    Source: §1 · p. 2, §7 · p. 17

  • Results

    The 1∆ protocols achieve ∆+2δ good-case latency, and the approach extends to weaker models with near-optimal latency.

    Source: §1 · p. 3, §7 · p. 17

  • Takeaways & Limitations

    The work uses non-lock-step execution and good-case latency to characterize BA and BB in a way the authors argue better captures practical BFT SMR.

    Source: §1 · p. 2, §7 · p. 17

    The mobile link-failure and mobile sluggish models separately describe slow or lossy links and slow replicas, with no clear way yet to unify them.

    Source: §7 · p. 17

Abstract

from arXiv · show

This paper investigates the problem \textit{good-case latency} of Byzantine agreement, broadcast and state machine replication in the synchronous authenticated setting. The good-case latency measure captures the time it takes to reach agreement when all non-faulty parties have the same input (or in BB/SMR when the sender/leader is non-faulty). Previous result implies a lower bound showing that any Byzantine agreement or broadcast protocol tolerating more than $n/3$ faults must have a good-case latency of at least $\Delta$, where $\Delta$ is the assumed maximum message delay bound. Our first result is a family of protocols we call $1\Delta$ that have near-optimal good-case latency. We propose a protocol $1\Delta$-BA that solves Byzantine agreement in the synchronous and authenticated setting with near-optimal good-case latency of $\Delta+2\delta$ and optimal resilience $f<n/2$, where $\delta$ is the actual (unknown) delay bound. We then extend our protocol and present $1\Delta$-BB and $1\Delta$-SMR for Byzantine fault tolerant broadcast and state machine replication, respectively, in the same setting and with the same good-case latency of $\Delta+2\delta$ and $f<n/2$ fault tolerance. Our $1\Delta$-SMR upper bound improves the gap between the best current solution, Sync HotStuff, which obtains a good-case latency of $2\Delta$ per command and the lower bound of $\Delta$ on good-case latency. Finally, we investigate weaker notions of the synchronous setting and show how to adopt the $1\Delta$ approach to these models.

1 Introduction

The paper reframes latency around real time and good-case progress, then introduces protocols that approach the ∆ lower bound while tolerating f < n/2 faults. It also extends the approach to two weaker synchronous models.

1 Introduction

  • The motivation distinguishes BA/BB’s traditional worst-case focus from SMR’s good case, where a stable honest leader drives multiple decisions.SMR runs continuously, committing an ever-growing sequence of values, unlike single-value BA/BB protocols that terminate after agreement.Source: §1 · p. 2
  • The paper motivates measuring latency in time rather than rounds, separating conservative ∆ from actual unknown δ, and focusing on good-case commitment.Lock-step protocols allocate ∆ to each step, potentially wasting time when ∆ is much larger than actual message delays; the good case for BA is when honest replicas share an input.Source: §1 · pp. 2–3
  • Any BA or BB protocol resilient to f ≥ n/3 faults has good-case latency at least ∆.Sync HotStuff provides a 2∆ good-case latency for BA/BB, and its authors conjectured that 2∆ was optimal; this paper refutes that conjecture.Source: §1 · p. 3
  • 1∆-BA, 1∆-BB, and 1∆-SMR achieve good-case latency ∆+2δ, with optimal resilience f < n/2 for BA and SMR.The paper says these protocols improve the gap between the upper and lower bounds for BA and BB.Source: §1 · p. 3
  • Under mobile link failures, good-case latency is 2∆+4δ with a 2∆ lower bound; under mobile sluggish faults, it is ∆+4δ.The mobile sluggish model concerns slow connections of honest replicas whose messages may exceed ∆.Source: §1 · p. 3

2 Preliminary

The preliminary section specifies the authenticated replica network and timing assumptions, then states the correctness guarantees for BA, BB, and BFT SMR.

2 Preliminary

  • The model has n replicas in a reliable authenticated all-to-all network, up to f Byzantine replicas, standard signatures, and public-key infrastructure.The notation ⟨x⟩p denotes message x signed by replica p.Source: §2 · p. 4
  • Message delay is bounded by known ∆, while actual bound δ is unknown to the protocol designer and satisfies δ ≤ ∆.Replicas proceed without lock-step execution, with clock skew bounded by σ and no assumed clock drift.Source: §2 · p. 4
  • BA requires agreement, termination, and validity; BB uses the same guarantees but requires the sender’s value when the sender is honest.For SMR, safety prevents different values at the same log position, and liveness requires every client request eventually be committed by all honest replicas.Source: §2 · p. 4

3 Byzantine Agreement/Broadcast with Near-optimal Good-case Latency

The paper presents 1∆-BA and 1∆-BB protocols with near-optimal good-case latency in the synchronous authenticated setting. Their design challenges the conjectured 2∆ lower bound by allowing asymmetric equivocation detection.

3.1 Intuition

  • The conjectured 2∆ wait assumes every replica must detect sender equivocation; 1∆-BA instead lets lagging replicas detect it while a leading replica may commit.The remaining honest replicas can later commit the same value as the leading replica, and the Byzantine-sender case need not meet the 1∆ deadline.Source: §3.1 · p. 5

3.2 1∆-BA Protocol under Synchrony

  • After forming a proposal from f + 1 signed messages, replicas forward it, wait ∆ before voting, and commit on f + 1 votes; a BA instance handles unresolved cases.In the described fallback, replicas invoke BA at 4∆ using their locked values.Source: §3.2 · p. 6

3.3 Correctness of Protocol 1∆-BA

  • A ∆-long wait before voting prevents honest replicas from voting for conflicting proposals, and forwarded votes let all honest replicas lock the committed value before fallback BA.The theorem establishes agreement, near-optimal good-case latency, and optimal resilience for 1∆-BA.Source: §3.2 · p. 7, §3.3 · pp. 7–8

3 Byzantine Agreement/Broadcast with Near-optimal Good-case Latency

  • ∆+ 2δ good-case latency with f < n/2 resilience: 1∆-BA solves Byzantine agreement in the synchronous authenticated setting.The paper identifies this resilience as optimal.Source: §3.3 · p. 8

3.4 1∆-BB under Synchrony

  • ∆+ 2δ good-case latency: 1∆-BB solves Byzantine broadcast, using the sender's signed value in proposals; its f < n/2 resilience is not optimal.The BB protocol replaces BA's input exchange with a sender broadcast and uses proposals containing only the sender's signed value.Source: §3.4 · pp. 8–9

4 State Machine Replication with Good-case Latency of ∆+ 2δ

1∆-SMR extends the paper’s low-latency approach to state machine replication, committing each proposed block in ∆+2δ time with an honest leader. Its view-based protocol is shown to preserve safety and liveness.

4 State Machine Replication with Good-case Latency of ∆+ 2δ

  • 1∆-SMR provides state machine replication with good-case latency ∆+2δ and optimal resilience f<n/2.Client requests are batched into hash-chained blocks, so committing a block also commits its ancestors.Source: §4 · p. 9

4.1 1∆-SMR Protocol under Synchrony

  • The protocol uses views with a stable leader; replicas forward valid proposals, wait ∆ before voting, and commit after collecting f+1 distinct votes.A quorum certificate consists of f+1 signatures among 2f+1 replicas.Source: §4 · p. 9, §4.1 · p. 10
  • A Byzantine leader that stalls or equivocates can trigger a view change after a quorum of replicas blames it.The new leader gathers status messages; the view-change waiting periods do not affect good-case latency with an honest leader.Source: §4.1 · p. 10

4.2 Correctness of Protocol 1∆-SMR

  • Honest replicas always commit the same block at each height, and keep committing new blocks.The section establishes safety and liveness as separate properties.Source: §4.2 · p. 12
  • ∆+2δ: in the good-case, every proposed block is committed that long after being proposed.The good-case is when an honest leader is in charge.Source: §4.2 · p. 12

5 The Mobile Link Failure Model

The paper extends its protocols to a non-lock-step model of mobile link failures using a generic message-relaying transformation. It obtains a 2∆+4δ good-case latency and proves a 2∆ lower bound for Byzantine agreement and broadcast under the stated link-failure conditions.

5 The Mobile Link Failure Model

  • 2∆+4δ: the transformed BA, BB, and BFT SMR protocols tolerate mobile link failures while retaining near-optimal good-case latency.The transformation applies to protocols designed for the synchronous model.Source: §5 · p. 12

The Mobile Link Failure Model without Lock-step Execution

  • The non-lock-step model allows directed links to fail independently and dynamically; faulty links may lose or delay messages, subject to per-replica fault-budget constraints.A recovered link continues to count against the faulty-link threshold for δ time.Source: §5 · p. 13

A generic transformation to tolerate mobile link failures under non-lock-step synchrony

  • Forwarding each received message once and doubling protocol timers simulates synchronous message delivery to all honest replicas within 2δ.The propagation guarantee is stated as a lemma.Source: §5 · p. 13

Lower bound on good-case latency under mobile link failures

  • Under the theorem’s fault and link-failure conditions, BA and BB require at least 2∆ good-case latency, even with static link failures.The lower bound is established for BA and extended to BB by an analogous proof.Source: §5 · p. 14

The mobile sluggish fault model

  • The mobile sluggish model permits some honest replicas’ messages to exceed ∆ while sluggish, assuming more than half the replicas remain honest and prompt.The paper extends 1∆-BA, 1∆-BB, and 1∆-SMR to tolerate these faults using extra communication rounds while keeping good-case latency near-optimal.Source: §5 · p. 15

The Mobile Link Failure Model without Lock-step Execution

  • Mobile link failures model adversarially controlled links that may lose or delay messages, rather than slow replicas themselves.The paper distinguishes this from mobile sluggish faults, which affect honest replicas.Source: §5 · pp. 15–16

6 Related Work

Prior work provides several contrasting approaches to Byzantine agreement, broadcast, and state machine replication. This paper distinguishes its good-case latency bounds from optimistic-case results and extends the approach to weaker network models.

Byzantine fault tolerant protocols

  • Sync HotStuff achieves 2∆ good-case latency, compared with this paper’s ∆+2δ; randomized BA/BB work instead achieves expected constant rounds.Dolev-Strong gives deterministic f+1-round broadcast and can be modified for authenticated BA when t<n/2.Source: §6 · p. 16
  • Optimistic responsiveness targets decisions at network speed O(δ) when >3n/4 votes are collected, unlike this paper’s bounds under any adversary strategy.Other low-latency work studies optimistic cases under synchrony or asynchrony.Source: §6 · p. 16

Weaker network models

  • Earlier mobile-link-failure results [30, 6, 35, 29, 7] assume lock-step execution, whereas this paper’s model and results do not require it.The paper also introduces techniques for mobile link failures and mobile sluggish faults in BA, BB, and BFT SMR.Source: §6 · pp. 16–17

7 Conclusion and Future Work

The paper presents near-optimal good-case latency protocols for BA, BB, and SMR, and extends them to mobile link failures and mobile sluggish faults. It identifies unresolved latency bounds and model limitations as future work.

7 Conclusion and Future Work

  • The proposed BA, BB, and SMR protocols achieve near-optimal good-case latency ∆+2δ, and extensions cover mobile link failures and mobile sluggish faults.The paper advocates non-lock-step models and good-case latency as measures for BA and BB relevant to practical BFT SMR.Source: §7 · p. 17
  • For n/3≤f<n/2, closing the gap between the ∆+2δ upper bound and ∆ lower bound remains open.Tight good-case latency bounds outside this fault range are also an open question.Source: §7 · p. 17
  • The mobile-link transformation increases communication complexity because other replicas relay messages; direct protocol design may avoid this blowup.Source: §7 · p. 17
  • The mobile link failure and mobile sluggish models cover slow or lossy links and slow replicas, respectively, and the paper offers no clear way to unify them.A unified model and protocols for it are proposed as future work.Source: §7 · p. 17

A Lower Bound on the Good-case Latency under Synchrony

The section restates a lower bound: Byzantine agreement and broadcast protocols tolerating at least n/3 faults require good-case latency of at least Δ. Its proof uses indistinguishable executions to show that a shorter latency would violate agreement.

A Lower Bound on the Good-case Latency under Synchrony

  • Any Byzantine agreement or broadcast protocol resilient to f ≥ n/3 faults must have good-case latency at least Δ.The section restates the lower bound from.Source: A Lower Bound on the Good-case Latency… · p. 20
  • For Byzantine agreement, three executions make replicas in groups P and Q commit different values within Δ, violating agreement.In the two good-case executions, silent Byzantine groups leave honest replicas with uniform inputs; in the mixed execution, replicas in P and Q cannot distinguish their local views before Δ.Source: A Lower Bound on the Good-case Latency… · p. 20
  • The broadcast lower bound follows by an analogous three-scenario argument, with a Byzantine sender sending different values to P and Q.The sender's messages are delivered instantaneously; the remainder of the proof follows the Byzantine-agreement argument.Source: A Lower Bound on the Good-case Latency… · p. 20

B Missing Proofs

Lemma 4 ensures that when a block extending a chain is certified, every honest replica receives that chain before entering the next view.

B Missing Proofs

  • If block Bl extending chain C is certified in view v, all honest replicas receive every block in C before entering view v + 1.An honest voter has the chain before voting and forwards it; an earlier view change would deliver a blame certificate in time to prevent that vote.Source: B Missing Proofs · p. 21

B.1 Proof for Lemma 2

The proof establishes that a directly committed block cannot be contradicted by another certified block in its view, and that certified blocks in later views must extend it. Timed forwarding and view-change rules preserve the chain and certificate information needed for this safety argument.

B.1 Proof for Lemma 2

  • No equivocating block can also be certified in the committed block's view, because an honest voter would learn of the conflict before voting.The proof considers both orders of honest votes: each forwarded proposal arrives in time to prevent the other vote.Source: §B.1 · p. 21
  • A certified block in a later view must equal or extend the directly committed block, whose chain and certificate reach honest replicas before they enter the next view.The proof uses the view-change waiting period to prevent replicas from advancing before receiving the committed block's certificate.Source: §B.1 · pp. 21–22
  • The highest certified block remains equal to or extends the committed block in the next view, so proposals can be certified only if they extend it.Whether the proposal carries status messages or S = ⊥, the voting rule preserves this extension property; induction carries it into every future view.Source: §B.1 · pp. 21–22

B.2 Proof of Theorem 5

The liveness proof shows that honest leaders avoid view changes and keep proposing blocks that honest replicas commit. It gives a bound for committing multiple blocks and explains how view changes handle Byzantine leaders.

B.2 Proof of Theorem 5

  • An honest leader receives honest replicas' status messages after waiting 2Δ, proposes a block extending the highest certified block, and avoids a view change as honest replicas keep voting.Lemma 4 ensures replicas have the required chain before entering the view.Source: §B.2 · p. 22
  • 6Δ + (p − 1)α time suffices for an honest replica to commit p blocks after entering a new view.The first block takes 6Δ; subsequent proposals are committed in a pipeline with one proposal every α time.Source: §B.2 · p. 22
  • Equivocation or proposals that arrive too slowly trigger a view change for a Byzantine leader; a timely commit can keep replicas committing unless a blame certificate triggers that change.A commit certificate broadcast by an honest replica can sustain progress, but a blame certificate leads all honest replicas to change views.Source: §B.2 · pp. 22–23

C Results for Mobile Sluggish Faults

The mobile sluggish fault model captures temporary violations of the message-delay bound at honest replicas, which can threaten the forwarding checks used by the protocols. The paper extends 1∆-SMR to tolerate these faults and says similar approaches apply to 1∆-BA and 1∆-BB.

C Results for Mobile Sluggish Faults

  • Temporary message-delay violations at honest replicas can threaten protocol correctness because forwarded proposals help honest replicas detect conflicting proposals.The synchronous model’s delay bound is crucial to this detection mechanism.Source: C Results for Mobile Sluggish Faults · p. 23
  • The authors extend 1∆-SMR to tolerate mobile sluggish faults and state that similar approaches apply to 1∆-BA and 1∆-BB.They present the SMR extension as an illustration of the technique.Source: C Results for Mobile Sluggish Faults · p. 23

C.1 The Mobile Sluggish Fault Model

In the mobile sluggish fault model, honest replicas can be sluggish or prompt, and the sluggish set can change over time. The model requires more than half of replicas to be honest and prompt at every time.

C.1 The Mobile Sluggish Fault Model

  • An honest replica may be sluggish or prompt at a given time, and messages involving sluggish replicas may be delayed beyond the assumed bound ∆.A message from a replica prompt at t1 reaches every replica prompt at t2 ≥ t1 + ∆.Source: §C.1 · p. 23
  • The sluggish set may change over time, but the number of honest and prompt replicas must always exceed n/2.With n = 2f + 1, at least f + 1 replicas are honest and prompt at any time.Source: §C.1 · p. 23

C.2 Protocol 1∆-SMR-MSF

1∆-SMR-MSF adapts 1∆-SMR to the mobile sluggish model by adding communication steps that require multiple messages before replicas proceed. The protocol preserves safety and liveness and achieves ∆+4δ good-case latency per command with resilience f < n/2.

C.2 Protocol 1∆-SMR-MSF

  • The protocol replaces each Forward, Vote, and Blame step with two communication steps, and replicas proceed after receiving f + 1 corresponding messages.This threshold ensures at least one message is from an honest, prompt replica despite sluggish replicas’ delayed messages.Source: §C.2 · pp. 23–24
  • Certification of a block extending a chain ensures f + 1 honest replicas have received that chain before entering the next view; a certified block ranking no lower than a directly committed block must equal or extend it.These properties support carrying committed history across view changes.Source: §C.2 · p. 24
  • Honest replicas always commit the same block at each height, and keep committing new blocks while all honest replicas stay prompt.These are the stated safety and liveness properties.Source: §C.2 · p. 27
  • 8∆+(p −1)α time suffices to commit p blocks after entering a new view under the stated liveness analysis.After the first block, proposals arrive every α time and are committed in a pipeline; an honest leader has sufficient time not to equivocate.Source: §C.2 · p. 27
  • ∆+4δ good-case latency per command and resilience f < n/2 are the stated guarantees of 1∆-SMR-MSF.When all honest replicas stay prompt and the leader is honest, a proposed value is committed in ∆+4δ time.Source: §C.2 · p. 28
Loading 2003.13155v4…