From Traditional Fault Tolerance to Blockchain. Wenbing Zhao. Читать онлайн. Newlib. NEWLIB.NET

Автор: Wenbing Zhao
Издательство: John Wiley & Sons Limited
Серия:
Жанр произведения: Зарубежная компьютерная литература
Год издания: 0
isbn: 9781119682110
Скачать книгу
and M. V. Steen. Distributed Systems: Principles and Paradigms. Prentice Hall, 2nd edition, 2006.

      11. A. S. Tanenbaum and D. J. Wetherall. Computer Networks (5th Ed.). Pearson, 2010.

      12. L. Tewksbury, L. Moser, and P. Melliar-Smith. Live upgrade techniques for corba applications. In New Developments in Distributed Applications and Interoperable Systems, volume 70 of IFIP International Federation for Information Processing, pages 257–271. Springer US, 2002.

      Logging and Checkpointing

      Checkpointing and logging are the most essential techniques to achieve dependability in distributed systems [7]. By themselves, they provide a form of fault tolerance that is relatively easy to implement and incurs low runtime overhead. Although some information could be lost (if only checkpointing is used) when a fault occurs and the recovery time after a fault is typically larger than that of more sophisticated fault tolerance approaches, it may be sufficient for many applications. Furthermore, they are used in all levels of dependability mechanisms.

      A checkpoint of a distributed system refers to a copy of the system state [7]. If the checkpoint is available after the system fails, it can be used to recover the system to the state when the checkpoint was taken. Checkpointing refers to the action of taking a copy of the system state (periodically) and saving the checkpoint to a stable storage that can survive the faults tolerated.

      Checkpointing and logging provide a form of rollback recovery [7] because they can recover the system to a state prior to the failure. In contrast, there exist other approaches that accomplish roll-forward recovery, that is, a failed process can be recovered to the current state by incorporating process redundancy into the system. However, roll-forward recovery protocols typically incur significantly higher runtime overhead and demand more physical resources.

Schematic illustration of an example distributed system.

      In such a distributed system, a failure could occur at a process. However, it is assumed that when a process fails, it simply stops execution and loses all its volatile state (i.e., the fail-stop model [18] is used). In addition, it is assumed that any two processes can establish a reliable connection (such as a TCP connection) for communication. Even though the network may lose messages, the reliable channel can effectively mask such losses. Naturally, the reliable connection ensures the first-in first-out (FIFO) property between the two endpoints of the reliable connection. This assumption also implies that the network does not partition, i.e., it does not prevent two or more processes in the system from interacting with each other for extended period of time.

      2.1.2 Process State and Global State

      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.

Schematic illustration of consistent and inconsistent global state examples.

      EXAMPLE 2.1

      To understand the problem better, consider the following example. Assume that P0 and P1 represent two bank accounts, A and B respectively. The purpose of m0 is to deposite $100 to account B after P0 has debited account A. P0 takes a checkpoint C0 before the debit operation, and P1 takes a checkpoint C1 after it has received and processed the deposit request (i.e., m0), as illustrated in Figure 2.2(a). If P0 crashes after sending the deposit request (m0), and P1 crashes after taking the checkpoint C1, upon recovery, P1’s state would reflect a deposit of $100 (from account A) while P0’s state would not reflect the corresponding debit operation. Consequently, $100 would appear