Practical Byzantine Fault Tolerance
Operating Systems Design and Implementation, 1999 · paper · Computer science
Presents a replication algorithm that tolerates Byzantine (arbitrary) faults and works in asynchronous settings like the Internet. A Byzantine-fault-tolerant NFS service built with it was measured as only 3% slower than standard unreplicated NFS.
Checked: PDF from css.csail.mit.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
2 findings
Reference or label Section 4.3 says "the digest can be computed using incremental cryptography [1] as discussed in Section 6.3"; the incremental digest (AdHash [1]) is described in Section 6.4, "Computing Checkpoint Digests".
- p. 5 Section 4.3, right column
can be computed using incremental cryptography [1] as discussed in Section 6.3
- p. 10 Section 6.3 / 6.4
we discuss how the digest is computed in Section 6.4
- p. 5 Section 4.3, Garbage Collection, paragraph after the checkpoint proof
incremental cryptography [1] as discussed in Section 6.3
- p. 10 Section 6.4 heading and text
snfsd uses an incremental collision-resistant one-way hash function called AdHash [1]
Judge's note: Section 6.3 on p10 (Maintaining Checkpoints) covers copy-on-write and itself says "we discuss how the digest is computed in Section 6.4". Section 6.4 describes AdHash [1] and the incremental update. The pointer should read 6.4.
Second check: another model agreed
Report a problem with this finding
Reference or label Reference [2] reads "Journal of the ACM, 32(4), 1995.", while [9] gives "Journal of the ACM, 32(2), 1985."
- p. 14 References, [2]
Journal of the ACM, 32(4), 1995.
- p. 14 References, [9]
Journal of the ACM, 32(2), 1985.
- p. 14
Protocols. Journal of the ACM, 32(4), 1995.
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: Bracha & Toueg's paper appeared in J. ACM 32(4) in 1985. Within the files, the p14 reference list dates J. ACM volume 32 to 1985 in [9] and to 1995 in [2], so the two entries contradict each other. The year in [2] is probably 1985.
Second check: another model agreed
Report a problem with this finding
5 minor (typos and the like; most checked by the judge only)
Wording Figure 2 labels the replicas "replica 0" to "replica n". Section 4 numbers replicas {0,...,|R|−1}, and n is used for the number of replicas (n − f, n > 3f), so the last label would be n−1.
- p. 9 Figure 2
replica n
- p. 3 Section 4, left column
identify each replica using an integer in {0,...,|R|−1}
Judge's note: Checked the Figure 2 crop and p3. Section 3/4 uses n as the replica count and numbers replicas from 0 to |R|−1. The figure label is a loose schematic and conflicts slightly with that notation.
Second check: another model agreed
Report a problem with this finding
Wording Table 3, phase 4, BFS strict is printed "8.77 (32%)" against NFS-std 6.60; the printed times give 32.9%.
- p. 12 Table 3, phase 4, strict column
8.77 (32%)
Only the authors can say what is right here.
Judge's note: Checked Table 3 on the p12 image. Every other percentage in Table 3 matches normal rounding of the printed times (35%, 20%, 19%, -69%, -73%, -2%, -16%, 3%). Even the rounding bounds 8.765/6.605 give 32.7%. Only the authors can say whether 32% comes from unrounded data or is a slip.
Second check: another model agreed
Report a problem with this finding
Typo The commit-phase paragraph ends "and the sequence number is between h and H" with no closing period.
- p. 4 Section 4.2, last line of right column
and the sequence number is between h and H
Judge's note: On the p4 image the last line of the right column ends with H and has no period. The parallel sentence in the prepare paragraph ends "between h and H." with a period. Page 5 opens a new indented paragraph ("We define the committed ..."), so the sentence does not continue there.
Second check: none (judge only)
Report a problem with this finding
Typo "e.g," lacks its second period twice: "specific invariants, e.g, the invariant" (p8, Section 5.2) and "(e.g,[2, 3, 24])" (p13, Section 8).
- p. 8 Section 5.2, right column top
specific invariants, e.g, the invariant
- p. 13 Section 8, second paragraph
(e.g,[2, 3, 24])
Judge's note: Both places are visible in the page images. Elsewhere the paper writes "e.g.," (for example "e.g., to remove a faulty primary" on p13).
Second check: none (judge only)
Report a problem with this finding
Typo Reference [3] prints the author as "R. Canneti and T. Rabin."
- p. 14 References, [3]
R. Canneti and T. Rabin.
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: the author's surname is spelled Canetti (Ran Canetti). The p14 image shows "Canneti", so this is not an extraction artefact.
Second check: none (judge only)