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. 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.