A Generic Efficient Biased Optimizer for Consensus Protocols

Roy Friedman; Yehonatan Buchnik

REVIEW 3 major objections 5 minor 23 references

A Generic Efficient Biased Optimizer for Consensus Protocols

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims a generic wrapper can make any consensus protocol terminate in a single all-to-all round whenever all nodes propose the same preferred value and no Byzantine failures occur, while preserving crash, Byzantine, and…

desk verdict The Byzantine thresholds (f<n/4 classical, f<n/3 external validity) are genuinely new and the counting arguments hold, but the generic wrapper's fallback path rests on an unproven late-participation assumption and the lower bound is too narrow to support the claimed optimality. read the letter →

arxiv 1908.02675 v1 pith:XO3O4FQE submitted 2019-08-07 cs.DC

Yehonatan Buchnik , Roy Friedman This is my paper · ORCID

classification cs.DC

keywords consensusoptimisticsinglecommunicationroundByzantinefaulttolerancecrashfailuresexternalvalidityfastpathbiasedvalue

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Consensus normally costs several communication rounds, even when the network and all nodes are well behaved. This paper claims that any consensus protocol can be wrapped in a biased fast path: if every node starts with the same distinguished value and no Byzantine failures occur, the wrapper decides in one all-to-all round and never runs the slower base protocol. If the fast path fails, the wrapper falls back to the base protocol while keeping its safety and liveness. The resilience depends on the failure model: crashes up to f

What carries the argument

The load-bearing object is the biased fast path together with its AdoptionCriteria. The optimizer chooses a distinguished preferred value v before the run; the fast path succeeds when the first n-f proposals a node sees are all v, and the adoption criterion is a threshold that lets a node safely fall back to the base protocol while still proposing v. The criterion is calibrated to the failure model so that if any node can decide fast, every other correct node's received set intersects enough v votes to drive it into the base protocol with v: at least one v for crashes, f+1 instances of v for Byzantine classical validity, and one valid v for external validity. This intersection argument is what transfers agreement and validity from the base protocol to the whole construction. A second load-bearing mechanism is the line requiring an already-decided node to invoke the base protocol with v once it detects that fallback has happened.

What would settle it

Take any candidate base consensus protocol that is correct only when every node calls Propose exactly once, wrap it with the optimizer, and run an execution in which one node decides v in the optimistic phase while another node falls back to Propose. If the base protocol deadlocks, makes an invalid decision, or violates agreement in that run, then the claim that the optimizer works for any consensus protocol fails; a user can run this same test per candidate before deployment.

Watch

Extended reading notes

Core claim

The central construction is Algorithm 1, a v-biased optimizer. Each node broadcasts its proposal, waits for n-f replies, and decides v immediately if every reply is v. Otherwise it consults an AdoptionCriteria: at least one v in the crash model, at least f+1 instances of v under classical Byzantine validity, or a valid v under external validity; if the criterion holds it feeds v to the underlying consensus protocol, and otherwise it feeds its own proposal. Any node that already decided v and later sees the base protocol being invoked joins it with v, so the base protocol has enough participants. The paper proves that for each model the intersection of the n-f received sets forces every correct node that did not decide fast to propose v, which makes the final decision v; the arguments establish termination, validity, and agreement while reusing the base protocol's correctness. Because the fast path only uses point-to-point messages and values, the Byzantine instantiations need only oral messages rather than signatures, and the proof-aware variant can postpone broadcasting cryptographic proofs until a fallback is needed. The accompanying lower bound shows that with n=3f+1 and classical validity, no asynchronous Byzantine protocol can guarantee one-round termination after receiving only n-f messages, even with a preferred value and no failures.

Load-bearing premise

The load-bearing assumption is that the base consensus protocol stays correct and live even when a node that has already decided v on the optimistic path later calls the base protocol's Propose with v; the paper invokes this step but does not prove that every black-box consensus protocol supports post-decision participation.

Editorial extensions

If this is right

