is taken by P1 after it has received m0, therefore, the dependency on P0 is captured by C1. Similarly, the dependency of P2 on P1 is also preserved by the checkpoint C2 taken by P2. Such a global state is an example of consistent global state. Of course, the execution after the checkpoints, such as the sending and receiving of m2 and m3, will be lost upon recovery.
The scenario described in Figure 2.2(c) is the most subtle one. In this scenario, P0 takes a checkpoint after it has sent message m0 while P1 takes a checkpoint before it receives m0 but after it has sent m1, and P2 takes a checkpoint before it receives m1. This means that the checkpoint C0 reflects the state change resulting from sending m0 whereas C1 does not incorporate the state change caused by the receiving of m0. Consequently, this set of checkpoints cannot be used to recover the system after a failure because m0 and m1 would have been lost. However, the global state reconstructed by using such a set of checkpoints would still be qualified as a consistent global state because it is one such that it could have happened, i.e., messages m0 and m1 are still in transit to their destinations. To accommodate this scenario, an additional type of states, referred to as channel state, is introduced as part of the distributed system state [5].
To define the channel state properly, it is necessary to provide a more rigorous (and abstract) definition of a distributed system. A distributed system consists of two types of components [5]:
◾ A set of N processes. Each process, in turn, consists of a set of states and a set of events. One of the states is the initial state when the process is started. Only an event could trigger the change of the state of a process.
◾ A set of channels. Each channel is a uni-directional reliable communication channel between two processes. The state of a channel is the set of messages that are still in transit along the channel (i.e., they have not yet been received by the target process). A TCP connection between two processes can be considered as two channels, one in each direction.
A pair of neighboring processes are always connected by a pair of channels, one in each direction. An event (such as the sending or receiving of a message) at a process may change the state of the process and the state of the channel it is associated with, if any. For example, the injection of a message into a channel may change the state of the channel from empty to one that contains the message itself.
Using this revised definition, the channel states in the third scenario would consist of the two in-transit messages m0 and m1. If the channel states can be properly recorded in addition to the checkpoints in this scenario, the recovery can be made possible (i.e., m0 will be delivered to P1 and m1 will be delivered to P2 during recovery).
2.1.3 Piecewise Deterministic Assumption
Checkpoint-based protocols only ensure to recover the system up to the most recent consistent global state that has been recorded and all executions happened afterwards, if any, are lost. Logging can be used to recover the system to the state right before the failure, provided that all events (that could potentially change the state of the processes) are logged and the log is available upon recovery. This is what is referred to as the piecewise deterministic assumption [21]. According to this assumption, all nondeterministic events can be identified and sufficient information (referred to as a determinant [1]) must be logged for each event. The most obvious example of nondeterministic events is the receiving of a message. Other examples include system calls, timeouts, and the receipt of interrupts. In this chapter, we typically assume that the only nondeterministic events are the receiving of a message. Note that the sending of a message is not a deterministic event, i.e., it is determined by a nondeterministic event or the initial state of the process [7].
2.1.4 Output Commit
A distributed system usually receives message from, and sends message to, the outside world, such as the clients of the services provided by the distributed system. Once a message is sent to the outside world, the state of the distributed system may be exposed to the outside world. If a failure occurs, the outside world cannot be relied upon for recovery. Therefore, to ensure that the recovered state is consistent with the external view, sufficient recovery information must be logged prior to the sending of a message to the outside world. This is what so called the output commit problem [21].
2.1.5 Stable Storage
An essential requirement for logging and checkpointing protocols is the availability of stable storage. Stable storage can survive process failures in that upon recovery, the information stored in the stable storage is readily available to the recovering process. As such, all checkpoints and messages logged must be stored in stable storage.
There are various forms of stable storage. To tolerate only process failures, it is sufficient to use local disks as stable storage. To tolerate disk failures, redundant disks (such as RAID-1 or RAID-5 [14]) could be used as stable storage. Replicated file systems, such as the Google File Systems [9], can be used as more robust stable storage.
2.2 Checkpoint-Based Protocols
Checkpoint-based protocols do not rely on the piecewise deterministic assumption, hence, they are simpler to implement and less restrictive (because the developers do not have to identify all forms of nondeterministic events and log them properly). However, a tradeoff is that the distributed systems that choose to use checkpoint-based protocols must be willing to tolerate loss of execution unless a checkpoint is taken prior to every event, which is normally not realistic.
2.2.1 Uncoordinated Checkpointing
Uncoordinated checkpointing, where each process in the distributed system enjoys full autonomy and can decide when to checkpoints, even though appears to be attractive, is not recommended for two primary reasons.
First, the checkpoints taken by the processes might not be useful to reconstruct a consistent global state. In the worst case, the system might have to do a cascading rollback to the initial system state (often referred to as the domino effect [16]), which completely defeats the purpose of doing checkpointing. Consider the following example.
EXAMPLE 2.2
Figure 2.3 An example of the domino effect in recovery with uncoordinated checkpointing.
In the example illustrated in Figure 2.3, process P1 crashed after it has sent message m8 to P0, but before it has a chance to take a checkpoint. The last checkpoint taken by P1 is C1,1. Furthermore, P2 also crashed concurrently. Now, let’s examine the impact of the failure of P1 and P2:
◾ The most recent checkpoint
