Auction-based Admission Control for Continuous Queries in a Multi-Tenant DSMS

##plugins.themes.academic_pro.article.sidebar##

Published Nov 1, 2012
https://doi.org/10.47164/ijngc.v3i3.37
Download
PDF
Statistic

Downloads

Download data is not yet available.

Metrics

Metrics Loading ...
Volume 3, Issue 3, November 2012

##plugins.themes.academic_pro.article.main##

Lory Al Moakar
Department of Computer Science, University of Pittsburgh
Panos K. Chrysanthis
Department of Computer Science, University of Pittsburgh
Christine Chung
Department of Computer Science, Connecticut College
Shenoda Guirguis
Department of Computer Science, University of Pittsburgh
Alexandros Labrinidis
Department of Computer Science, University of Pittsburgh
Panayiotis Neophytou
Department of Computer Science, University of Pittsburgh
Kirk Pruhs
Department of Computer Science, University of Pittsburgh

Abstract

The growing popularity of monitoring applications and "Big Data" analytics used by a variety of users will lead to a multi-tenant data stream management system. This paper deals with the problem of admission control of continuous queries, where the stream processing resources are sold to the end users. We employ variable pricing by means of auction-based mechanisms. The admission control auction mechanism determines which queries to admit, and how much to charge the user for each query in a way that maximizes system revenue. The admission mechanism is required to be strategyproof and sybil-immune, incentivizing users to use the system honestly. Specifically, we require that each user maximizes her payoff by bidding her true value of having a query run. We further consider the requirement that the mechanism be sybil-immune: that is, no user can increase her payoff by submitting queries that she does not value. Given the above requirements, the main challenges come from the difficulty of effectively utilizing shared processing of continuous queries. We design several payment mechanisms and experimentally evaluate them.

##plugins.themes.academic_pro.article.details##

How to Cite
Moakar, L. A. ., Chrysanthis, P. K. ., Chung, C. ., Guirguis, S. ., Labrinidis, A. ., Neophytou, P. ., & Pruhs, K. . (2012). Auction-based Admission Control for Continuous Queries in a Multi-Tenant DSMS. International Journal of Next-Generation Computing, 3(3), 247–273. https://doi.org/10.47164/ijngc.v3i3.37
Crossref
Scopus
Google Scholar
Europe PMC