Any existing consensus protocol, whether synchronous, asynchronous, or oracle-assisted, can be given a one-round fast path without changing its internal logic; only the wrapper needs to know the preferred value.
In leader-based blockchains where the common case is accepting the leader's block, the fast path turns the normal-case decision into a single round among replicas.
The Byzantine-resilience results mean the classical-validity version needs more than 3f+1 nodes (n>4f), while the external-validity version reaches the usual n=3f+1 threshold.
If the base consensus protocol keeps its correctness properties when joined after a decision, the wrapper is generic; users only need to supply the preferred value and the adoption criterion.
When valid values carry large cryptographic proofs, the proof-aware variant can skip sending proofs in the fast path and only exchange them on fallback, reducing common-case message size.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A user applying the wrapper to a concrete base protocol must verify that invoking Propose(v) after a node has already decided is safe; the paper leaves that as an interface assumption, so in practice the optimizer is black-box only modulo that property.
The lower bound implies that any attempt to reach n=3f+1 resilience in the classical-validity setting must either wait for more than n-f messages, use synchrony or timeouts, or weaken the decision guarantee; the paper sketches a timeout-based variant but does not analyze it fully.
For blockchain deployments, this suggests a simple common-case acceleration: bias toward accepting the leader's block, and only pay the cost of a full consensus round when voting disagrees; adversarial cases can cause fallback but not safety violation if the base protocol's assumptions hold.
The same wrapper could be applied at multiple layers of a state-machine replication stack, such as per-round block acceptance and cross-shard agreement, as long as each layer's preferred value is known in advance; testing this is a natural next step not explored in the paper.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Short version: the Byzantine part is the real news, and it is mostly right. The generic wrapper that biases consensus toward a preferred value and terminates in one round when everyone starts with that value and no Byzantine failures occur is a clean idea. For benign failures it reproduces the f

Now the soft spots, in proportion. The biggest one is exactly what your stress-test flagged: Line 14. The termination lemmas all reduce to 'if at least one node invokes the base consensus, then by Line 14 all nodes invoke it.' But for a node that already decided v optimistically and returned, Line 14 requires it to later learn that another node invoked the base protocol and then call Consensus.Propose(v) after already deciding. The paper never specifies the interface of the black-box consensus protocol, nor proves that an already-decided correct process can join an in-progress consensus invocation without breaking correctness or liveness. Standard consensus algorithms assume all correct processes start at a common protocol beginning; a late starter can miss round 1 and either look absent or operate at an inconsistent round. So the claim that this works for 'any consensus protocol' is not established. The optimistic fast path is unaffected; the gap is only in fallback executions, but those are exactly where correctness matters.

The second issue is the lower bound in Section 5. It only rules out n=3f+1, with a specific message-delivery pattern. It does not rule out other resiliency levels, so the paper's claim of 'optimal resiliency' is unsupported. The authors even mention a synchronous workaround that works for f

There are minor issues too: a few typos, the 'proof aware' variant deserves more than 'the proof is essentially the same,' and the related-work discussion could be tighter. But those are minor.

Who is this for? People working on optimistic BFT and blockchain consensus. The Byzantine thresholds are a real step beyond [14], and the wrapper abstraction is useful even if it needs a caveat about which base protocols it applies to. I would not cite it as-is because of the Line 14 gap, but I would send it to a serious referee. It deserves review, not desk rejection; the core idea is sound and the Byzantine results are publishable once the interface assumption is made explicit and either proven or scoped out.

Referee Report

3 major / 5 minor

Summary. The paper proposes a generic 'biased optimizer' (Algorithm 1) that takes an arbitrary consensus protocol and produces an optimized protocol which, when all nodes start with a predetermined preferred value v and no Byzantine failures occur, terminates optimistically in one all-to-all round. The optimizer is instantiated for benign failures with f<n/2, for Byzantine failures with classical validity with f<n/4, and for external validity with f<n/3; a proof-aware variant (Algorithm 2) reduces the optimistic-phase message size when values carry large proofs. Section 5 claims a lower bound showing that, for n=3f+1, no asynchronous Byzantine consensus protocol can guarantee single-round termination after receiving only n-f messages even with a preferred value. The paper's central correctness proofs rely on a black-box base consensus and on Line 14, which makes an already-decided node invoke the base protocol late if any other node invoked it.

