Failure-aware checkpointing in fine-grained cycle sharing systems

ABSTRACT

Fine-Grained Cycle Sharing (FGCS) systems aim at utilizing the large amountof idle computational resources available on the Internet. Such systems allow guest jobs to run on a host if they do not significantly impact the local users of the host. Since the hosts are typically provided voluntarily, their availability fluctuates greatly. To provide fault tolerance to guest jobs without adding significant computational overhead, we propose failure-aware checkpointing techniques that apply the knowledge of resource availability to select checkpoint repositories and to determine checkpoint intervals. We present the schemes of selecting reliable and efficient repositories from the non-dedicated hosts that contribute their disk storage. These schemes are formulated as 0/1 programming problems to optimize the network overhead of transferring checkpoints and the work lost due to unavailability of a storage host when needed to recover a guest job. We determine the checkpoint interval by comparing the cost of checkpointing immediately and the cost of delaying that to a later time, which is a function of the resource availability. We evaluate these techniques on an FGCS system called iShare, using trace-based simulation. The results show that they achieve better application performance than the prevalent methods which use checkpointing with a fixed periodicity on dedicated checkpoint servers.

REFERENCES

• 1: Using Erasure Codes Efficiently for Storage in a Distributed System, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.336-345, June 28-July 01, 2005 [doi>10.1109/DSN.2005.96]
• 2: Jim Basney , Miron Livny, Managing Network Resources in Condor, Proceedings of the 9th IEEE International Symposium on High Performance Distributed Computing, p.298, August 01-04, 2000
• 3: R. Buyya and M. Murshed. GridSim: A toolkit for the modeling and simulation of distributed resource management and scheduling for grid computing. Concurrency and Computation: Practice and Experience, 14:1175--1220, 2002.
• 4: Christian Cachin , Stefano Tessaro, Optimal Resilience for Erasure-Coded Byzantine Distributed Storage, Proceedings of the International Conference on Dependable Systems and Networks (DSN'06), p.115-124, June 25-28, 2006 [doi>10.1109/DSN.2006.56]
• 5: Raphael Y. de Camargo , Renato Cerqueira , Fabio Kon, Strategies for storage of checkpointing data using non-dedicated repositories on Grid systems, Proceedings of the 3rd international workshop on Middleware for grid computing, p.1-6, November 28-December 02, 2005, Grenoble, France [doi>10.1145/1101499.1101500]
• 6: Peter A. Dinda , David R. O'Hallaron, An Evaluation of Linear Models for Host Load Prediction, Proceedings of the 8th IEEE International Symposium on High Performance Distributed Computing, p.10, August 03-06, 1999
• 7: W. Gentzsch (Sun Microsystems), Sun Grid Engine: Towards Creating a Compute Power Grid, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.35, May 15-18, 2001
• 8: http://setiathome.ssl.berkeley.edu/. SETIυhome: Search for extraterrestrial intelligence at home.
• 9: Yibei Ling , Jie Mi , Xiaola Lin, A Variational Calculus Approach to Optimal Checkpoint Placement, IEEE Transactions on Computers, v.50 n.7, p.699-708, July 2001 [doi>10.1109/12.936236]
• 10: D. Nurmi, J. Brevik, and R. Wolski. Minimizing the network overhead of checkpointing in cycle-harvesting cluster environments. In Proc. of Cluster'05, 2006.
• 11: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 12: J. S. Plank , W. R. Elwasif, Experimental Assessment of Workstation Failures and Their Impact on Checkpointing Systems, Proceedings of the The Twenty-Eighth Annual International Symposium on Fault-Tolerant Computing, p.48, June 23-25, 1998
• 13: 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]
• 14: 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]
• 15: X. Ren and R. Eigenmann. iShare - Open internet sharing built on P2P and web. In Proc. of EGC'05, pages 1117--1127, 2005.
• 16: Xiaojuan Ren , Rudolf Eigenmann, Empirical Studies on the Behavior of Resource Availability in Fine-Grained Cycle Sharing Systems, Proceedings of the 2006 International Conference on Parallel Processing, p.3-11, August 14-18, 2006 [doi>10.1109/ICPP.2006.39]
• 17: X. Ren, R. Eigenmann, and S. Bagchi. Availability prediction for non-dedicated storages in fine-grained cycle sharing systems. Technical Report ECE-HPCLab-06201, Purdue University, 2006.
• 18: X. Ren, S. Lee, R. Eigenmann, and S. Bagchi. Resource availability prediction in fine-grained cycle sharing systems. In Proc. of HPDC'06, pages 93--104, 2006.
• 19: X. Ren, S. Lee, R. Eigenmann, and S. Bagchi. Prediction of resource availability in fine-grained cycle sharing systems and empirical evaluation. To appear in the Journal of Grid Computing, 2007.
• 20: Kyung Dong Ryu , Jeffrey K. Hollingsworth, Resource Policing to Support Fine-Grain Cycle Stealing in Networks of Workstations, IEEE Transactions on Parallel and Distributed Systems, v.15 n.10, p.878-892, October 2004 [doi>10.1109/TPDS.2004.58]
• 21: Se-Chang Son, The Kangaroo Approach to Data Movement on the Grid, Proceedings of the 10th IEEE International Symposium on High Performance Distributed Computing, p.325, August 07-09, 2001
• 22: Douglas Thain , Todd Tannenbaum , Miron Livny, Distributed computing in practice: the Condor experience: Research Articles, Concurrency and Computation: Practice & Experience, v.17 n.2-4, p.323-356, February 2005 [doi>10.1002/cpe.v17:2/4]
• 23: Nitin H. Vaidya, Impact of Checkpoint Latency on Overhead Ratio of a Checkpointing Scheme, IEEE Transactions on Computers, v.46 n.8, p.942-947, August 1997 [doi>10.1109/12.609281]
• 24: Rich Wolski , Neil T. Spring , Jim Hayes, The network weather service: a distributed resource performance forecasting service for metacomputing, Future Generation Computer Systems, v.15 n.5-6, p.757-768, Oct. 1999 [doi>10.1016/S0167-739X(99)00025-4]
• 25: Y. Y. Zhang, M. Squillante, A. Sivasubramaniam, and R. K. Sahoo. Performance implications of failures in large-scale cluster scheduling. In 10th Workshop on Job Scheduling Strategies for Parallel Processing, 2004.
• 26: D. Zhou and V. Lo. Wave scheduler: Scheduling for faster turnaround time in peer-based desktop grid systems. mIn Proc. of the 11th Workshop on Job Scheduling Strategies for Parallel Processing, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Fault tolerance

General Terms:
Performance, Reliability

Keywords:
checkpointing, cycle-sharing systems