Ridge: combining reliability and performance in open grid platforms

ABSTRACT

Large-scale donation-based distributed infrastructures need to cope with the inherent unreliability of participant nodes. A widely-used work scheduling technique in such environments is to redundantly schedule the out sourced computations to a number of nodes. We present the design and implementation of RIDGE, a reliability aware system which uses a node's prior performance and behavior to make more effective scheduling decisions. We have implemented RIDGE on top of the BOINC distributed computing infrastructure and have evaluated its performance on a live test bed consisting of 120 PlanetLab nodes. Our experimental results show that RIDGE is able to match or surpass the throughput of the best vanilla BOINC configuration under different reliability environments, by automatically adapting to the characteristics of the underlying environment. In addition, RIDGE is able to provide much lower work unit makes pans compared to BOINC, which indicates its desirability in service-oriented environments with time constraints.

REFERENCES

• 1: David P. Anderson, BOINC: A System for Public-Resource Computing and Storage, Proceedings of the Fifth IEEE/ACM International Workshop on Grid Computing, p.4-10, November 08-08, 2004 [doi>10.1109/GRID.2004.14]
• 2: David P. Anderson , Jeff Cobb , Eric Korpela , Matt Lebofsky , Dan Werthimer, SETI@home: an experiment in public-resource computing, Communications of the ACM, v.45 n.11, p.56-61, November 2002 [doi>10.1145/581571.581573]
• 3: Andy Bavier , Mic Bowman , Brent Chun , David Culler , Scott Karlin , Steve Muir , Larry Peterson , Timothy Roscoe , Tammo Spalink , Mike Wawrzoniak, Operating system support for planetary-scale network services, Proceedings of the 1st conference on Symposium on Networked Systems Design and Implementation, p.19-19, March 29-31, 2004, San Francisco, California
• 4: BLAST. http://www.ncbi.nlm.nih.gov/blast.
• 5: J. Brevik , D. Nurmi , R. Wolski, Automatic methods for predicting machine availability in desktop Grid and peer-to-peer systems, Proceedings of the 2004 IEEE International Symposium on Cluster Computing and the Grid, p.190-199, April 19-22, 2004
• 6: Fourth IEEE International Symposium on Network Computing and Applications - Cover, Proceedings of the Fourth IEEE International Symposium on Network Computing and Applications, p.287.1, July 27-29, 2005 [doi>10.1109/NCA.2005.21]
• 7: Climate Prediction Network. http://www.climateprediction.net/.
• 8: Wenliang Du , Jing Jia , Manish Mangal , Mummoorthy Murugesan, Uncheatable Grid Computing, Proceedings of the 24th International Conference on Distributed Computing Systems (ICDCS'04), p.4-11, March 24-26, 2004
• 9: Foldingυhome distributing computing project. http://folding.stanford.edu.
• 10: Philippe Golle , Ilya Mironov, Uncheatable Distributed Computations, Proceedings of the 2001 Conference on Topics in Cryptology: The Cryptographer's Track at RSA, p.425-440, April 08-12, 2001
• 11: Frank Wang , Na Helian , Sining Wu , Yuhui Deng , Ke Zhou , Yike Guo , Steve Thompson , Ian Johnson , Dave Milward , Robert Maddock , Benjamin Khoo, Cluster Computing and Grid 2005 Works in Progress, IEEE Distributed Systems Online, v.6 n.9, p.2, September 2005 [doi>10.1109/MDSO.2005.46]
• 12: Derrick Kondo , Andrew A. Chien , Henri Casanova, Resource Management for Rapid Application Turnaround on Enterprise Desktop Grids, Proceedings of the 2004 ACM/IEEE conference on Supercomputing, p.17, November 06-12, 2004 [doi>10.1109/SC.2004.50]
• 13: D. Nurmi, J. Brevik, and R. Wolski. Minimizing the Network Overhead of Checkpointing in Cycle-harvesting Cluster Environment. In Proceedings of Cluster 2005, September 2005.
• 14: D. Nurmi, J. Brevik, and R. Wolski. Modeling Machine Availability in Enterprise and Wide-area Distributed Computing Environments. In Proceedings of EUROPAR 2005, August 2005.
• 15: PPDG: Particle Physics Data Grid. http://www.ppdg.net.
• 16: X. Ren, S. Lee, R. Eigenmann, and S. Bagchi. Resource Availability Prediction in Fine-Grained Cycle Sharing Systems. In Proceedings of the 15th IEEE International Symposium on High Performance Distributed Computing, 2006.
• 17: M. R. Viswanath and K. Schwan. Harnessing Non-dedicated Wide-area Clusters for On-demand Computing. In Proceedings of the IEEE International Conference on Cluster Computing (Cluster 2005), September 2005.
• 18: Luis F. G. Sarmenta, Sabotage-Tolerance Mechanisms for Volunteer Computing Systems, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.337, May 15-18, 2001
• 19: J. Sonnek, M. Nathan, A. Chandra, and J.Weissman. Reputation-Based Scheduling on Unreliable Distributed Infrastructures. Technical Report 05-036, Dept. of CSE, Univ. of Minnesota, November 2005.
• 20: Jason Sonnek , Mukesh Nathan , Abhishek Chandra , Jon Weissman, Reputation-Based Scheduling on Unreliable Distributed Infrastructures, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.30, July 04-07, 2006 [doi>10.1109/ICDCS.2006.70]
• 21: Michela Taufer , Patricia J. Teller , David P. Anderson , Charles L. Brooks, III, Metrics for Effective Resource Management in Global Computing Environments, Proceedings of the First International Conference on e-Science and Grid Computing, p.204-211, December 05-08, 2005 [doi>10.1109/E-SCIENCE.2005.58]
• 22: Shanyu Zhao , Virginia Lo , Chris GauthierDickey, Result Verification and Trust-Based Scheduling in Peer-to-Peer Grids, Proceedings of the Fifth IEEE International Conference on Peer-to-Peer Computing (P2P'05), p.31-38, August 31-September 02, 2005 [doi>10.1109/P2P.2005.32]

INDEX TERMS

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

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

General Terms:
Algorithms, Performance, Reliability

Keywords:
open grids, reliability, reputation, scheduling