Practical byzantine fault tolerance and proactive recovery
Paper: Practical byzantine fault tolerance and proactive recovery. Miguel Castro, and Barbara Liskov. 2002
PBFT definition
This is a customization of the standard SMR definition.
State Machine Description
- The state machine is \(\langle \mathcal{S}, \mathcal{U}, \mathcal{O}, \mathcal{O}', g, s_{0}\rangle\)
- Here \(\mathcal{S}\) is the space of all valid states
- \(s_0\) is the initial state
- \(\mathcal{U}\) is the space of all clients (users)
- \(\mathcal{O}\) and \(\mathcal{O}'\) is the space of all inputs and outputs respectively
Safety
The safety property offered by PBFT is a relaxed form of linearizability tolerating Byzantine clients where the system behaves as a centralized implementation that executes operations atomically one at a time.
Liveness
We guarantee liveness (i.e., clients eventually receive replies to their requests), provided at most \(\lfloor(n-1)/3\rfloor\) replicas are faulty and \(delay(t )\) does not grow faster than \(t\) indefinitely. This is a rather weak synchrony assumption that is likely to be true in any real system provided network faults are eventually repaired and denial-of-service attacks eventually stop, yet it enables us to circumvent the impossibility result.
Notes
- It is an [BROKEN LINK: 7d0c07ad-f65b-4664-8474-e5f703bd3bdb].
- It is in the [BROKEN LINK: 399a7a0c-20a7-4ca6-9683-c3699b480bc5] model.
- It is [BROKEN LINK: ca894ba8-5da4-4bd1-8e43-cc42d31685d6].
- The SMR definition is [BROKEN LINK: 09067bfa-56a6-4bda-ae14-d657ac5874d4]
- Modified form of linearizability from Maurice and Hehrily.
- The protocol is Fair The PBFT protocol ensures fairness by ensuring that clients get replies to their requests even when there are other clients accessing the service. A non-faulty primary assigns sequence numbers using a FIFO manner. Backups maintain the requests in a FIFO queue and they only stop the view-change timer when the first request in their queue is executed; this prevents faulty primaries from giving preference to some clients while not processing requests from others.