Abstract
The global internet is rich in commodity resources but scarce in specialized resources. We argue that a grid framework can achieve better performance if it separates the management of commodity tasks from the tasks requiring specialized resources. We show that the performance of task execution on a commodity grid is the delay of entering into execution. This effectively transforms the resource allocation problem into a routing problem.
We present an approach in which commodity tasks are distributed to the computation service providers by the use of a forwarding mesh based on randomized Hamilton cycles. We provide stochastically weighted algorithms for forwarding. Mathematical analysis and extensive simulations demonstrate that the approach is scalable and provides efficient task allocation on networks loaded up to 95% of their capacity.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Anderson, D.P.: Public computing: Reconnecting people to science. In: Proceedings of the Conference on Shared Knowledge and the Web (November 2003)
Baker., M., Foster, I.: Recent Changes in the Grid Community, http://dsonline.computer.org/0402/d/o2004a.htm
Liljeqvist, B., Bengtsson, L.: Grid computing distribution using network processors. In: Proc. of the 14th IASTED Parallel and Distributed Computing Conference (November 2002)
Foster, I., Kesselman, C. (eds.): The Computational Grid: Blueprint to a New Computer Infrastructure. Morgan Kaufmann, San Francisco (1998)
Foster, I., Kesselman, C., Nick, J., Tuecke, S.: The Physiology of the Grid: An open grid services architecture for distributed systems integration, http://www.globus.org/research/papers/ogsa.pdf
Foster, I., Kesselman, C., Tuecke, S.: The anatomy of the grid: Enabling scalable virtual organizations. International Journal of Supercomputer Applications 15(3) (2001)
Iamnitchi, A., Foster, I.: On fully decentralized resource discovery in grif environments. In: Proceedings of the International Workshop on Grid Computing, Denver, CO (November 2001)
Ji, Y., Marinescu, D.C., Zhang, W., Baker, T.S.: Orientation refinement of virus structures with unknown symmetry. In: Proceedings of the 17th Ann. Int’l Parallel and Distrib. Processing Symposium Nice, France. IEEE Press, Los Alamitos (2003)
Marinescu, D.C., Ji, Y.: A computational framework for the 3d structure determination of viruses with unknown symmetry. Journal of Parallel and Distributed Computing 63(7-8), 738–758 (2003)
Marinescu, D.C., Ji, Y.: A computational framework for the 3d structure determination of viruses with unknown symmetry. Journal of Parallel and Distributed Computing 63, 738–758 (2003)
Thain, D., Tannenbaum, T., Livny, M.: Condor and the grid. In: Berman, F., Fox, G., Hey, T. (eds.) Grid Computing: Making the Global Infrastructure a Reality. John Wiley & Sons, Chichester (December 2002)
Berkeley Open Infrastructure for Network Computing, http://boinc.berkeley.edu/
Folding@Home project, http://www.stanford.edu/group/pandegroup/folding/
Mersenne Prime search, http://www.mersenne.org/prime.htm
RSA Challenge, http://www.rsasecurity.com/rsalabs/challenges/
SETI@Home project, http://setiathome.ssl.berkeley.edu/
The Wire Speed Grid project, http://www.ce.chalmers.se/staff/labe/WireSpeedGridProject.htm
YAES: Yet Another Extensible Simulator, http://netmoc.cpe.ucf.edu/Yaes/Yaes.html
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bölöni, L., Turgut, D., Kocak, T., Ji, Y., Marinescu, D.C. (2005). Rapid Distribution of Tasks on a Commodity Grid. In: Sloot, P.M.A., Hoekstra, A.G., Priol, T., Reinefeld, A., Bubak, M. (eds) Advances in Grid Computing - EGC 2005. EGC 2005. Lecture Notes in Computer Science, vol 3470. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11508380_73
Download citation
DOI: https://doi.org/10.1007/11508380_73
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26918-2
Online ISBN: 978-3-540-32036-4
eBook Packages: Computer ScienceComputer Science (R0)