Prasang Upadhyaya
Dan Suciu
Abstract
Data-management-as-a-service systems are increasingly being used in collaborative settings, where multiple users access common datasets. Cloud providers have the choice to implement various optimizations, such as indexing or materialized views, to accelerate queries over these datasets. Each optimization carries a cost and may benefit multiple users. This creates a major challenge: how to select which optimizations to perform and how to share their cost among users. The problem is especially challenging when users are selfish and will only report their true values for different optimizations if doing so maximizes their utility.
In this paper, we present a new approach for selecting and pricing shared optimizations by using Mechanism Design. We first show how to apply the Shapley Value Mechanism to the simple case of selecting and pricing additive optimizations, assuming an offline game where all users access the service for the same time-period. Second, we extend the approach to online scenarios where users come and go. Finally, we consider the case of substitutive optimizations.
We show analytically that our mechanisms induce truthfulness and recover the optimization costs. We also show experimentally that our mechanisms yield higher utility than the state-of-the-art approach based on regret accumulation.
- D. Abramson, R. Buyya, and J. Giddy. A computational economy for grid computing and its implementation in the Nimrod-G resource broker. Future Generation Computer Systems, 18(8):1061--1074, 2002. Google Scholar
Digital Library
- E. Adar and B. A. Huberman. Free riding on gnutella, 2000.Google Scholar
- Amazon Web Services (AWS). aws.amazon.com.Google Scholar
- Amazon Elastic MapReduce. aws.amazon.com/elasticmapreduce.Google Scholar
- Amazon EC2 Instances. aws.amazon.com/ec2/instance-types/.Google Scholar
- Amazon Relational Database Service. aws.amazon.com/rds/.Google Scholar
- Amazon S3: Requester Pays Buckets. http://docs.amazonwebservices.com/AmazonS3/latest/dev/index.html?Reques%terPaysBuckets.html.Google Scholar
- Amazon Simple Storage Service (Amazon S3). http://www.amazon.com/gp/browse.html?node=16427261.Google Scholar
- Amazon SimpleDB. http://www.amazon.com/simpledb/.Google Scholar
- Windows Azure Platform. microsoft.com/windowsazure/.Google Scholar
- Windows Azure Storage Services REST API Ref. http://msdn.microsoft.com/en-us/library/dd179355.aspx.Google Scholar
- M. Balazinska, H. Balakrishnan, and M. Stonebraker. Contract-based load management in federated distributed systems. In Proc. of the Symposium on Networked Systems Design and Implementation, pages 15--15, 2004. Google ScholarDigital Library
- R. Buyya, H. Stockinger, J. Giddy, and D. Abramson. Economic models for management of resources in peer-to-peer and grid computing, 2001.Google Scholar
- B. N. Chun. Market-based cluster resource management. PhD thesis, University of California at Berkeley, 2001. Google ScholarDigital Library
- B. Cohen. Incentives build robustness in bittorrent, 2003.Google Scholar
- D. Dash, V. Kantere, and A. Ailamaki. An economic model for self-tuned cloud caching. In Proc. of the IEEE Int'l Conf. on Data Engineering, pages 1687--1693, 2009. Google ScholarDigital Library
- M. Feldman, C. Papadimitriou, J. Chuang, and I. Stoica. Free-riding and whitewashing in peer-to-peer systems. In Proc. of the ACM SIGCOMM Workshop on Practice and Theory of Incentives in Networked Systems, pages 228--236, 2004. Google ScholarDigital Library
- D. F. Ferguson, C. Nikolaou, J. Sairamesh, and Y. Yemini. Economic models for allocating resources in computer systems, pages 156--183. World Scientific Publishing Co., 1996. Google ScholarDigital Library
- H. Gonzalez, A. Halevy, C. S. Jensen, A. Langen, J. Madhavan, R. Shapley, and W. Shen. Google fusion tables: data management, integration and collaboration in the cloud. In ACM Symposium on Cloud Computing, pages 175--180, 2010. Google ScholarDigital Library
- Google App Engine. http://code.google.com/appengine/.Google Scholar
- Google App Engine Datastore. code.google.com/appengine/docs/datastore.Google Scholar
- V. Kantere, D. Dash, G. Gratsias, and A. Ailamaki. Predicting cost amortization for query services. In Proc. of the ACM SIGMOD, pages 325--336, 2011. Google ScholarDigital Library
- Y. Kwon, D. Nunley, J. P. Gardner, M. Balazinska, B. Howe, and S. Loebman. Scalable clustering algorithm for n-body simulations in a shared-nothing cluster. In Proc. of the Int'l Conf. on Scientific and Statistical Database Management, pages 132--150, 2010. Google ScholarDigital Library
- A. Li, X. Yang, S. Kandula, and M. Zhang. CloudCmp: shopping for a cloud made easy. In HotCloud, pages 5--5, 2010. Google ScholarDigital Library
- S. Loebman. Personal communication.Google Scholar
- Microsoft SQL Azure. microsoft.com/windowsazure/sqlazure/.Google Scholar
- H. Moulin and S. Shenker. Strategyproof sharing of submodular costs: budget balance versus efficiency. Economic Theory, 18(3):511--533, 2001.Google ScholarCross Ref
- About the Blue Waters project. ncsa.illinois.edu/BlueWaters/.Google Scholar
- C. Ng, D. C. Parkes, and M. Seltzer. Strategyproof computing: systems infrastructures for self-interested parties. In 1st Workshop on the Economics of P2P systems, 2003.Google Scholar
- T.-W. J. Ngan, D. S. Wallach, and P. Druschel. Enforcing fair sharing of peer-to-peer resources. In IPTPS Workshop, 2003.Google ScholarCross Ref
- N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007. Google ScholarDigital Library
- M. Pal and E. Tardos. Group strategyproof mechanisms via primal-dual algorithms. In FOCS, pages 584--593, 2003. Google ScholarDigital Library
- D. C. Parkes. Iterative Combinatorial Auctions: achieving economic and computational efficiency. PhD thesis, University of Pennsylvania, 2001. Google ScholarDigital Library
- J.-A. Quiané-Ruiz, P. Lamarre, S. Cazalens, and P. Valduriez. Managing virtual money for satisfaction and scale up in p2p systems. In Proc. of DaMaP Workshop, pages 67--74, 2008. Google ScholarDigital Library
- Salesforce. http://www.salesforce.com/.Google Scholar
- T. Sandholm. An implementation of the contract net protocol based on marginal cost calculations. In Int'l Workshop on Distributed Artificial Intelligence, pages 295--308, 1993. Google ScholarDigital Library
- V. Springel, S. D. M. White, A. Jenkins, C. S. Frenk, N. Yoshida, L. Gao, J. Navarro, R. Thacker, D. Croton, J. Helly, J. A. Peacock, S. Cole, P. Thomas, H. Couchman, A. Evrard, J. Colberg, and F. Pearce. Simulations of the formation, evolution and clustering of galaxies and quasars. NATURE, 435:629--636, 2005.Google ScholarCross Ref
- Stonebraker et al. Mariposa: a wide-area distributed database system. VLDB Journal, 5(1):048--063, 1996. Google ScholarDigital Library
- P. B. Teregowda, B. Urgaonkar, and C. L. Giles. Implications of moving to the cloud: a digital libraries perspective. In HotCloud, 2010.Google Scholar
- K. Tsakalozos, H. Kllapi, E. Sitaridi, M. Roussopoulos, D. Paparas, and A. Delis. Flexible use of cloud resources through profit maximization and price discrimination. In Proc. of the 27th ICDE Conf., pages 75--86, 2011. Google ScholarDigital Library
- P. Upadhyaya, M. Balazinska, and D. Suciu. How to Price Shared Optimizations in the Cloud. Technical Report UW-CSE-11-05-04, University of Washington, 2011.Google Scholar
- V. Vishnumurthy, S. Chandrakumar, and E. G. Sirer. KARMA: A secure economic framework for peer-to-peer resource sharing. In Workshop on the Economics of Peer-to-Peer Systems, 2003.Google Scholar
- C. A. Waldspurger, T. Hogg, B. A. Huberman, J. O. Kephart, and W. S. Stornetta. Spawn: a distributed computational economy. Tran. on Software Engineering, 18(2):103--117, 1992. Google ScholarDigital Library
- H. Wang, Q. Jing, R. Chen, B. He, Z. Qian, and L. Zhou. Distributed systems meet economics: pricing in the cloud. In HotCloud, pages 6--6, 2010. Google ScholarDigital Library
Recommendations
Uniform Price Auctions: Equilibria and Efficiency
We study the Uniform Price Auction, one of the standard sealed-bid multi-unit auction formats in Auction Theory, for selling multiple identical units of a single good to multi-demand bidders. Contrary to the truthful and efficient multi-unit Vickrey ...
Tight Bounds for the Price of Anarchy of Simultaneous First-Price Auctions
We study the price of anarchy (PoA) of simultaneous first-price auctions (FPAs) for buyers with submodular and subadditive valuations. The current best upper bounds for the Bayesian price of anarchy (BPoA) of these auctions are e/(e − 1) [Syrgkanis and ...
Uniform Price Auctions: Equilibria and Efficiency
SAGT 2012: Proceedings of the 5th International Symposium on Algorithmic Game Theory - Volume 7615We present our results on Uniform Price Auctions, one of the standard sealed-bid multi-unit auction formats, for selling multiple identical units of a single good to multi-demand bidders. Contrary to the truthful and economically efficient multi-unit ...
Comments