Efficient Global Snapshot Algorithms for Large-Scale Distributed Systems

A global snapshot represents a consistent global state of the system. A global state is consistent if and only if all pairs of its constituent local states of processors are consistent, i.e., if the receiving event of message is recorded, the sending event of the same message must also be recorded, and all in-transit messages on the channels are recorded .Hence, computing the global snapshot of a distributed system enjoys many applications in asynchronous distributed computing. In this paper, we propose an efficient global-snapshot algorithm able to let every process finish its local snapshot in a given number of rounds. Particularly, such an algorithm allows a tradeoff between the response time and the message complexity. Moreover, our global-snapshot algorithm is symmetrical in the sense that identical steps are executed by every process. This means that our algorithm is able to achieve better workload balance and less network congestion. Most importantly, based on our framework, we demonstrate that the minimum number of control messages required by a symmetrical global-snapshot algorithm is (NlogN), where N is the number of processes. Finally, we also assume non-FIFO channels. Therefore, our result provides more flexibility in designing an efficient global-snapshot algorithm for larger scale distributed systems with different requirements.