Zyzzyva: Speculative Byzantine Fault Tolerance
Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, 2007 · paper · Computer science
Presents Zyzzyva, a protocol using speculation to cut the cost and simplify the design of Byzantine fault tolerant replication. Replicas respond without first agreeing on order, and clients detect inconsistencies, bringing replication overheads near their theoretical minima.
Checked: PDF from cs.cornell.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
6 findings
Substance Zyzzyva fault-free bottleneck cost: Table 1 prints "2+3f/b" (MAC ops at bottleneck server), but §5.3 prints "2+(3f+1) cryptographic operations" and §5.4 "2+ (3f+1)/b".
- p. 2 Table 1, Throughput row, Zyzzyva column
2+3f/b
- p. 11 Section 5.3
Zyzzyva requires 2+(3f +1) cryptographic oper-
- p. 11 Section 5.4
creases from 2+ 3f+1
- p. 11 Section 5.3, first paragraph
Zyzzyva requires 2+(3f +1) cryptographic operations
Only the authors can say what is right here.
Judge's note: Table 1 on p2 has the bold entry 2+3f/b. On p11, §5.3 and §5.4 both give 3f+1. Table 1 says "MAC ops" and the text says "cryptographic operations", but the paper never says these are different counts. The Table 1 footnote defers to TR [17], which is not among the files. At f=1, b=1 the two forms give different values. Only the authors can say which form is intended.
Second check: another model agreed
Report a problem with this finding
Substance PBFT fault-free bottleneck cost: Table 1 prints "2+(8f+1)/b", while §5.3 prints "2 + (10f + 1) cryptographic operations" and §5.4 "PBFT uses 2 + (10f+1)/b operations in both this scenario and fault-free".
- p. 2 Table 1, Throughput row, PBFT column
2+(8f+1)/b
- p. 11 Section 5.3
2 + (10f + 1) cryptographic operations
- p. 11 Section 5.4
PBFT uses 2 + 10f+1
- p. 11 Section 5.3, first paragraph
compared to 2 + (10f + 1) cryptographic operations for PBFT
Only the authors can say what is right here.
Judge's note: Seen on p2 (Table 1) and p11. The gap is 2f, which grows with f, and nothing in the paper reconciles the two forms. The 16% figure in §5.4 (Zyzzyva 3+(5f+1)/b against PBFT at f=1, b=10) is reached with 10f+1 but not with 8f+1. Table 1 defers to TR [17], which is not among the files.
Second check: another model agreed
Report a problem with this finding
Reference or label Figure 1(b) labels the commit phase with steps "5" and "6", but the caption says "The numbers refer to the main steps of the protocol numbered in the text" and the text has no steps 5 or 6 (the commit phase is steps 4b.1 and 4b.2).
- p. 3 Figure 1(b) and caption
The numbers refer to the main steps of the protocol numbered in the text.
- p. 6 Section 3.2 step headings
4b.1.
Judge's note: The p3 image of Figure 1(b) shows labels 1, 2, 3, 4b, 5, 6. Searching the text for step headings finds only 1, 2, 3, 4, 4a, 4b, 4b.1, 4b.2, 4c, 4d. Page 4 also says that the numbers in Figure 1 correspond to the numbers in the text.
Second check: another model agreed
Report a problem with this finding
Reference or label "completes in three one-way message exchanges as in Figure 2(a)" should point to Figure 1(a) (gracious execution); Figure 2 is "State maintained at each replica" and has no panel (a).
- p. 4 Section 3, paragraph introducing §4.1
three one-way message exchanges as in Figure 2(a)
- p. 4 Section 3 overview, last paragraph
completes in three one-way message exchanges as in Figure 2(a)
Judge's note: Seen on the p4 image. Figure 2's caption, in the text at line 548, is "State maintained at each replica". The gracious-execution pattern is Figure 1(a) (p3).
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [32] lists the authors as "V. Prabhakaran, L. Bairavasundaram, N. Agrawal, H. G. A. Arpaci-Dusseau, and R. Arpaci-Dusseau." "H. G. A. Arpaci-Dusseau" looks like two authors (H. S. Gunawi and A. C. Arpaci-Dusseau) merged into one name.
- p. 14 Reference [32]
H. G. A. Arpaci-Dusseau, and R. Arpaci-Dusseau.
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the IRON File Systems (SOSP 2005) author list includes H. S. Gunawi and A. C. Arpaci-Dusseau. The p14 image confirms the entry is printed as "H. G. A. Arpaci-Dusseau"; this is not an extraction artefact.
Second check: another model agreed
Report a problem with this finding
Wording §5.2: "each replica verifies 4f + 1 MACs (1 to authenticate the client and 4f+1 to validate the OHS state)": the parts sum to 4f+2, not 4f+1; the parallel clause uses "1 ... and 4f".
- p. 10 Section 5.2, description of Q/U implementation
each replica verifies 4f + 1 MACs (1 to authenticate the client and 4f +1 to validate the OHS state)
Judge's note: Seen on the p10 image. The total and its parts are in the same sentence. The parallel clause for generated MACs gives 1 + 4f = 4f+1, which points to 4f as the intended OHS term. Worked at f=1.
Second check: another model agreed
Report a problem with this finding
19 minor (typos and the like; most checked by the judge only)
Wording Intro states that compared to "PBFT [9, 33, 41], Q/U [3], and HQ [10], Zyzzyva ... increases peak throughput by a factor of two to an order of magnitude", but §5.1 reports batched PBFT at 59K vs Zyzzyva 86K ops/sec ("The 45% difference").
- p. 2 Section 1, top of left column
increases peak throughput by a factor of two to an order of magnitude for demanding workloads
- p. 10 Section 5.1
The 45% difference between Zyzzyva and PBFT’s
- p. 10 Section 5.1
The 45% difference between Zyzzyva and PBFT’s peak throughput
- p. 12 Sec 5.4
outperform PBFT by 43% with batching
Only the authors can say what is right here.
Judge's note: Text on p2 and p10. The factor of 2 holds against unbatched PBFT (2.7x), Q/U (>3x) and HQ (>9x), but not against batched PBFT (about 1.46x). The sentence does not limit the claim to those cases, so the wording overstates. The 43% vs 45% sub-point is not a defect: the 43% (§5.4, p12) is a comparison under failures (Figure 8), a different measurement from the fault-free 86K/59K. The 45% is also close to 86/59.
Second check: another model agreed
Report a problem with this finding
Wording §1.1 says "the metrics that depend on f grow as slowly or more slowly in Zyzzyva as in any other protocol", but §5.3 says "message counts at the primary for Zyzzyva, Zyzzyva5, and PBFT increase as f increases, while server message counts are constant with f for Q/U and HQ".
- p. 2 Section 1.1, right column
the metrics that depend on f grow as slowly or more slowly in Zyzzyva as in any other protocol
- p. 11 Section 5.3, right column
message counts at the primary for Zyzzyva, Zyzzyva5, and PBFT increase as f increases, while server message counts are constant with f for Q/U and HQ
Judge's note: Seen on p2 and p11. The intro claim probably refers to the Table 1 metrics (replicas, MAC ops), where it holds. As worded, though, it is unqualified, and the paper's own message-count metric in Figure 7/§5.3 grows with f for Zyzzyva and not for Q/U or HQ. §5.3 notes that multicast would change this, but the figure does not use multicast.
Second check: another model agreed
Report a problem with this finding
Wording "Note that cases 4b and 4c are not exclusive of 4d; a client may receive messages sufficient to complete a request or form a commit certificate and also a proof of misbehavior": the explanation describes cases 4a (complete) and 4b (commit certificate), not 4c.
- p. 6 End of step 4d
Note that cases 4b and 4c are not exclusive of 4d; a client may receive messages sufficient to complete a request or form a commit certificate
Only the authors can say what is right here.
Judge's note: Seen on the p6 image. Case 4c is defined as fewer than 2f+1 matching responses followed by a resend. That case neither completes a request nor forms a certificate, so the case labels do not match the explanation that follows them. The authors could mean that 4c leads to completion after the resend, so this is left as a query.
Second check: another model agreed
Report a problem with this finding
Wording "we scale reported performance up by 7.5% to account for our use of 3.0 GHz rather than 2.8GHz machines": the clock-speed ratio is about 7.1%.
- p. 10 Section 5, paragraph 2
we scale reported performance up by 7.5% to account for our use of 3.0 GHz rather than 2.8GHz machines
Only the authors can say what is right here.
Judge's note: Seen on the p10 image. 3.0/2.8 gives 1.071. The paper gives no other scaling rule, so the authors should say how they derived 7.5%. The difference is small.
Second check: another model agreed
Report a problem with this finding
Wording Sec 5.2: "Figure 4 shows the latencies of Zyzzyva, Zyzzyva5, Q/U, and PBFT" leaves out HQ (and Unreplicated), although Figure 4 plots HQ bars and the next paragraph discusses HQ.
- p. 10 Sec 5.2
Figure 4 shows the latencies of Zyzzyva, Zyzzyva5, Q/U,
- p. 13 Conclusion
approach the theoretical lower bounds for any BFT protocol
Judge's note: The full p10 image shows Figure 4 with HQ and Unreplicated bars for every benchmark, so the list in the text is incomplete. The second part of the finding, that the Conclusion overclaims "approach the theoretical lower bounds", is a summarising claim and a matter of interpretation. It is not counted as a defect here.
Second check: another model agreed
Report a problem with this finding
Wording Appendix VC5: "Upon receipt of 2f+1 matching view-confirm messages, replica i begins the new view v." Steps VC2–VC4 define the new view as v+1 (view-change, new-view and view-confirm messages carry v+1).
- p. 14 Appendix, VC5
replica i begins the new view v.
Judge's note: Checked p14 image and text. VC2 says "commits to a view change into view v+1", VC3 says "initial state for view v + 1", and VC4's view-confirm carries v+1. So in VC5 "the new view v" conflicts with the notation fixed in the earlier steps. The pedantic details that follow use v generically, so this is a notation slip and the protocol is unaffected.
Second check: another model agreed
Report a problem with this finding
Typo Duplicated word in Introduction para 1: "the growing value of data and and falling costs of hardware".
- p. 1 Section 1, paragraph 1
the growing value of data and and falling costs of hardware
- p. 1 Introduction, first paragraph
the growing value of data and and falling costs
- p. 1
st, the growing value of data and and falling costs of ha
Judge's note: The page 1 image shows "and and" in the middle of a line, so it is not a line-break artefact.
Second check: code check
Report a problem with this finding
Typo Subject–verb disagreement: "mounting evidence of non-fail-stop behavior in real systems [...] suggest that BFT may yield" should read "suggests".
- p. 1 Section 1 Introduction, right column, top
36, 39, 40] suggest that BFT may yield significant benefits
Judge's note: Page 1 shows that the subject is "mounting evidence", which is singular. The verb is printed as "suggest".
Second check: none (judge only)
Report a problem with this finding
Typo Safety condition SAF says "any request that completes with a higher sequence number n′ ≥ n": the word "higher" disagrees with the non-strict ≥.
- p. 3 Safety condition saf
higher sequence number n′ ≥n
- p. 3 saf condition
higher sequence number n′ ≥n has a history
- p. 8 §3.4.1 Part 2
hn is a prefix of hn′ for n < n′
Judge's note: Seen on the p3 image. The case n′ = n is trivially true, so the condition is not affected. Only the wording and the symbol disagree, and §3.4.1 uses n < n′.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling in §2: "many real-word applications" should be "real-world".
- p. 3 Section 2, paragraph 3
many real-word applications
- p. 3 Section 2 System Model
real-word
Judge's note: Visible in the p3 image.
Second check: none (judge only)
Report a problem with this finding
Typo Step 4b.2 heading: "Client receives a LOCAL-COMMIT messages from 2f + 1 replicas" has a singular article with a plural noun.
- p. 6 Step 4b.2 heading
Client receives a local-commit messages
Judge's note: Visible in the boxed heading on the p6 image.
Second check: none (judge only)
Report a problem with this finding
Typo Figure 3 and Figure 8 captions both read "as the number of client varies"; it should be "clients".
- p. 10 Figure 3 caption
as the number of client varies
- p. 11 Figure 8 caption
as the number of client varies
Judge's note: Seen in both captions on the page images (p10 Figure 3, p11 Figure 8).
Second check: none (judge only)
Report a problem with this finding
Typo Sec 5.1: "The 45% difference between Zyzzyva and PBFT's peak throughput are largely accounted for PBFT's higher cryptographic overhead" is missing "by" and has a subject–verb disagreement (difference ... are).
- p. 10 Section 5.1
are largely accounted for PBFT’s higher
Judge's note: Verified on the p10 image. The intended meaning is clear from context, so this is a copy-editing fix.
Second check: none (judge only)
Report a problem with this finding
Typo "replicas continue to execute request speculatively" (p12) and "simply replies to client request over an authenticated channel" (p10) are missing a plural or an article ("requests").
- p. 12 Section 6 Related Work, last line of right column
replicas continue to execute request speculatively, without
- p. 10 Section 5.1 end
simply replies to client request over an authenticated channel
- p. 12 Related work
replicas continue to execute request speculatively
Judge's note: Both phrases verified on the page images. The p12 instance clearly needs "requests", as in the parallel "requests with lower sequence number". The p10 instance is a looser article/plural slip.
Second check: none (judge only)
Report a problem with this finding
Typo Sec 5.3: "Figures 7 shows the number of cryptographic operations" should read "Figure 7 shows".
- p. 11 Section 5.3, paragraph 3
Figures 7 shows the number of cryptographic operations
- p. 11 §5.3
Figures 7 shows
Judge's note: Verified on the p11 image.
Second check: none (judge only)
Report a problem with this finding
Typo Sec 6: "In particular, Zyzzyva fast agreement protocol is based on recent work on fast Paxos" lacks a possessive or article ("Zyzzyva's").
- p. 12 Section 6 Related Work, right column
lar, Zyzzyva fast agreement protocol is based on recent work
- p. 12 Section 6
Zyzzyva fast agreement protocol is based
Judge's note: Verified on the p12 image. Using "Zyzzyva" as an attributive noun is possible, but the sentence reads as if the possessive was dropped; elsewhere the paper writes "Zyzzyva's protocol".
Second check: none (judge only)
Report a problem with this finding
Typo Reference [30] gives the first author as "D. Openheimer, A. Ganapathi, and D. Patterson."
- p. 13 Reference [30]
D. Openheimer, A. Ganapathi, and D. Patterson.
- p. 13 References [30]
D. Openheimer, A. Ganapathi
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the first author of the USITS 2003 paper is David Oppenheimer (double p). The p13 image confirms the printed spelling "Openheimer".
Second check: none (judge only)
Report a problem with this finding
Typo Acknowledgements: "source code for PBFT, HQ, and QU respectively" uses "QU", while the rest of the paper writes "Q/U".
- p. 13 Acknowledgements
HQ, and QU respectively.
- p. 13 Section 8 Acknowledgements
HQ, and QU respectively
Judge's note: Verified on the p13 image. Every other mention in the paper (Sec 5, Figures 3–5, Sec 6) uses Q/U.
Second check: none (judge only)
Report a problem with this finding
Typo Appendix VC3: "grows exponentially with the number view changes that fail in succession" is missing "of".
- p. 14 Appendix, VC3 Additional Pedantic Details
grows exponentially with the number view changes that fail in succession
Judge's note: Verified on the p14 image.
Second check: none (judge only)