Significance. The fast-phase counting arguments are clean and, under the stated adoption criteria, the agreement and validity arguments are correct. The modular optimizer idea is valuable: if the interface question is resolved, it would turn any late-join-friendly consensus protocol into one with one-round favorable-case termination using only oral messages. The paper is also honest about the price of a bad guess, namely additional communication rounds. However, the universal claim over 'any consensus protocol' is not supported by the proofs, and the lower bound as stated does not establish the claimed optimality of f<n/4. These issues are load-bearing; with a carefully stated interface assumption and a corrected lower-bound statement, the work would be a useful contribution.

major comments (3)

[§4.1, Algorithm 1, Lines 13–14; Lemmas 4.2.1, 4.3.1, 4.4.1] The termination proofs all reduce to the statement that if at least one node invokes the base consensus protocol, then by Line 14 all nodes invoke it once, and termination follows from the base protocol. This requires that a correct node that has already decided optimistically and returned can later call Consensus.Propose(v) and have that call contribute to a base protocol whose correctness assumes that all participants begin together and remain active until decision. That is not a property of every consensus protocol; a late starter may have missed the first round of a round-based or leader-based protocol, and its messages may be ignored or violate the protocol's synchrony assumptions. The paper never defines the interface of the black-box consensus protocol, nor proves that every consensus protocol supports this late-participation pattern. Please either prove this closure property or add an explicit assumption/interface requirement and restrict the 'any consensus protocol' claim accordingly.
[§5, Theorem 5.0.1] The lower bound is proved for n=3f+1, i.e., f=(n-1)/3, whereas the classical-validity instantiation is claimed for f<n/4 and is described in the introduction as having 'optimal resiliency.' The theorem does not address f≥n/4 and therefore does not establish optimality of the f<n/4 threshold. The contradiction only rules out one-round termination at the n=3f+1 point, which is outside the claimed range. Please state precisely what Theorem 5.0.1 implies, or provide a lower bound for f≥n/4 (e.g., n=4f) if optimality of f<n/4 is intended. As written, the optimality claim is unsupported.
[§4.4.2, Algorithm 2, Lines 8–10 and 15–17] If some correct nodes decide in Line 6 and return while others proceed to Line 8, the non-deciding nodes wait at Line 10 for |fullvals|=n-f. A decided node is not specified to send its proof after returning, so unless a background handler for decided nodes is explicitly assumed, the wait cannot be satisfied and the proof-aware variant can deadlock. Please specify the life cycle of decided nodes in this variant and provide a liveness argument; the sentence 'the proof is essentially the same as in Section 4.4.1' does not cover this different communication pattern.

minor comments (5)

[§3] The heading 'F ailure Modesl' contains a typo and should read 'Failure Modes and Resiliency.'
[Abstract] The phrase 'optimizer than can' should be 'optimizer that can.'
[§5] 'Always works at the paste of the slowest node' should be 'at the pace of the slowest node.'
[§4.1, Algorithm 1, Lines 13–14] The mechanism by which a decided node detects that another node invoked Consensus.Propose is not defined; please specify a background message handler or an event exposed by the base-protocol interface.
[Abstract and §3] The claim that the optimizer works 'regardless of the network timing assumptions' is too broad, since the optimistic phase still requires eventual delivery of messages between correct nodes; this should be stated more precisely.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the optimizer is a reduction to a black-box consensus protocol with an explicit preferred value, and the proofs rely on the base protocol's assumed guarantees rather than on the conclusion they establish.

full rationale

