Abstract
Byzantine quorum safety relies on correct replicas refusing to sign conflicting values. A replica that loses its protocol state during recovery but retains its identity and signing key may forget an earlier vote. We study certificates formed by matching signed votes from at least $q$ of $n$ replicas, assuming that each correct replica avoids conflicting votes between recoveries. If two conflicting certificates form, their overlap has size between $2q-n$ and $b+c$, where $b$ counts Byzantine replicas and $c$ counts correct identities that recovered during the execution considered. Our main result decomposes the slack $b+c-(2q-n)$ into four nonnegative counts: extra signers in the first certificate, extra signers in the second, identities in neither certificate, and Byzantine or recovering identities outside their overlap. Zero slack forces an exact signer partition. With $n=3f+1$ replicas, threshold $q=2f+1$, at most $f$ Byzantine replicas, and exactly one correct recovery event, any conflicting pair forces exactly $f$ Byzantine replicas, all in the overlap together with the recovered replica; each certificate has a disjoint side of $f$ correct replicas. A minimal protocol attains this form. We distinguish certificate formation from acceptance, give a sufficient check using configured fault and recovery caps, and explain why durable vote records written before signature release prevent the conflict.
Keywords
Subject
Publication details
- Journal
- Not available
- Open access
- Green open access
Cite this article
APA 7
Mallick, A., & Chebolu, I. (2026). When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT. https://omanscience.com/en/articles/when-can-stateless-recovery-defeat-byzantine-quorum-safety-a-tight-normal-form-for-single-step-bft
MLA 9
Mallick, Arnab, and Indraveni Chebolu. "When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT." https://omanscience.com/en/articles/when-can-stateless-recovery-defeat-byzantine-quorum-safety-a-tight-normal-form-for-single-step-bft.
Chicago (author–date)
Mallick, Arnab, and Indraveni Chebolu. 2026. "When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT." https://omanscience.com/en/articles/when-can-stateless-recovery-defeat-byzantine-quorum-safety-a-tight-normal-form-for-single-step-bft.
Harvard
Mallick, A. and Chebolu, I. (2026) 'When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT', Available at: https://omanscience.com/en/articles/when-can-stateless-recovery-defeat-byzantine-quorum-safety-a-tight-normal-form-for-single-step-bft.
Vancouver
Mallick A, Chebolu I. When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT. https://omanscience.com/en/articles/when-can-stateless-recovery-defeat-byzantine-quorum-safety-a-tight-normal-form-for-single-step-bft
IEEE
A. Mallick, and I. Chebolu, "When Can Stateless Recovery Defeat Byzantine Quorum Safety? A Tight Normal Form for Single-Step BFT," https://omanscience.com/en/articles/when-can-stateless-recovery-defeat-byzantine-quorum-safety-a-tight-normal-form-for-single-step-bft.