Classic Byzantine Fault Tolerance says you can survive lying nodes if honest nodes outnumber them 2:1. PBFT is the algorithm that made this idea practical in 1999 — instead of exponential message complexity, it does consensus in three fixed rounds with a designated primary. It's the ancestor of every modern BFT protocol (Tendermint, HotStuff, Istanbul BFT, and by extension most permissioned blockchains).

The setup: n replicas, up to f of them Byzantine (arbitrary faults, including malicious). PBFT needs n ≥ 3f + 1. Why? A quorum needs 2f+1 replicas to guarantee overlap with any other quorum in at least f+1 nodes — enough that at least one honest node bridges any two decisions.

The three rounds after a client sends a request to the primary:

• Pre-prepare: Primary assigns a sequence number and broadcasts the request to all backups.
• Prepare: Every backup that accepts the pre-prepare broadcasts a PREPARE message to everyone. A replica considers itself "prepared" once it has 2f matching PREPARE messages (plus its own pre-prepare) — this locks the sequence number.
• Commit: Once prepared, each replica broadcasts a COMMIT. After receiving 2f+1 matching COMMITs, it executes the request and replies to the client. The client waits for f+1 matching replies to know the result is real.

If the primary is faulty (times out, sends conflicting pre-prepares), backups run a view change: they broadcast VIEW-CHANGE with their prepared state, and the next primary (chosen round-robin) collects 2f+1 of these to reconstruct the log and resume.

Concrete example: Hyperledger Fabric's ordering service used PBFT variants for years. With 4 nodes, you tolerate 1 Byzantine node — one lying orderer can't force a bad block, because the honest 3 form a quorum that excludes it. Bump to 7 nodes for f=2. Note the cost: O(n²) messages per consensus round because every replica talks to every other in prepare and commit phases. This is why PBFT stops scaling past ~20 nodes and why HotStuff replaced the all-to-all pattern with a leader-collected threshold signature (O(n) messages).

Rule of thumb: if your replica count is n, you tolerate ⌊(n-1)/3⌋ Byzantine failures. 4 nodes → 1 lie. 7 nodes → 2 lies. 10 nodes → 3 lies. Below 4 nodes, BFT is impossible: there's no quorum that guarantees an honest majority overlap.

Use PBFT when you have a small, permissioned set of participants who don't trust each other (consortium blockchains, cross-organization settlement, high-value financial state machines) and can afford the message overhead for cryptographic certainty.