Читать книгу From Traditional Fault Tolerance to Blockchain - Wenbing Zhao - Страница 48
EXAMPLE 2.3
Оглавление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., P0 has a connection with P1, P1 has a connection with P2, and P2 has a connection with P0. Therefore, each process has two incoming channels and two outgoing channels connected to its two neighbors.
Assume process P0 is the checkpointing coordinator. It initiates the global checkpointing by sending a CHECKPOINT message to P1 and P2, respectively, along the two outgoing channels. In the mean time, P1 sends a regular message m0 to P0, and P2 sends a regular message m1 to P1.
Upon receiving the CHECKPOINT message from P0, P1 stops normal execution and sends a CHECKPOINT message along each of its outgoing channel to P0 and P2, respectively. Similarly, P2 sends the CHECKPOINT message to P0 and P1, respectively, once it receives the first CHECKPOINT message.
Due to the FIFO property of the connections, P0 receives m0 before it collects all the CHECKPOINT messages from all its incoming channels, and P1 receives m1 before it receives the CHECKPOINT messages from P2. 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 P0 receives the CHECKPOINT messages from P1 and P2, it takes a local checkpoint, C0,0 and append the message log to the checkpoint. Similarly, P1 takes a local checkpoint when it receives the CHECKPOINT messages from P0 and P2, and P2 takes a local checkpoint when it receives the CHECKPOINT messages from P0 and P1.
Subsequently, P1 and P2 send their SAVED messages to P0, i.e., the global checkpointing coordinator. P0 then informs P1 and P2 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.
