Grid result checking
Authors:
Open Access
- 4 May 2005
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 87-96
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 outKeywords
This publication has 9 references indexed in Scilit:
- Result checking in global computing systems2003
- On Death, Taxes, and the Convergence of Peer-to-Peer and Grid Computing2003
- Grid services for distributed system integrationComputer, 2002
- Sabotage-tolerance mechanisms for volunteer computing systemsFuture Generation Computer Systems, 2002
- The Anatomy of the Grid: Enabling Scalable Virtual OrganizationsThe International Journal of High Performance Computing Applications, 2001
- SETI@home-massively distributed computing for SETIComputing in Science & Engineering, 2001
- Property testing and its connection to learning and approximationJournal of the ACM, 1998
- Software reliability via run-time result-checkingJournal of the ACM, 1997
- Designing programs that check their work1989