Efficient distributed snapshots in an anonymous asynchronous message-passing system

摘要

We present a global snapshot algorithm with concurrent initiators, with termination detection in an anonymous asynchronous distributed message-passing system having FIFO channels. In anonymous systems, process identifiers are not available and an algorithm cannot use process identifiers in its operation. Such systems arise in several domains due to a variety of reasons. In the proposed snapshot algorithm for anonymous systems, each instance of algorithm initiation is identified by a random number (nonce); however, this is not used as an address in any form of communication. In the algorithm, each process can determine an instant when the local snapshot recordings at all the processes have terminated. This is a challenging problem when an algorithm cannot use process identifiers and a process does not know the number of processes in the system or the diameter of the network and cannot use a predefined topology overlay on the network, because there is no easy way to identify the global termination condition. The message complexity of our algorithm is (cn~2), where c is the number of concurrent initiators and n is the number of processes in the system, which is much better than that of the algorithm by Chalopin et al. (2012) [6]. Further, the algorithm by Chalopin et al. also requires knowledge of the network diameter.