Protocols for Maintaining Fault Tolerance: Part I

Our protocols for $t$ fault tolerance in a system provide us with a guarantee that our system will not fail if no more than $t$ replicas fail. With this guarantee, we must ensure that the number of faulty nodes in an ensemble of replicas does not exceed $t$. We can do this by replacing faulty replicas with non-faulty replicas. Let's formally discuss this.

Modeling replica replacement

We define $P(\tau)$ as the total number of nodes running state machine replicas in an ensemble of replicas and $F(\tau)$ as the number of faulty nodes in that ensemble at time $tau$. $P(\tau) - F(\tau)$ must be greater than a certain number to guarantee that our system will produce the correct output. Here is how we can formally define this combining condition:

Here, $Enuf = P(\tau)/2$ when Byzantine failures are possible. And $Enuf = 0$ when only ...