Читать книгу From Traditional Fault Tolerance to Blockchain - Wenbing Zhao - Страница 38

The state of an individual process is defined by its entire address space in an operating system. A generic checkpointing library (such as Condor [23]) normally saves the entire address space as a checkpoint of the process. Of course, not everything in the address space is interesting based on the application semantics. As such, the checkpoint of a process can be potentially made much smaller by exploiting application semantics.

The state of a distributed system is usually referred to as the global state of the system [5]. It is not a simple aggregation of the states of the processes in the distributed system because the processes exchange messages with each other, which means that a process may causally depend on some other processes. Such dependency must be preserved in a global state. Assume that each process in the distributed system takes checkpoints periodically, this implies that we may not be able to use the latest set of checkpoints for proper recovery should the processes fails, unless the checkpointing at different processes are coordinated [5]. To see why, considering the three scenarios illustrated in Figure 2.2 where the global state is constructed by using the three checkpoints, C₀, C₁, C₂, taken at processes P₀, P₁, and P₂, respectively.

Figure 2.2(a) shows a scenario in which the checkpoints taken by different processes are incompatible, and hence cannot be used to recover the system upon a failure. Let’s see why. In this scenario, P₀ sends a message m₀ to P₁, and P₁ subsequently sends a message m₁ to P₂. Therefore, the state of P₂ potentially depends on the state of P₁ after it has received m₁, and the state of P₁ may depend on that of P₀ once it receives m₀. The checkpoint C₀ is taken before P₀ sends the message m₀ to P₁, whereas the checkpoint C₁ is taken after P₁ has received m₀. The checkpoints are not compatible because C₁ reflects the receiving of m₀ while C₀ does not reflect the sending of m₀, that is, the dependency is broken. Similarly, C₂ reflects the receiving of m₁ while C₁ does not reflect the sending of m₁.

Figure 2.2 Consistent and inconsistent global state examples.