Harnessing migrations in a market-based grid OS
Authors: 
L. Amar, J. Stosser, E. Levy, A. Shiloh, A. Barak, D. NeumannAuthors Info & Claims
Pages 85 - 94
Abstract
Applying economic principles to grids is deemed promising to improve the overall value provided by such systems. End users can influence the allocation of resources by reporting valuations for these resources. Current market-based schedulers, however, are static, assume the availability of complete information about jobs (in particular with respect to processing times), and do not make use of the flexibility offered by advanced computing systems. In this paper, we present the implementation of economic resource allocation principles into MOSIX, a state-of-the-art management system for computing clusters and multi-cluster organizational grids. The system is designed so as to be able to work in large-scale settings with selfish agents. Facing incomplete information about jobspsila characteristics, it dynamically allocates jobs to computing machines by leveraging preemption and job migration, two distinct features offered by MOSIX. We validate and showcase the behavior of our economic model by means of experiments in the real system.
References
[1]
L. Amar, A. Barak, Z. Drezner, and I. Peer. Gossip algorithms for maintaining a distributed bulletin board with guaranteed age properties. TR, Hebrew University.
[2]
L. Amar, A. Mu'alem, and J. Stößer. On the importance of migration for fairness in online grid markets. AAMAS, 2008.
[3]
A. AuYoung, B. Chun, A. Snoeren, and A. Vahdat. Resource allocation in federated distributed computing infrastructures. OASIS, 2004.
[4]
A. Barak, A. Shiloh, and L. Amar. An organizational grid of federated mosix clusters. In CCGrid05, May 2005.
[5]
R. Buyya, D. Abramson, and J. Giddy. Nimrod/G: An Architecture for a Resource Management and Scheduling System in a Global Computational Grid. HPC Asia, 2000.
[6]
A. Byde, M. Salle, and C. Bartolini. Market-based resource allocation for utility data centers. HP Lab, Bristol, Technical Report HPL-2003-188, Sept, 2003.
[7]
D. Feitelson. Parallel workloads archive. http://www. cs.huji.ac.il/labs/parallel/workload/.
[8]
I. Foster, C. Kesselman, and S. Tuecke. The Anatomy of the Grid: Enabling Scalable Virtual Organizations. International Journal of High Performance Computing Applications, 15(3):200, 2001.
[9]
K. Lai. Markets are dead, long live markets. ACM SIGecom Exchanges, 5(4):1-10, 2005.
[10]
K. Lai, L. Rasmusson, E. Adar, L. Zhang, and B. Huberman. Tycoon: An implementation of a distributed, market-based resource allocation system. Multiagent and Grid Systems, 1(3):169-182, 2005.
[11]
R. Motwani, S. Phillips, and E. Torng. Nonclairvoyant scheduling. Theoretical Computer Science, 130(1):17-47, 1994.
[12]
A. Mu'alem and D. Feitelson. Utilization, predictability, workloads, and user runtime estimates in scheduling the IBM SP 2 with backfilling. IEEE TPDS, 12(6):529-543, 2001.
[13]
D. Neumann, N. Borissov, J. Stößer, and S. See. Best myopic vs. rational response: An evaluation of an Online Scheduling Mechanism. 70. Wissenschaftliche Jahrestagung des Verbands der Hochschullehrer fr Betriebswirtschaft e.V., Berlin, 2008.
[14]
N. Nisan and A. Ronen. Algorithmic Mechanism Design. Games and Economic Behavior, 35(1-2):166-196, 2001.
[15]
N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic Game Theory. Cambridge University Press, New York, NY, USA, 2007.
[16]
P. Padala, C. Harrison, N. Pelfort, E. Jansen, M. Frank, and C. Chokkareddy. OCEAN: the open computation exchange and arbitration network, a market approach to meta computing. Symposium on Parallel and Distributed Computing, 2003.
[17]
P. Padala and J. Wilson. GridOS: Operating System Services for Grid Architectures. International Conference On HP computing, 2002.
[18]
S. Phelps. Evolutionary Mechanism Design. PhD thesis, University of Liverpool, 2007.
[19]
B. Schnizler, D. Neumann, D. Veit, and C. Weinhardt. Trading grid services-a multi-attribute combinatorial approach. European Journal of Operational Research, 187(3):943-961, 2008.
[20]
W. E. Smith. Various optimizers for single-stage production. Naval Resource Logistics Quarterly, 3:59-66, 1956.
[21]
J. Stößer, D. Neumann, and A. Anandasivam. A truthful heuristic for efficient scheduling in network-centric grid OS. ECIS, 2007.
[22]
I. Sutherland. A futures market in computer time. Communications of the ACM, 11(6):449-451, 1968.
[23]
C. Waldspurger, T. Hogg, B. Huberman, J. Kephart, and W. Stornetta. Spawn: A Distributed Computational Economy. IEEE Transactions on Software Engineering, 18(2):103-117, 1992.
[24]
C. Watkins and P. Dayan. Q-learning. Machine Learning, 8(3):279-292, 1992.
Index Terms
- Harnessing migrations in a market-based grid OS
Recommendations
A Market Design for Grid Computing
Grid computing uses software to integrate computing resources, such as CPU cycles, storage, network bandwidth, and even applications, across a distributed and heterogeneous set of networked computers. It is now widely deployed by organizations and ...
A commodity market algorithm for pricing substitutable Grid resources
A crucial goal for future Grid systems is to strive towards user-centric service provisioning. A way to achieve this is through the use of economics-based resource management. Currently, several models exist from among which auction- and commodity-based ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2008
416 pages
ISBN:9781424425785
Publisher
IEEE Computer Society
United States
Publication History
Published: 29 September 2008
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 135Total Downloads
- Downloads (Last 12 months)21
- Downloads (Last 6 weeks)9
Reflects downloads up to 14 Feb 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in