Grid result checking

ABSTRACT

Result checking is the theory and practice of proving that the result of an execution of a program on an input is correct. Result checking has most often been envisioned in the framework of program testing or property testing, where the issue is the conformity of the program to some a-priori specification. Very large scale distributed computing systems demand to tackle the issue of computation correctness, albeit from hypothesis very different from the program testing ones. The general issues examined in this paper are the following. First, the definition of checking methods adapted to large-scale Monte-Carlo simulations; for these applications, no external criterion can be used to assess the quality of the result. Second, two result checking algorithms which minimize the overall overhead through an adaptive strategy. Finally, a specialization of this framework to a case study, the Auger astrophysics experiment. Our main contributions are: first to focus on checking Monte-Carlo simulations, which have rarely been considered previously; second to define a probabilistic checking strategy including the risk of first kind (false positive) as well as the risk of second kind (false negative) which is usually the only one considered, and which is compatible with Byzantine saboteurs; third, to exploit the probable characteristics of the behaviour of the saboteurs to optimise for the most frequent case. Finally, we show on a case study that the implementation details can be carried out

REFERENCES

• 1: V. Barnett and T. Lewis. Outliers in Statistical Data. John Wiley and Sons,84.
• 2: M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73015]
• 3: Hal Wasserman , Manuel Blum, Software reliability via run-time result-checking, Journal of the ACM (JACM), v.44 n.6, p.826-849, Nov. 1997 [doi>10.1145/268999.269003]
• 4: A. Brown and D.A. Patterson. Embracing Failure: A Case for Recovery-Oriented Computing (ROC). In High Performance Transaction Processing Symposium, 2001.
• 5: P. Buncic, A. J. Peters, and P. Saiz. The AliEn system, status and perspectives. In Computing in High Energy and Nuclear Physics. econf- http://www.slac.stanford.edu/econf/C0303241, 2003.
• 6: B. Falissard. Les analyses intermdiaires dans les essais thrapeutiques. PhD thesis, Universit Paris-Sud, 90.
• 7: Gilles Fedak , Cecile Germain , Vincent Neri , Franck Cappello, XtremWeb: A Generic Global Computing System, Proceedings of the 1st International Symposium on Cluster Computing and the Grid, p.582, May 15-18, 2001
• 8: I. Foster and A. Iamnitchi. On Death, Taxes, and the Convergence of Peer-to-Peer and Grid Computing. In 2nd Intl Workshop on Peer-to-Peer Systems (IPTPS '03), volume 2573 of LNCS, pages 118--128. Springer-Verlag,2003.
• 9: Ian Foster , Carl Kesselman , Jeffrey M. Nick , Steven Tuecke, Grid Services for Distributed System Integration, Computer, v.35 n.6, p.37-46, June 2002 [doi>10.1109/MC.2002.1009167 ]
• 10: Ian Foster , Carl Kesselman , Steven Tuecke, The Anatomy of the Grid: Enabling Scalable Virtual Organizations, International Journal of High Performance Computing Applications, v.15 n.3, p.200-222, August 2001 [doi>10.1177/109434200101500302]
• 11: Cécile Germain , Gilles Fedak , Vincent Néri , Franck Cappello, Global Computing Systems, Proceedings of the Third International Conference on Large-Scale Scientific Computing-Revised Papers, p.218-227, June 06-10, 2001
• 12: Cécile Germain-Renaud , Nathalie Playez, Result checking in global computing systems, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782846]
• 13: Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
• 14: 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
• 15: Trusted Computing Group. https://www.trustedcomputinggroup.org/downloads/specifications/.
• 16: D. Heck and al. The Corsika program. Technical report, Forschungszentrum Karlsruhe, 98.
• 17: John H. Hine , Paul Dagger, Securing distributed computing against the hostile host, Proceedings of the 27th Australasian conference on Computer science, p.279-286, January 01, 2004, Dunedin, New Zealand
• 18: Dan Werthimer , Jeff Cobb , Matt Lebofsky , David Anderson , Eric Korpela, SETI@HOME—massively distributed computing for SETI, Computing in Science and Engineering, v.3 n.1, p.78-83, January 1, 2001 [doi>10.1109/5992.895191 ]
• 19: Luis F. G. Sarmenta, Sabotage-tolerance mechanisms for volunteer computing systems, Future Generation Computer Systems, v.18 n.4, p.561-572, March 2002 [doi>10.1016/S0167-739X(01)00077-2 ]
• 20: S. J. Sciutto. Aires: Air showers extended simulation. Department of Physics of the Universidad Nacional de La Plata, Argentina, 1995. http://www.fisica.unlp.edu.ar/auger/aires/.
• 21: D. Siegmund. Sequential Analysis. Springer Series in Statistics. Springer Verlag, 85.
• 22: Doug Szajda , Barry Lawson , Jason Owen, Hardening Functions for Large Scale Distributed Computations, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.216, May 11-14, 2003
• 23: A. Wald. Sequential Analysis. Wiley Series in Stat. Wiley, 66.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

Additional Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics

Keywords:
grids, result checking, simulation