Strategies for storage of checkpointing data using non-dedicated repositories on Grid systems

ABSTRACT

Dealing with the large amounts of data generated by long-running parallel applications is one of the most challenging aspects of Grid Computing. Periodic checkpoints might be taken to guarantee application progression, producing even more data. The classical approach is to employ high-throughput checkpoint servers connected to the computational nodes by high speed networks. In the case of Opportunistic Grid Computing, we do not want to be forced to rely on such dedicated hardware. Instead, we want to use the shared Grid nodes to store application data in a distributed fashion.In this work, we evaluate several strategies to store checkpoints on distributed non-dedicated repositories. We consider the tradeoff among computational overhead, storage overhead, and degree of fault-tolerance of these strategies. We compare the use of replication, parity information, and information dispersal (IDA). We used InteGrade, an object-oriented Grid middleware, to implement the storage strategies and perform evaluation experiments.

REFERENCES

• 1: Noga Alon , Haim Kaplan , Michael Krivelevich , Dahlia Malkhi , Julien P. Stern, Scalable Secure Storage when Half the System Is Faulty, Proceedings of the 27th International Colloquium on Automata, Languages and Programming, p.576-587, July 09-15, 2000
• 2: Stephanos Androutsellis-Theotokis , Diomidis Spinellis, A survey of peer-to-peer content distribution technologies, ACM Computing Surveys (CSUR), v.36 n.4, p.335-371, December 2004 [doi>10.1145/1041680.1041681]
• 3: Fran Berman , Geoffrey Fox , Anthony J. G. Hey , Tony Hey, Grid Computing: Making the Global Infrastructure a Reality, John Wiley & Sons, Inc., New York, NY, 2003
• 4: de Camargo, R. Y., Goldchleger, A., Carneiro, M., and Kon, F. The Grid architectural pattern: Leveraging distributed processing capabilities. In Pattern Languages of Program Design 5 (2005), Addison-Wesley Publishing Company. Accepted.
• 5: Raphael Y. De Camargo , Fabio Kon , Alfredo Goldman, Portable checkpointing and communication for BSP applications on dynamic heterogeneous Grid environments, Proceedings of the 17th International Symposium on Computer Architecture on High Performance Computing, p.226-234, October 24-27, 2005 [doi>10.1109/CAHPC.2005.33]
• 6: Daniel Ellard , James Megquier, DISP: Practical, efficient, secure and fault-tolerant distributed data storage, ACM Transactions on Storage (TOS), v.1 n.1, p.71-94, February 2005 [doi>10.1145/1044956.1044960]
• 7: E. N. (Mootaz) Elnozahy , Lorenzo Alvisi , Yi-Min Wang , David B. Johnson, A survey of rollback-recovery protocols in message-passing systems, ACM Computing Surveys (CSUR), v.34 n.3, p.375-408, September 2002 [doi>10.1145/568522.568525]
• 8: Ian Foster , Carl Kesselman, The Grid 2: Blueprint for a New Computing Infrastructure, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 9: Juan A. Garay , Rosario Gennaro , Charanjit S. Jutla , Tal Rabin, Secure Distributed Storage and Retrieval, Proceedings of the 11th International Workshop on Distributed Algorithms, p.275-289, September 24-26, 1997
• 10: Andrei Goldchleger , Fabio Kon , Alfredo Goldman , Marcelo Finger , Germano Capistrano Bezerra, InteGrade object-oriented Grid middleware leveraging the idle computing power of desktop machines: Research Articles, Concurrency and Computation: Practice & Experience, v.16 n.5, p.449-459, April 2004 [doi>10.1002/cpe.v16:5]
• 11: Litzkow, M., Livny, M., and Mutka, M. Condor - A hunter of idle workstations. In ICDCS '88: Proceedings of the 8th Int. Conference of Distributed Computing Systems (June 1988), pp. 104--111.
• 12: D. Long , A. Muir , R. Golding, A longitudinal survey of Internet host reliability, Proceedings of the 14TH Symposium on Reliable Distributed Systems, p.2, September 13-15, 1995
• 13: Qutaibah M. Malluhi , William E. Johnston, Coding for High Availability of a Distributed-Parallel Storage System, IEEE Transactions on Parallel and Distributed Systems, v.9 n.12, p.1237-1252, December 1998 [doi>10.1109/71.737699]
• 14: James S. Plank, A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems, Software—Practice & Experience, v.27 n.9, p.995-1012, Sept. 1997 [doi>10.1002/(SICI)1097-024X(199709)27:9<995::AID-SPE111>3.3.CO;2-Y]
• 15: James S. Plank , Kai Li , Michael A. Puening, Diskless Checkpointing, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.972-986, October 1998 [doi>10.1109/71.730527]
• 16: Jim Pruyne , Miron Livny, Managing Checkpoints for Parallel Programs, Proceedings of the Workshop on Job Scheduling Strategies for Parallel Processing, p.140-154, April 16, 1996
• 17: Michael O. Rabin, Efficient dispersal of information for security, load balancing, and fault tolerance, Journal of the ACM (JACM), v.36 n.2, p.335-348, April 1989 [doi>10.1145/62044.62050]
• 18: Peter Sobe, Stable Checkpointing in Distributed Systems without Shared Disks, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.214.2, April 22-26, 2003

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

  E. Data
  E.4 CODING AND INFORMATION THEORY

General Terms:
Performance, Reliability

Keywords:
checkpointing, data coding, distributed storage, fault-tolerance, grid computing