References

  1. Abadi, D. J., Carney, D., C etintemel, U., Cherniack, M., Convey, C., Lee, S., Stonebraker, M., Tatbul, N., and Zdonik, S. 2003. Aurora: a new model and architecture for data stream management. VLDBJ 12, 2, 120–139.
  2. Aggarwal, G. and Hartline, J. D. 2006. Knapsack auctions. In Proceedings of the seventeenth annual ACMSIAM symposium on Discrete algorithm. SODA ’06. ACM, New York, NY, USA, 1083–1092.
  3. Al Moakar, L., Chrysanthis, P. K., Chung, C., Guirguis, S., Labrinidis, A., Neophytou, P., and Pruhs, K. 2010. Admission control mechanisms for continuous queries in the cloud. In Proceedings of the 26th IEEE International Conference on Data Engineering. ICDE’10. IEEE Computer Society, Long Beach, CA, U.S.A, 409–412.
  4. AmazonEC 2009. Amazon elastic compute cloud, http://aws.amazon.com/ec2/.
  5. Arasu, A., Babcock, B., Babu, S., Datar, M., Ito, K., Motwani, R., Nishizawa, I., Srivastava, U., Thomas, D., Varma, R., and Widom, J. 2003. Stream: The stanford stream data manager. IEEE Data Engineering Bulletin 26, 1, 19–26.
  6. Babcock, B., Babu, S., Motwani, R., and Datar, M. 2003. Chain: operator scheduling for memory minimization in data stream systems. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data. SIGMOD ’03. ACM, New York, NY, USA, 253–264.
  7. Blumrosen, L. and Nisan, N. 2007. Combinatorial auctions. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, ´Eva Tardos, and V. V. Vazirani, Eds. Cambridge University Press, Chapter 11, 267–300.
  8. Carney, D., C etintemel, U., Cherniack, M., Convey, C., Lee, S., Seidman, G., Stonebraker, M., Tatbul, N., and Zdonik, S. 2002. Monitoring streams: a new class of data management applications. In Proceedings of the 28th international conference on Very Large Data Bases. VLDB ’02. VLDB Endowment, 215–226.
  9. Chakravarthy, S. and Jiang, Q. 2009. Stream Data Processing: A Quality of Service Perspective - Modeling, Scheduling, Load Shedding, and Complex Event Processing. Advances in Database Systems, vol. 36. Kluwer.
  10. Chandrasekaran, S., Cooper, O., Deshpande, A., Franklin, M. J., Hellerstein, J. M., Hong, W., Krishnamurthy, S., Madden, S. R., Reiss, F., and Shah, M. A. 2003. Telegraphcq: continuous dataflow processing. In Proceedings of the 2003 ACM SIGMOD international conference on Management of data. SIGMOD ’03. ACM, New York, NY, USA, 668–668.
  11. Coral8 2004. http://www.coral8.com/.
  12. Douceur, J. R. 2002. The sybil attack. In Revised Papers from the First International Workshop on Peer-to-Peer Systems. IPTPS ’01. Springer-Verlag, London, UK, 251–260.
  13. Esper Tech 2006. http://esper.codehaus.org.
  14. Feige, U., Peleg, D., and Kortsarz, G. 2001. The dense k-subgraph problem. Algorithmica 29, 3, 410–421.
  15. Fiat, A., Goldberg, A. V., Hartline, J. D., and Karlin, A. R. 2002. Competitive generalized auctions. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. STOC ’02. ACM, New York, NY, USA, 72–81.
  16. Friedman, E., Resnick, P., and Sami, R. 2007. Manipulation-resistant reputation systems. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, ´Eva Tardos, and V. V. Vazirani, Eds. Cambridge University Press, Chapter 27, 267–300.
  17. Gedik, B., Wu, K.-L., Yu, P. S., and Liu, L. 2005. Adaptive load shedding for windowed stream joins. In Proceedings of the 14th ACM international conference on Information and knowledge management. CIKM ’05. ACM, New York, NY, USA, 171–178.
  18. Goldberg, A. V., Hartline, J. D., Karlin, A. R., Saks, M., and Wright, A. 2006. Competitive auctions. Games and Economic Behavior 55, 242–269.
  19. Krishnamurthy, S., Wu, C., and Franklin, M. 2006. On-the-fly sharing for streamed aggregation. In Proceedings of the 2006 ACM SIGMOD international conference on Management of data. SIGMOD ’06. ACM, New York, NY, USA, 623–634.
  20. Lehmann, D., Ocallaghan, L. I., and Shoham, Y. 2002. Truth revelation in approximately efficient combinatorial auctions. J. ACM 49, 5, 577–602.
  21. Madden, S., Shah, M., Hellerstein, J. M., and Raman, V. 2002. Continuously adaptive continuous queries over streams. In Proceedings of the 2002 ACM SIGMOD international conference on Management of data. SIGMOD ’02. ACM, New York, NY, USA, 49–60.
  22. Microsoft StreamInSight 2008. http://www.microsoft.com/sqlserver/2008/en/us/r2-complex-event.aspx.
  23. Nisan, N. 2007. Introduction to mechanism design. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, ´Eva Tardos, and V. V. Vazirani, Eds. Cambridge University Press, Chapter 9, 267–300.
  24. Pham, T. N., Moakar, L. A., Chrysanthis, P. K., and Labrinidis, A. 2011. Dilos: A dynamic integrated load manager and scheduler for continuous queries. In Proceedings of the 2011 IEEE 27th International Conference on Data Engineering Workshops. ICDEW ’11. IEEE Computer Society, Washington, DC, USA, 10–15.
  25. Sakurai, Y., Yokoo, M., and Matsubara, S. 1999. A limitation of the generalized vickrey auction in electronic commerce: robustness against false-name bids. In AAAI/IAAI. American Association for Artificial Intelligence, Menlo Park, CA, USA, 86–92.
  26. Sellis, T. K. 1988. Multiple-query optimization. ACM Transactions on Database Systems 13, 1, 23–52.
  27. Sharaf, M. A., Chrysanthis, P. K., Labrinidis, A., and Pruhs, K. 2008. Algorithms and metrics for processing multiple heterogeneous continuous queries. ACM Transactions on Database Systems 33, 1, 1–44.
  28. Streambase 2006. http://www.streambase.com.
  29. System S 2008. http://domino.research.ibm.com/comm/research projects.nsf/pages/esps.index.html.
  30. Tatbul, N., C etintemel, U., Zdonik, S., Cherniack, M., and Stonebraker, M. 2003. Load shedding in a data stream manager. In Proceedings of the 29th international conference on Very large data bases - Volume 29. VLDB ’03. VLDB Endowment, 309–320.
  31. Wolf, J., Bansal, N., Hildrum, K., Parekh, S., Rajan, D., Wagle, R., and Wu, K.-L. 2009. Job scheduling strategies for parallel processing. Springer-Verlag, Berlin, Heidelberg, Chapter Job Admission and Resource Allocation in Distributed Streaming Systems, 169–189.
  32. Wolf, J., Bansal, N., Hildrum, K., Parekh, S., Rajan, D., Wagle, R., Wu, K.-L., and Fleischer, L. 2008.
  33. Soda: An optimizing scheduler for large-scale stream-based distributed computer systems. In Middleware 2008, V. Issarny and R. Schantz, Eds. Lecture Notes in Computer Science, vol. 5346. Springer Berlin / Heidelberg, 306–325.