The paper's derivation chain is a standard modular reduction. Algorithm 1 wraps a black-box consensus protocol, and the correctness proofs (Lemmas 4.2.1-4.2.3, 4.3.1-4.3.3, 4.4.1-4.4.3) invoke the base protocol's termination, agreement, and validity as hypotheses, not as consequences of the optimizer's own behavior. The preferred value v is a design input, not a fitted parameter; no quantity is trained, calibrated, or derived from the target result. The adoption criteria are chosen by counting arguments (e.g., f < n/2, f < n/4, f < n/3) and are not defined in terms of the optimized protocol's output. Self-citations such as [7], [13], and [14] appear only in related-work and application motivation; they are not load-bearing for the main theorems. A genuine interface concern exists at Algorithm 1, Line 14, where a node that has already decided v must later invoke the base consensus protocol with v; the paper does not prove that every consensus protocol permits late participation by an already-decided node. However, this is an unstated interface assumption and a possible correctness gap, not a circularity: the base protocol's guarantees are not equivalent to the optimizer's conclusion, and Line 14 is an algorithmic construction rather than an imported theorem. Since no derivation step reduces by definition, self-citation, or fitted input to its own input, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central claim rests on standard distributed-systems assumptions: network integrity, eventual delivery, a black-box base consensus protocol with the stated properties, and for the external-validity case, three explicit assumptions. No free parameters or invented entities are introduced.

assumptions (6)

domain assumption Network integrity: messages delivered were sent by claimed sender and content is not corrupted.
Stated in Section 3; needed to prevent impersonation and message modification.
domain assumption During the optimizing phase, messages between correct nodes are eventually delivered.
Stated in Section 3; ensures termination of the wait in Line 3.
domain assumption The base consensus protocol satisfies its stated termination, agreement, and validity properties.
Used as a black box in all instantiations; the optimizer inherits correctness from it.
domain assumption For Byzantine classical validity, the base protocol satisfies Byzantine validity (if all correct propose same value, only it can be decided).
Assumed in Lemma 4.3.2 and 4.3.3.
domain assumption For external validity, Assumptions 1-3 hold: correct nodes' values are valid, the base protocol satisfies classical validity, and either binary consensus or the base protocol satisfies external validity.
Stated in Section 4.4.1; necessary for the f<n/3 instantiation.
domain assumption No Sybil attacks; a node cannot impersonate another.
Stated in Section 3; required for oral messages to provide authentication.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Generic Efficient Biased Optimizer for Consensus Protocols." pith.science (2026). https://pith.science/paper/XO3O4FQE

@misc{pith2026190802675,
  author       = {Pith},
  title        = {Pith review of: A Generic Efficient Biased Optimizer for Consensus Protocols},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/XO3O4FQE}},
  note         = {Machine review of arXiv:1908.02675}
}

abstract

Consensus is one of the most fundamental distributed computing problems. In particular, it serves as a building block in many replication based fault-tolerant systems and in particular in multiple recent blockchain solutions. Depending on its exact variant and other environmental assumptions, solving consensus requires multiple communication rounds. Yet, there are known optimistic protocols that guarantee termination in a single communication round under favorable conditions. In this paper we present a generic optimizer than can turn any consensus protocol into an optimized protocol that terminates in a single communication round whenever all nodes start with the same predetermined value and no Byzantine failures occur (although node crashes are allowed). This is regardless of the network timing assumptions and additional oracle capabilities assumed by the base consensus protocol being optimized. In the case of benign failures, our optimizer works whenever the number of faulty nodes $f<n/2$. For Byzantine behavior, our optimizer's resiliency depends on the validity variant sought. In the case of classical validity, it can accommodate $f<n/4$ Byzantine failures. With the more recent external validity function assumption, it works whenever $f<n/3$. Either way, our optimizer only relies on oral messages, thereby imposing very light-weight crypto requirements.

Figures

Figures reproduced from arXiv: 1908.02675 by the authors.

**Figure 2.** A worst case scenario for the Byzantine failure model with classic validity and f < n/4. If some node p decides after receiving n − f votes for v, then any other node q must receive at least f + 1 votes for v. same value (v). Similarly, if all nodes decide by invoking the base consensus protocol in Lines 9 or 11, then by the agreement property of this protocol all nodes decide on the same value. Hence, the only pot… view at source ↗

