CISUC

Characterizing Result Errors in Internet Desktop Grids

Authors

Abstract

Desktop grids use the free resources in Intranet and Inter-
net environments for large-scale computation and storage. While desktop
grids offer a high return on investment, one critical issue is the validation
of results returned by participating hosts. Several mechanisms for result
validation have been previously proposed. However, the characterization
of errors is poorly understood. To study error rates, we implemented
and deployed a desktop grid application across several thousand hosts
distributed over the Internet. We then analyzed the results to give quan-
titative and empirical characterization of errors stemming from input or
output (I/O) failures. We find that in practice, error rates are widespread
across hosts but occur relatively infrequently. Moreover, we find that er-
ror rates tend to not be stationary over time nor correlated between
hosts. In light of these characterization results, we evaluated state-of-
the-art error detection mechanisms and describe the trade-offs for using
each mechanism.

Subject

Desktop Grid

Related Project

CoreGRID: the European Research Network on Foundations, Software Infrastructures and Applications for Large Scale Distributed, GRID and Peer-to-Peer Technologies

Conference

13th International EuroPar Conference 2007, August 2007

PDF File


Cited by

Year 2015 : 6 citations

 [HTML] Algorithmic Mechanisms for Reliable Crowdsourcing Computation under Collusion
AF Anta, C Georgiou, MA Mosteiro, D Pareja - PloS one, 2015 - dx.plos.org
Abstract We consider a computing system where a master processor assigns a task for
execution to worker processors that may collude. We model the workers' decision of whether
to comply (compute the task) or not (return a bogus result to save the computation cost) as ...
Cited by 1 Related articles All 9 versions Cite Save More
[PDF] from inria.fr
Contributions to Desktop Grid Computing

 Multi-round Master-Worker Computing: a Repeated Game Approach
AF Anta, C Georgiou, MA Mosteiro, D Pareja - arXiv preprint arXiv: …, 2015 - arxiv.org
Abstract: We consider a computing system where a master processor assigns tasks for
execution to worker processors through the Internet. We model the workers decision of
whether to comply (compute the task) or not (return a bogus result to save the computation ...
Cite Save

 Result Verification Scheme with Resource Clustering in Desktop Grids
JM Gil, YH Cho, SH Hong - Advanced Multimedia and Ubiquitous …, 2015 - Springer
Abstract In desktop grids, it is important to guarantee the verification of task results in the
presence of dynamic properties, such as volatility and heterogeneity. To achieve this
objective, we propose the result-verification scheme with resource clustering that can ...
Related articles All 2 versions Cite Save

 An implementation of credibility-based job scheduling method in volunteer computing systems
S Tani, Y Nogami, M Fukushi - Consumer Electronics-Taiwan ( …, 2015 - ieeexplore.ieee.org
Abstract—This paper addresses a job scheduling problem in Volunteer Computing (VC)
systems, where some malicious participant may return incorrect results (sabotaging).
Credibilitybased job scheduling method, namely ENR-ECJ, is a promising approach to ...
Cite Save

 Virtual Screening in a Desktop Grid: Replication and the Optimal Quorum
I Chernov, N Nikitina - Parallel Computing Technologies, 2015 - Springer
Abstract We propose a mathematical model of a desktop grid computing system that solves
tasks with two possible answers. Replication is used in order to reduce the error risk: wrong
answers are returned with some known probabilities and penalty is added to the ...
Cited by 2 Cite Save

 Dynamic Job Scheduling Method Based on Expected Probability of Completion of Voting in Volunteer Computing
Y MIYAKOSHI, S YASUDA, K WATANABE… - … on Information and …, 2015 - search.ieice.org
This paper addresses the problem of job scheduling in volunteer computing (VC) systems
where each computation job is replicated and allocated to multiple participants (workers) to
remove incorrect results by a voting mechanism. In the job scheduling of VC, the number ...
Cite Save

Year 2014 : 3 citations

 Reputation-Based Mechanisms for Reliable Crowdsourcing Computation
E Christoforou, A Fernández Anta, G Chryssis… - 2014 - eprints.networks.imdea.org
We consider an Internet-based Master-Worker framework, for machine-oriented computing
tasks (ie SETI@ home) or human intelligence tasks (ie Amazon's Mechanical Turk). In this
framework a master sends tasks to unreliable workers, and the workers execute and ...
Cite Save

 The Effectiveness of Reputation-based Voting for Collusion Tolerance in Large-Scale Grids
M Essaaidi, A Bendahmane, A El Moussaoui, Y Ali - ieeexplore.ieee.org
Abstract—Large scale grids permit to share grid resources spread over different
autonomous administrative sites in the internet. The rapid progress of grid systems opens
the door for numerous companies to adopt this technology in their business development. ...
Cite Save

 A Group Based Replication Mechanism to Reduce the Wastage of Processing Cycles in Volunteer Computing
MK Khan, SI Hyder, GU Ahmed, S Begum… - Wireless Personal …, 2014 - Springer
Abstract Volunteer Computing is an exciting discipline for high throughput applications but
due to inherent resource volatility, several issues arises such as tasks failure due to
host/CPU unavailability, results validation etc. Replication is a solution to most of these ...

Year 2013 : 4 citations

 Christoforou, Evgenia and Anta, Antonio Fernandez and Georgiou, Chryssis and Mosteiro, Miguel A et al., ”Reputation-based Mechanisms for Evolutionary Master-Worker Computing”,arXiv preprint arXiv:1307.2783, 2013.

 Muszynski, Jakub and Varrette, Sébastien and Bouvry, Pascal, ”Expected running time of parallel evolutionary algorithms on unimodal pseudo-boolean functions over small-world networks”, IEEE Congress on Evolutionary Computation (CEC), pp. 2588-2594, 2013.

 Watanabe, Kan and Fukushi, Masaru and Funabiki, Nobuo and Nakanishi, Toru,”Performance Evaluation of Check-By-Voting for Colluding Attack in Volunteer Computing Systems”, IAENG Transactions on Engineering Technologies, pp.33-48, 2013.

 Watanabe, Kan and Funabiki, Nobuo and Nakanishi, Toru and Fukushi, Masaru, ”Optimal Spot-Checking for Delayed Attack on Desktop Grid Systems”, UKSim, pp.600-605, 2013.

Year 2012 : 6 citations

 Silaghi C. Gheorghe, Dependable Resource Management Tools towards Automated Collaboration in Heterogeneous Computing Environments, Habilitation Thesis, Babes Bolyai University, Romenia, 2012.

 Christoforou, Evgenia and Fernández Anta, Antonio and Georgiou, Chryssis and Mosteiro, Miguel A. Algorithmic Mechanisms for Reliable Master-Worker Internet-based Computing. IEEE Transactions on Computers. ISSN 0018-9340, 2012.

 Fernández Anta, Antonio and Georgiou, Chryssis and López, Luis and Santos, Agustin (2012) Reliable Internet-based Master-Worker Computing in the Presence of Malicious Workers. Parallel Processing Letters, 22 (1).

 Bendahmane, Ahmed and Essaaidi, Mohammad and Younes, Ali et al., ”A new mechanism to ensure integrity for MapReduce in cloud computing”, 2012 International Conference on Multimedia Computing and Systems (ICMCS), pp 785–790, 2012.

 Bendahmane, Ahmed and Essaaidi, Mohammad and Moussaoui, Ahmed El and Younes, Ali, ”Result verification mechanism for MapReduce computation integrity in cloud computing”, 2012 International Conference on Complex Systems (ICCS), 2012.

 [PDF] http://www.iaeng.org/publication/IMECS2012/IMECS2012_pp1658-1663.pdf
Kan Watanabe, Nobuo Funabiki, Toru Nakanishi and Masaru Fukushi, "Modeling and Performance Evaluation of Colluding Attack in Volunteer Computing Systems", Proceedings of the International MultiConference of Engineers and Computer Scientists 2012, Vol. II, IMECS 2012, March 14-16, 2012, Hong Kong.

Year 2011 : 5 citations

 Watanabe, K. and Fukushi, M. and Kameyama, M., “Adaptive Group-Based Job Scheduling for High Performance and Reliable Volunteer Computing”, Journal of Information Processing, Volume 19, pp. 39-51, 2011

 Christoforou, E.; Anta, A.F.; Georgiou, C.; Mosteiro, M.A.; "Algorithmic mechanisms for internet supercomputing under unreliable communication", Network Computing and Applications (NCA), 2011 10th IEEE International Symposium on, pp 275-280, DOI: 10.1109/NCA.2011.46, 2011 (http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6038615)

 E. Christoforou, AF Anta, C Georgiou, Miguel A. Mosteiro, "Efficient Mechanisms for Single-task Reliable-communication Master-Worker Computing with Malicious and Rational Workers", Technical Report TR-11-04, Department of Computer Science, University of Cyprus, May 2011 (http://www.cs.ucy.ac.cy/ric/publications/UCY-CS-TR-11-04.pdf)

 Heien, Eric and Kondo, Derrick and Gainaru, Ana and LaPine, Dan and Kramer, Bill and Cappello, Franck, "Modeling and tolerating heterogeneous failures in large parallel systems", Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, pp 1(45)-11(45), SC'11, 2011.

 Christoforou, Evgenia and Fernández Anta, Antonio and Georgiou, Chryssis and Mosteiro, Miguel, Algorithmic Mechanisms for Internet-Based Computing under Unreliable Communication, Lecture Notes in Computer Science, pp 147-149 (DOI:10.1007/978-3-642-24100-0_13), 2011

Year 2010 : 9 citations

 Ahmed Bendahmane, Mohammad Essaaidi, Ahmed El~Moussaoui, and Ali Younes.
Compromised resources tolerance in grid computing systems. In Mohammad Essaaidi, Michele Malgeri, and Costin Badica, editors, {em Intelligent Distributed Computing IV}, volume 315 of {em Studies in Computational Intelligence}, pages 145--154. Springer Berlin / Heidelberg, 2010.

 Eugen Staab. {em Reliable Information Acquisition in the Presence of Malicious Sources}. PhD thesis, University of Luxembourg, April 2010. Online Version, 2010-04-22.

 Bendahmane, A. and Essaaidi, M. and El Moussaoui, A. and Younes, A., “Compromised Resources Tolerance in Grid Computing Systems”, Intelligent Distributed Computing IV, pp. 145-154, 2010

 Tang, B. and Moca, M. and Chevalier, S. and He, H. and Fedak, G., “Towards mapreduce for desktop grid computing”, IEEE Computer Society, 2010

 Bendahmane, A. and Essaaidi, M. and El Moussaoui, A. and Younes, A., “Reputation-based Majority Voting for Malicious Grid Resources Tolerance”, SCALABLE COMPUTING, pp. 385, 2010

 Canon, L.C., “Outils et algorithmes pour gérer l’incertitude lors de l’ordonnancement d’application sur plateformes distribuées”, PhD Thesis, Université Henri Poincarré – Nancy 1, France, 2010.

 Watanabe, K. and Fukushi, M. and Horiguchi, S., “Expected-credibility-based Job Scheduling for Reliable Volunteer Computing”, IEICE Transactions on Information and Systems, volume 93, issue 2, pp. 306-314, 2010

 Watanabe, K. and Fukushi, M., “Generalized Spot-checking for Sabotage-tolerance in Volunteer Computing Systems”, 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing, pp. 655-660, 2010

 Watanabe, K. and Fukushi, M., “Generalized Spot-Checking for Reliable Volunteer Computing”, IEICE TRANSACTIONS on Information and Systems, volume 93, issue 12, pp. 3164-3172, 2010

Year 2009 : 5 citations

 \item Rim Chayeh, Christophe Cerin, and Mohamed Jemni.
A probabilistic fault-tolerant recovery mechanism for task and result certification of large-scale distributed applications.
In Nabil Abdennadher and Dana Petcu, editors, {\em Advances in Grid and Pervasive Computing}, volume 5529 of {\em Lecture Notes in Computer
Science}, pages 471--482. Springer Berlin / Heidelberg, 2009.

 \item Mark Silberstein, Artyom Sharov, Dan Geiger, and Assaf Schuster.
Gridbot: Execution of bags of tasks in multiple grids. In {\em SC '09 Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis}, 2009.

 \item Eugen Staab.
{\em Reliable Information Acquisition in the Presence of Malicious Sources}.
PhD thesis, University of Luxembourg, April 2010. Online Version, 2010-04-22.
\item Eugen Staab and Thomas Engel.
Collusion detection for grid computing. In Franck Cappello, Cho-Li Wang, and Rajkumar Buyya, editors, {\em Proceedings of the 9th IEEE/ACM International Symposium on Cluster Computing
and the Grid (CCGrid '09)}, pages 412--419. IEEE Computer Society, May 2009.

 \item Eugen Staab and Thomas Engel.
Tuning evidence-based trust models. {\em Computational Science and Engineering, IEEE International Conference on}, 3:92--99, 2009.

 In {\em e-Business Engineering, 2009. ICEBE '09. IEEE International Conference on}, pages 213 --218, October 2009.

Year 2008 : 9 citations

 Defeating colluding nodes in Desktop Grid computing platforms - ►coregrid.net [PDF] 
GC Silaghi, F Araujo, LM Silva, P Domingues, AE ? - IEEE International Symposium on Parallel and Distributed ?, 2008 - ieeexplore.ieee.org
Page 1. 978-1-4244-1694-3/08/$25.00 ©2008 IEEE Defeating Colluding Nodes in Desktop
Grid Computing Platforms Gheorghe Cosmin Silaghi Dept. of Business Information Systems
Babes . -Bolyai University, Cluj, Romania gsilaghi@econ.ubbcluj.ro .

 [PDF] ►Using correlation for collusion detection in grid settings
E Staab, V Fusenig, T Engel - wiki.uni.lu
Eugen Staab, Volker Fusenig and Thomas Engel ... Faculty of Sciences,
Technology and Communication University of Luxembourg 6, rue R.
Coudenhove-Kalergi 1359 Luxembourg Luxembourg ... Using Correlation for ...
Cited by 2 - Related articles - View as HTML - Web Search

 BitDew: a programmable environment for large-scale data management and distribution - ►lri.fr [PDF] 
G Fedak, H He, F Cappello - Proceedings of the 2008 ACM/IEEE conference on ?, 2008 - portal.acm.org
Abstract"Desktop Grids use the computing, network and storage resources from
idle desktop PC"s distributed over multiple-LAN"s or the Internet to compute
a large variety of resource-demanding distributed applications. While these ...
Cited by 2 - Related articles - Web Search - All 5 versions

 [CITATION] Priority based list scheduling for sabotage-tolerance with deadline tasks in desktop grids
HS Kim, CS Hwang, S Lee, SJ Choi, JM Gil - International Journal of Computer Systems Science & ?, 2008 - CRL Publishing Ltd, PO Box 31, Market Harborough, Leics, LE 16 9 ?
Related articles - Web Search - BL Direct

 USING SLA BASED APPROACH TO HANDLE SABOTAGE TOLERANCE IN THE GRIDS
S Naqvi, S Mouton, P Massonet, GC Silaghi, D ? - Springer
Syed Naqvi, Stephane Mouton, Philippe Massonet Centre of Excellence in
Information and Communication Technologies, Belgium { syed.naqvi,
stephane.mouton, philippe.massonet } @cetic.be ... Gheorghe Cosmin Silaghi ...
Related articles - Web Search

 [PDF] ►BitDew: A Programmable Environment for Large-Scale Data Management and Distribution
GFHHF Cappello - inria.ccsd.cnrs.fr
Page 1. apport de recherche I S S N 0 2 4 9 - 6 3 9 9 I S R N I N R I A / R R - -
6 4 2 7 - - F R + E N G Thème SYM INSTITUT NATIONAL DE RECHERCHE EN INFORMATIQUE
ET EN AUTOMATIQUE BitDew: A Programmable Environment for ...
Related articles - View as HTML - Web Search - All 6 versions

 [PDF] ►BitDew: a Programmable Environment for Data Desktop Grids
G Fedak, D Kondo, F Cappello - gforge.inria.fr
Page 1. BitDew : a Programmable Environment for Data Desktop Grids Gilles Fedak,
Derrick Kondo, Paul Malecot, Franck Cappello Grand-Large/INRIA-Futurs Laboratoire
de Recherche en Informatique Universite Paris XI Tsukuba 2006, Japan ...
Related articles - View as HTML - Web Search - All 2 versions

 [PDF] ►Collusion Detection
E Staab - wiki.uni.lu
Page 1. Collusion Detection For Acquisition of Unverifiable Information
Eugen Staab University of Luxembourg eugen.staab@uni.lu SECAN-Lab day
Amneville-Les-Thermes, France, June 30, 2008 Page 2. ...
Related articles - View as HTML - Web Search

 [PDF] ARC INRIA PROPOSAL
labri.fr [PDF]
G IPT, M IPT, A IPT - 2008 - labri.fr
A grid is a set of distributed and heterogeneous resources. In recent years, a lot of work has been
done to efficiently manage and use such resources. However, most of the models,
algorithms, protocols and programs designed and developed in this context do not take ...
View as HTML