Practical byzantine fault tolerance and proactive recovery

Paper: [1]

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.

_20230506_163800screenshot.png

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.

References

[1] Miguel Castro, and Barbara Liskov. 2002. “Practical byzantine fault tolerance and proactive recovery.” https://doi.org/10.1145/571637.571640.