Scalable algorithms for global snapshots in distributed systems

ABSTRACT

Existing algorithms for global snapshots in distributed systems are not scalable when the underlying topology is complete. In a network with N processors, these algorithms require O(N) space and O(N) messages per processor. As a result, these algorithms are not efficient in large systems when the logical topology of the communication layer such as MPI is complete. In this paper, we propose three algorithms for global snapshot: a grid-based, a tree-based and a centralized algorithm. The grid-based algorithm uses O(N) space but only O(√N) messages per processor. The tree-based algorithm requires only O(1) space and O(logNlog w) messages per processor where w is the average number of messages in transit per processor. The centralized algorithm requires only O(1) space and O(log w) messages per processor. We also have a matching lower bound for this problem. Our algorithms have applications in checkpointing, detecting stable predicates and implementing synchronizers. We have implemented our algorithms on top of the MPI library on the Blue Gene/L supercomputer. Our experiments confirm that the proposed algorithms significantly reduce the message and space complexity of a global snapshot.

REFERENCES

• 1: Baruch Awerbuch, Complexity of network synchronization, Journal of the ACM (JACM), v.32 n.4, p.804-823, Oct. 1985 [doi>10.1145/4221.4227]
• 2: L. Bougé, Repeated snapshots in distributed systems with synchronous communications and their implementation in CSP, Theoretical Computer Science, v.49 n.2-3, p.145-169, January 1987 [doi>10.1016/0304-3975(87)90005-3]
• 3: K. Mani Chandy , Leslie Lamport, Distributed snapshots: determining global states of distributed systems, ACM Transactions on Computer Systems (TOCS), v.3 n.1, p.63-75, Feb. 1985 [doi>10.1145/214451.214456]
• 4: K. Mani Chandy , Jayadev Misra, How processes learn, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.204-214, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323615]
• 5: E. W. Dijkstra and C. S. Scholten. Termination detection for diffusing computations. Information Processing Letters, 11(4):1--4, Aug. 1980.
• 6: Vijay K. Garg, Concurrent and Distributed Computing in Java, John Wiley & Sons, 2004
• 7: A. D. Kshemkalyani, M. Raynal, and M. Singhal. An introduction to snapshot algorithms in distributed computing. Distributed Systems Engineering, 2(4):224--233, Dec. 1995.
• 8: Leslie Lamport, Time, clocks, and the ordering of events in a distributed system, Communications of the ACM, v.21 n.7, p.558-565, July 1978 [doi>10.1145/359545.359563]
• 9: Friedemann Mattern, Efficient algorithms for distributed snapshots and global virtual time approximation, Journal of Parallel and Distributed Computing, v.18 n.4, p.423-434, Aug. 1993 [doi>10.1006/jpdc.1993.1075]
• 10: Martin Schulz , Greg Bronevetsky , Rohit Fernandes , Daniel Marques , Keshav Pingali , Paul Stodghill, Implementation and Evaluation of a Scalable Application-Level Checkpoint-Recovery Scheme for MPI Programs, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.38, November 06-12, 2004 [doi>10.1109/SC.2004.29]
• 11: M. Spezialetti and P. Kearns. Efficient distributed snapshots. In Proc. of the 6th International Conference on Distributed Computing Systems, pages 382--388, 1986.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.5 Reliability
          Subjects: Checkpoint/restart

General Terms:
Algorithms

Keywords:
Blue Gene/L, checkpointing, fault tolerance, global snapshot algorithms, stable predicates