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 fail-stop failures are possible.

If the condition above holds, our system will provide the correct output. This is ensured by having the minimum number of non-faulty nodes present in the system, depending on the respective failure types. For Byzantine failures, we need a majority, which means more than half of the total nodes. Therefore, any integer greater than $P(\tau)/2$. We only need one non-faulty node for fail-stop failures, which ...