**Figure 3.** A worst case scenario for the Byzantine failure model with external validity and f < n/3. If some node p decides after receiving n − f votes for v, then any other node q must receive at least one vote for v. As shown in [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Setup for lower bound proof. the other nodes is not received by p1 until after time t 1 1 to be defined shortly. The f Byzantine processes send to p1 the same messages they would have generated in P had they been started with v (so Byzantine failures do not manifest i…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 22 canonical work pages

[5]

F. V. Brasileiro, F. Greve, A. Most´ efaoui, and M. Raynal. Consensus in One Communication Step. In Proceedings of the 6th International Conference on Parallel Computing Technologies , PaCT, pages 42–50. Springer-Verlag, 2001

work page 2001
[14]

Friedman, A

R. Friedman, A. Mostefaoui, and M. Ray- nal. Simple and Eﬃcient Oracle-Based Consen- sus Protocols for Asynchronous Byzantine Sys- tems. IEEE Trans. Dependable Secur. Comput. , 2(1):46–56, Jan. 2005

work page 2005
[1]

Abd-El-Malek, G

M. Abd-El-Malek, G. R. Ganger, G. R. Good- son, M. K. Reiter, and J. J. Wylie. Fault-scalable Byzantine Fault-tolerant Services. In Proceed- ings of the 20th ACM Symposium on Operating Systems Principles , SOSP, pages 59–74, 2005

work page 2005
[2]

Attiya and J

H. Attiya and J. Welch. Distributed Comput- ing: Fundamentals, Simulations and Advanced Topics (2nd edition) . John Wiley Interscience, March 2004

work page 2004
[3]

Aublin, R

P.-L. Aublin, R. Guerraoui, N. Kneˇ zevi´ c, V. Qu´ ema, and M. Vukoli´ c. The Next 700 BFT Protocols. ACM Trans. Comput. Syst. , 32(4), Jan. 2015

work page 2015
[4]

Birman and R

K. Birman and R. Friedman. Trading Consis- tency for Availability in Distributed Systems. Technical Report TR96-1579, Computer Science Department, Cornell University, Apr. 1996

work page 1996
[6]

E. Buchman. Tendermint: Byzantine Fault Tol- erance in the Age of Blockchains. Master’s the- sis, University of Guelph, 2016

work page 2016
[7]

FireLedger: A High Throughput Blockchain Consensus Protocol

Y. Buchnik and R. Friedman. TOY: a To- tal ordering Optimistic sYstem for Permissioned Blockchains. CoRR, abs/1901.03279, January

work page Pith review arXiv 1901

Show all 23 references

[8]

Cachin and M

C. Cachin and M. Vukolic. Blockchain Consensus Protocols in the Wild. CoRR, abs/1707.01873, 2017

2017 arXiv
[9]

Castro and B

M. Castro and B. Liskov. Practical Byzantine Fault Tolerance. In Proceedings of the 3rd ACM Symposium on Operating Systems Design and Implementation, OSDI, pages 173–186, 1999

1999
[10]

Cowling, D

J. Cowling, D. Myers, B. Liskov, R. Rodrigues, and L. Shrira. HQ Replication: A Hybrid Quo- rum Protocol for Byzantine Fault Tolerance. In Proceedings of the 7th Symposium on Operat- ing Systems Design and Implementation , OSDI, pages 177–190. USENIX Association, 2006

2006
[11]

Crain, V

T. Crain, V. Gramoli, M. Larrea, and M. Ray- nal. DBFT: Eﬃcient Leaderless Byzantine Con- sensus and its Application to Blockchains. In 17th IEEE International Symposium on Network Computing and Applications (NCA) , 2018

2018
[12]

M. J. Fischer, N. A. Lynch, and M. S. Paterson. Impossibility of Distributed Consensus with One Faulty Process. J. ACM , 32(2):374–382, Apr. 1985

1985
[13]

Friedman, A

R. Friedman, A. Most´ efaoui, S. Rajsbaum, and M. Raynal. Asynchronous Agreement and Its Relation with Error-Correcting Codes. IEEE Trans. Computers, 56(7):865–875, 2007

2007
[15]

Keidar and S

I. Keidar and S. Rajsbaum. On the Cost of Fault-Tolerant Consensus When There Are No Faults - A Tutorial. In Dependable Comput- ing, First Latin-American Symposium (LADC) , pages 366–368, 2003

2003
[16]

Kotla, L

R. Kotla, L. Alvisi, M. Dahlin, A. Clement, and E. Wong. Zyzzyva: Speculative Byzantine Fault 10 Tolerance. SIGOPS Oper. Syst. Rev. , 41(6):45– 58, Oct. 2007

2007
[17]

L. Lamport. The Part-time Parliament. ACM Trans. Comput. Syst., 16(2):133–169, May 1998

1998
[18]

Lamport, R

L. Lamport, R. Shostak, and M. Pease. The Byzantine Generals Problem. ACM Trans. Pro- gram. Lang. Syst. , 4(3):382–401, July 1982

1982
[19]

Martin and L

J.-P. Martin and L. Alvisi. Fast Byzantine Con- sensus. IEEE Trans. on Dependable and Secure Computing, 3(3):202–215, July 2006

2006
[20]

Mostefaoui, S

A. Mostefaoui, S. Rajsbaum, and M. Raynal. Conditions on Input Vectors for Consensus Solv- ability in Asynchronous Distributed Systems. J. ACM, 50(6):922–954, Nov. 2003

2003
[21]

M. Raynal. Fault-Tolerant Message-Passing Dis- tributed Systems – an Algorithmic Approach . Springer International Publishing, 2018

2018
[22]

Schneier

B. Schneier. Applied Cryptography : Protocols, Algorithms and Source Code in C . John Wiley & Sons Inc, December 2015

2015
[23]

Y. Yeh. Safety Critical Avionics for the 777 Pri- mary Flight Controls System. In 20th Digital Avionics Systems Conference (DASC) , 2001. 11

2001

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [5]

F. V. Brasileiro, F. Greve, A. Most´ efaoui, and M. Raynal. Consensus in One Communication Step. In Proceedings of the 6th International Conference on Parallel Computing Technologies , PaCT, pages 42–50. Springer-Verlag, 2001

work page 2001

[2] [14]

Friedman, A

R. Friedman, A. Mostefaoui, and M. Ray- nal. Simple and Eﬃcient Oracle-Based Consen- sus Protocols for Asynchronous Byzantine Sys- tems. IEEE Trans. Dependable Secur. Comput. , 2(1):46–56, Jan. 2005

work page 2005

[3] [1]

Abd-El-Malek, G

M. Abd-El-Malek, G. R. Ganger, G. R. Good- son, M. K. Reiter, and J. J. Wylie. Fault-scalable Byzantine Fault-tolerant Services. In Proceed- ings of the 20th ACM Symposium on Operating Systems Principles , SOSP, pages 59–74, 2005

work page 2005

[4] [2]

Attiya and J

H. Attiya and J. Welch. Distributed Comput- ing: Fundamentals, Simulations and Advanced Topics (2nd edition) . John Wiley Interscience, March 2004

work page 2004

[5] [3]

Aublin, R

P.-L. Aublin, R. Guerraoui, N. Kneˇ zevi´ c, V. Qu´ ema, and M. Vukoli´ c. The Next 700 BFT Protocols. ACM Trans. Comput. Syst. , 32(4), Jan. 2015

work page 2015

[6] [4]

Birman and R

K. Birman and R. Friedman. Trading Consis- tency for Availability in Distributed Systems. Technical Report TR96-1579, Computer Science Department, Cornell University, Apr. 1996

work page 1996

[7] [6]

E. Buchman. Tendermint: Byzantine Fault Tol- erance in the Age of Blockchains. Master’s the- sis, University of Guelph, 2016

work page 2016

[8] [7]

FireLedger: A High Throughput Blockchain Consensus Protocol

Y. Buchnik and R. Friedman. TOY: a To- tal ordering Optimistic sYstem for Permissioned Blockchains. CoRR, abs/1901.03279, January

work page Pith review arXiv 1901