Abstract
Current distributed computing infrastructures, such as peer-to-peer networks, grids, and more recently clouds, make sharing and trading resources ubiquitous. In these large distributed systems, rational users are both providers and consumers of resources. Currently, there is growing interest in exploiting economic models for the allocation of shared computing resources that incentivize rational users. However, when the number of resource types and users increases, computational complexity of the allocation algorithms grows rapidly and efficiency deteriorates. In this paper, we propose a scalable distributed market framework for the allocation of shared resources in large distributed systems. We use mechanism design to create a pricing scheme that allocates a request for multiple resource types, by trading economic efficiency for computational efficiency, strategy-proof and budget-balance. To address scalability, our proposed framework leverages on a peer-to-peer overlay for resource discovery and management. We prototype our framework using FreePastry, a popular overlay network based on the Pastry protocol. We show that our scheme is efficient and scalable using both simulation experiments and results from the deployment on PlantLab.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
FreePastry - A scalable, decentralized, self-organizing and fault-tolerant substrate for peer-to-peer applications (2009), http://freepastry.org
Auyoung, A., Chun, B., Snoeren, A., Vahdat, A.: Resource Allocation in Federated Distributed Computing Infrastructures. In: Proc. of the Workshop on Operating System and Arch. Support for the On-demand IT Infr., Boston, USA (2004)
Buyya, R., Abramson, D., Giddy, J.: Nimrod/G: An Architecture of a Resource Management and Scheduling System in a Global Computational Grid. In: Proc. of the 4th Intl. Conf. on High Performance Computing in Asia-Pacific Region, Beijing, China, pp. 283–289 (2000)
Buyya, R., Bubendorfer, K. (eds.): Market Oriented Grid and Utility Computing. Wiley Press, Chichester (2009)
Cramton, P., Shoham, Y., Steinberg, R. (eds.): Combinatorial Auctions. MIT Press, Cambridge (2006)
Eymann, T., Reinicke, M., Ardaiz, O., Artigas, P., de Cerio, L.D., Freitag, F., Messeguer, R., Navarro, L., Royo, D., Sanjeevan, K.: Decentralized vs. centralized economic coordination of resource allocation in grids. In: European Across Grids Conf., Santiago de Compostela, Spain, pp. 9–16 (2003)
Feigenbaum, J., Papadimitriou, C.H., Shenker, S.: Sharing the Cost of Multicast Transmissions. Journal of Computer and System Sciences 63, 21–41 (2001)
Gon Chun, B., Fonseca, R., Stoica, I., Kubiatowicz, J.: Characterizing Selfishly Constructed Overlay Routing Networks. In: Proc. of INFOCOM 2004, Hong Kong, China, pp. 1329–1339 (2004)
Groves, T.: Incentives in Teams. Econometrica 41(4), 617–631 (1973)
Hausheer, D.: PeerMart: The Technology for a Distributed Auction-based Market for Peer-to-Peer Services. In: Proc. of the 40th IEEE Intl. Conf. on Communications, Seoul, Korea (2005)
Krauter, K., Buyya, R., Maheswaran, M.: A Taxonomy and Survey of Grid Resource Management Systems for Distributed Computing. Software Practice and Experience 32, 135–164 (2002)
Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21(7), 558–565 (1978)
Mihailescu, M., Teo, Y.M.: Strategic-Proof Dynamic Resource Pricing of Multiple Resource Types on Federated Clouds. In: Proc. of the 10th Intl. Conf. on Algorithms and Architectures for Parallel Processing, Busan, Korea, pp. 337–350 (2010)
Myerson, R.B., Satterthwaite, M.A.: Efficient Mechanisms for Bilateral Trading. Journal of Economic Theory 29(2), 265–281 (1983)
Nielson, S.J., Crosby, S.A.: A Taxonomy of Rational Attacks. In: Proc. of the 4th Intl. Workshop on Peer-to-Peer Systems, Ithaca, USA, pp. 36–46 (2005)
Nimis, J., Anandasivam, A., Borissov, N., Smith, G., Neumann, D., Wirström, N., Rosenberg, E., Villa, M.: SORMA - Business Cases for an Open Grid Market. In: Grid Economics and Business Models, Berlin, Germany, pp. 173–184 (2008)
Nisan, N.: Bidding and Allocation in Combinatorial Auctions. In: Proc. of the 2nd ACM Conf. on Electronic Commerce, Minneapolis, USA, pp. 1–12 (2000)
Rowstron, A., Druschel, P.: Pastry: Scalable, Decentralized Object Address, and Routing for Large-Scale Peer-to-Peer Systems. In: Proc. of the Intl. Conf. on Distributed Systems Platforms, Heidelberg, Germany, pp. 329–350 (2001)
Shneidman, J., Parkes, D.C.: Rationality and Self-Interest in Peer to Peer Networks. In: Proc. of the 2nd Intl. Workshop on Peer-to-Peer Systems, Berkely, USA, pp. 139–148 (2003)
Stoica, I., Morris, R., Liben-Nowell, D., Karger, D., Kaashoek, M.F., Dabek, F., Balakrishnan, H.: Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications. Networking, IEEE/ACM Transactions 11(1), 17–32 (2003)
Teo, Y.M., Mihailescu, M.: A Strategic-proof Pricing Scheme for Multiple Resource Type Allocations. In: Proc. of 38th Intl. Conf. on Parallel Processing, Vienna, Austria, pp. 172–179 (2009)
Wolski, R., Plank, J.S., Brevik, J., Bryan, T.: G-commerce: Market Formulations Controlling Resource Allocation on the Computational Grid. In: Proc. of the Intl. Parallel and Distributed Processing Symp., San Francisco, USA, pp. 46–54 (2001)
Wu, C., Li, B., Li, Z.: Dynamic Bandwidth Auctions in Multioverlay P2P Streaming with Network Coding. IEEE Transactions on Parallel Distributed Systems 19, 806–820 (2008)
Yeo, C.S., Buyya, R.: A Taxonomy of Market-based Resource Management Systems for Utility-driven Cluster Computing. Software: Practice and Experience 36, 1381–1419 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mihailescu, M., Teo, Y.M. (2010). A Distributed Market Framework for Large-Scale Resource Sharing. In: D’Ambra, P., Guarracino, M., Talia, D. (eds) Euro-Par 2010 - Parallel Processing. Euro-Par 2010. Lecture Notes in Computer Science, vol 6271. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15277-1_40
Download citation
DOI: https://doi.org/10.1007/978-3-642-15277-1_40
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15276-4
Online ISBN: 978-3-642-15277-1
eBook Packages: Computer ScienceComputer Science (R0)