Message Number Check and Message Rearranging Theory and Protocols. In Rollback Recovery of Distributed Systems

      Аннотация: Message number check and message rearranging are basic theory concerning rollback recovery of distributed systems. In previous studies, the consistency of global state is based on the analysis of the dependency relations of message receipt and sending events. To simplify the determination of the global state consistency issue, we proposed message number check theory. Under the FIFO reliable channel assumption, the consistence of global state, can be determined by the number of messages sent and received by each process. In optimistic message protocols, the receipt order of unlogged messages may be lost upon receiver process failure, and the receipt order cannot be recovered if it is lost. To address the problem the loss of message receipt order, We propose an equivalent message sequence to replace original one. In the equivalent message sequence, the messages are rearranged according to the value of sender process’s improved logic clock. So, the message receipt order can be equivalently recovered by the sender process logic clock upon receiver process failure. Thus, the corresponding protocol can possess the merit of Pessimistic and Optimistic logging protocols simultaneously.

Ключевые слова: distributed system, Rollback Recovery, message logging