From Traditional Fault Tolerance to Blockchain. Wenbing Zhao

Чтение книги онлайн.

Figure 2.6 Normal operation of the Tamir and Sequin checkpointing protocol in an example three-process distributed system.

To see how the checkpointing protocol works, consider the example shown in Figure 2.6. In this example, we assume that the distributed system consists of three processes, where the three processes are fully connected, i.e., P₀ has a connection with P₁, P₁ has a connection with P₂, and P₂ has a connection with P₀. Therefore, each process has two incoming channels and two outgoing channels connected to its two neighbors.

Assume process P₀ is the checkpointing coordinator. It initiates the global checkpointing by sending a CHECKPOINT message to P₁ and P₂, respectively, along the two outgoing channels. In the mean time, P₁ sends a regular message m₀ to P₀, and P₂ sends a regular message m₁ to P₁.

      Upon receiving the CHECKPOINT message from P₀, P₁ stops normal execution and sends a CHECKPOINT message along each of its outgoing channel to P₀ and P₂, respectively. Similarly, P₂ sends the CHECKPOINT message to P₀ and P₁, respectively, once it receives the first CHECKPOINT message.

      Due to the FIFO property of the connections, P₀ receives m₀ before it collects all the CHECKPOINT messages from all its incoming channels, and P₁ receives m₁ before it receives the CHECKPOINT messages from P₂. According to the protocol rule, such regular messages are logged instead of delivered because normal execution must be stopped once the global checkpointing is initiated. These logged messages will be appended to the local checkpoint once it is taken. In fact, such messages reflect the channel states of the distributed system. These messages won’t be delivered for execution until a process resumes normal execution.

      When P₀ receives the CHECKPOINT messages from P₁ and P₂, it takes a local checkpoint, C_0,0 and append the message log to the checkpoint. Similarly, P₁ takes a local checkpoint when it receives the CHECKPOINT messages from P₀ and P₂, and P₂ takes a local checkpoint when it receives the CHECKPOINT messages from P₀ and P₁.

      Subsequently, P₁ and P₂ send their SAVED messages to P₀, i.e., the global checkpointing coordinator. P₀ then informs P₁ and P₂ to resume normal execution with a RESUME message to each of them.

      A more complicated distributed system in which some processes do not have direct connection with the coordinator will require some of the coordinator’s neighbors to relay the SAVED notification to the coordinator.

       2.2.2.2 Correctness of the Protocol.

It is easy to see why the protocol always produce a set of checkpoints that can be used to reconstruct a consistent global state in the absence of failures. As shown in Figure 2.2(a) and (b), a consistent global state consists of only two scenarios with respect to each pair of local states:

      In the Tamir and Sequin protocol, if neither the coordinator nor any of the participants receives any regular message once the global checkpointing is initiated, then the scenario 1 holds. On the other hand, if a process receives one or more regular messages, it logs them and append them to the local checkpoint, ensuring their replayability. Hence, the scenario 2 holds. Because the protocol prohibits any process from continuing normal execution (including the sending of a message) as soon as it initiates (if it is the coordinator) or receives the very first CHECKPOINT message (for a participant), no process would receive a message prior to its checkpointing that has been sent by another process after that process has taken its local checkpoint in the same round. That is, the inconsistent global state scenario shown in Figure 2.2(a) does not occur.

      2.2.3 Chandy and Lamport Distributed Snapshot Protocol

      The Tamir and Sequin global checkpointing protocol is very elegant. However, it is a blocking protocol in that normal execution is suspended during each round of global checkpointing. For applications that do not wish to suspend the normal execution for potentially extensive period of time, the Chandy and Lamport distributed snapshot protocol [5] might be more desirable.

The Chandy and Lamport distributed snapshot protocol [5] is a nonblocking protocol in that normal execution is not interrupted by the global checkpointing. However, unlike the Tamir and Sequin protocol, the Chandy and Lamport distributed snapshot protocol only concerns on how to produce a consistent global checkpoint, and it prescribes no mechanisms on how to determine the end of the checkpointing round, and how to atomically switch over to the new global checkpoint.