I have recently learned about the protocol described in the paper titled “Practical Byzantine Fault Tolerance”, as part of my university course on distributed systems. There was one example where it seemed to me a request can be committed and executed by only some but not all non-faulty replicas. The example was as follows:
There are four replicas: 0 (primary), 1, 2, and 3. The primary is Byzantine (f = 1) and sends a pre-prepare message to replicas 1 and 2. Both pre-prepare messages correspond to the same client request (or an imaginary forged request if there was never such a request to begin with). No pre-prepare message was sent to replica 3.
Now prepare stage begins, and the non-faulty replicas 1 and 2 each receive prepare messages from replicas 0, 1, and 2 (i.e. including “self-votes”). Hence, they accumulate enough (2f+1 = 3) prepare messages to precede to commit stage.
Commit stage begins, and similarly to the prepare stage, replicas 1 and 2 each receive enough messages to complete the commit stage, and execute the request. Both of them complete and reply to the client. The client receives f+1 = 2 matching replies and assumes everything is normal.
Now my problem is that this does not seem to satisfy the requirement that all non-faulty nodes agree on the same state. In particular, replicas 1 and 2 have executed the request and agree on the state, whereas replica 3 has not executed the request and thus disagrees with replicas 1 and 2.
From what I can tell this violates interactive consistency. I presume that the protocol is correct (duh), so what am I missing here?