Algorithm

The normal execution path is primarily derived from the PBFT paper. As in the paper, we assume that the system asynchronous and distributed where nodes are connected by a network. The network may fail to deliver messages, delay them, duplicate them, or deliver them out of order, however we do assume it is secure (uses TLS). We use a Byzantine failure model, i.e., faulty nodes may behave arbitrarily.

The algorithm is used to implement a deterministic replicated service with a state. Clients issue requests to the replicated service and wait for a reply. The replicated service is implemented by n replicas (nodes). The algorithm provides both safety and liveness assuming no more than replicas are faulty.

The nodes move through a succession of configurations called views. In a view one node is the leader and the others are followers. Views are numbered consecutively. The leader of a view is node i such that , where v is the view number. View changes are carried out when it appears that the leader has failed.

The next figure is taken from the PBFT paper and it shows the operation of the algorithm in the normal case. Replica 0 is the leader, replica 3 is faulty, and C is the client.

The client sends its request to all nodes (instead of sending only to the leader to help prevent censorship). Clients' requests are batched together and the leader starts a three-phase protocol. The three phases are pre-prepare, prepare, and commit. The pre-prepare and prepare phases are used to totally order requests sent in the same view even when the leader, which proposes the ordering of requests, is faulty. The prepare and commit phases are used to ensure that requests that commit are totally ordered across views.

In the prePrepare phase, the leader batches requests to create a proposal, and it then assigns a sequence number to the proposal. Next the leader sends a prePrepare message to all followers containing the proposal, its sequence number and the current view number v.

A follower accepts the prePrepare message if the proposal is valid, it is in view v, it is expecting that sequence number, and it has not accepted a different prePrepare message for view and sequence number.