Protocols for Maintaining Fault Tolerance: Part II

So far we’ve just discussed removing faulty elements and haven’t yet explored adding repaired or new elements to the system. Let's see how we can successfully integrate a new or repaired component into a system of state machine replicas.

Integrating repaired elements

It is not enough for the element being added to be non-faulty. It must also be in the right state to behave consistently with other components. Let's start by introducing some notation:

We define $e[r_i]$ as the state of a non-faulty element e after processing request $r_0$ through $r_i$. An element $e$ that joins a configuration after request $r_{join}$ must be in the state $e[r_{join}]$ for it to behave consistently after joining so it may successfully become part of the system.

An element is self-stabilizing if its current state is completely defined by a fixed number of previously processed inputs, say $k$ inputs. For such elements, all we need to do is ensure that the element runs long enough to process $k$ inputs and will be in state $e[r_{join}]$. For non-self-stabilizing elements, we need to do things differently. In the following discussion, we will discuss two such cases:

Logical clocks and fail-stop failures

When using logical clocks and assuming only fail-stop failures, we only require the state of a state machine replica $sm_i$. The state of $sm_i$ will be correct since we know that $sm_i$ is non-faulty. Let's consider the following three cases in which the integrated element is an output device, a client, or a state machine replica: