Task scheduling scheme by checkpoint sharing and task duplication in P2P-based desktop grids

Abstract

A scheduling scheme is proposed to reduce execution time by means of both checkpoint sharing and task duplication under a peer-to-peer (P2P) architecture. In the scheme, the checkpoint executed by each peer (i.e., a resource) is used as an intermediate result and executed in other peers via its duplication and transmission. As the checkpoint is close to a final result, the reduction of execution time for each task becomes higher, leading to reducing turnaround time. To evaluate the performance of our scheduling scheme in terms of transmission cost and execution time, an analytical model with an embedded Markov chain is presented. We also conduct simulations with a failure rate of tasks and compare the performance of our scheduling scheme with that of the existing scheme based on client-server architecture. Performance results show that our scheduling scheme is superior to the existing scheme with respect to the reduction of execution time and turnaround time.

Keywords

P2P-based desktop grids / checkpoint sharing / task duplication / embedded Markov chain

References

[1] EmmanuelU. Cloud, grid and high performance computing [M]. IGI Global, 2011135-154

[2] ZhaoH, LiuX, LiX. A taxonomy of peer-to-peer desktop grid paradigms [J]. Cluster Computing, 2011, 14(2): 129-144

[3] SETI@Home Project [EB/OL]. http://setiathome.ssl.berkeley.edu. 2014.

[4] CesarioE, de CariaN, MastroianniC, TaliaD. Distributed data mining using a public resource computing framework [M]. Grids, P2P and Services Computing, 201033-44

[5] Berkeley Open Infrastructure for Network Computing (BOINC) [EB/OL]. http://boinc.berkeley.edu/. 2014.

[6] PatniJ C, AswalM S, PrakashO M, GuptaA. Load balancing strategies for grid computing [C]. International Conference on Electronics Computer Technology. Kanyakumari, 2011239-243

[7] UrbahE, KacsukP, FarkasZ, FedakG, KecskemetiG, LodygenskyO, MarosiA, BalatonZ, CaillatG, GombasG, KornafeldA, KovacsJ, HeH, LovasR. EDGeS: Bridging EGEE to BOINC and XtremWeb [J]. Journal of Grid Computing, 2009, 7(3): 335-354

[8] Korea@Home[EB/OL]. http://www.koreaathome.org/eng/. 2010.

[9] KacsukP, KovacsJ, FarkasZ, MarosiA C, GombasG, BalatonZ. SZTAKI Desktop grid (SZDG): A flexible and scalable desktop grid system [J]. Journal of Grid Computing, 2009, 7(4): 439-461

[10] VladoiuM, ConstantinescuZ. Development journey of QADPZ-A desktop grid computing platform [J]. International Journal of Computers, Communications & Control, 2009, 44(1): 82-91

[11] Entropia [EB/OL]. http://enterthegrid.com/. 2014.

[12] United devices [EB/OL]. http://www.univa.com/. 2014.

[13] International desktop grid federation [EB/OL]. http://desktopgridfederation.org/applications/. 2014.

[14] PatakiM, MarosiA C. Searching for translated plagiarism with the help of desktop grids [J]. Journal of Grid Computing, 2013, 11(1): 149-166

[15] GilJ M, KimM. A log analysis system with REST Web services for desktop grids and its application to resource group-based task scheduling [J]. Journal of Information Processing Systems, 2011, 7(4): 707-716

[16] BouguerraM S, KondoD, TrystramD. On the scheduling of checkpoints in desktop grids [C]. 11th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing. Newport Beach, CA, USA, 2011305-313

[17] WangD, GongB. On the checkpointing strategy in desktop grids [J]. Lecture Notes in Computer Science, 2012, 7648: 217226

[18] DomingusP, SilvaJ G, SilvaL. Sharing Checkpoints to improve turnaround time in desktop grid computing [C]. 20th International Conference on Advanced Information Networking and Applications. Vienna, Austria, 20066-11

[19] XtremWeb [EB/OL]. http://www.xtremweb.net/index.html. 2014.

[20] KwokY K RPeer-to-peer computing: Applications, architecture, protocols, and challenges [M], 20118-9

[21] FeldmanR M, Valdez-FloresCApplied probability and stochastic processes [M], 2010115-132