research-article

Bidding for Highly Available Services with Low Price in Spot Instance Market

Authors:

Weimin ZhengAuthors Info & Claims

HPDC '15: Proceedings of the 24th International Symposium on High-Performance Parallel and Distributed Computing

Pages 191 - 202

https://doi.org/10.1145/2749246.2749259

Published: 15 June 2015 Publication History

Abstract

Amazon EC2 has built the Spot Instance Marketplace and offers a new type of virtual machine instances called as spot instances. These instances are less expensive but considered failure-prone. Despite the underlying hardware status, if the bidding price is lower than the market price, such an instance will be terminated.

Distributed systems can be built from the spot instances to reduce the cost while still tolerating instance failures. For example, embarrassingly parallel jobs can use the spot instances by re-executing failed tasks. The bidding framework for such jobs simply selects the spot price as the bid. However, highly available services like lock service or storage service cannot use the similar techniques for availability consideration. The spot instance failure model is different to that of normal instances (fixed failure probability in traditional distributed model). This makes the bidding strategy more complex to keep service availability for such systems.

We formalize this problem and propose an availability and cost aware bidding framework. Experiment results show that our bidding framework can reduce the costs of a distributed lock service and a distributed storage service by 81.23% and 85.32% respectively while still keeping availability level the same as it is by using on-demand instances.

References

[1]

O. Agmon Ben-Yehuda, M. Ben-Yehuda, A. Schuster, and D. Tsafrir. Deconstructing amazon ec2 spot instance pricing. ACM Trans. Econ. Comput., 1(3):16:1--16:20, Sept. 2013.

Digital Library

[2]

Y. Amir and A. Wool. Optimal availability quorum systems: Theory and practice. Information Processing Letters, 65(5):223--228, 1998.

Digital Library

[3]

A. Andrzejak, D. Kondo, and S. Yi. Decision model for cloud computing under sla constraints. In Proceedings of the 2010 IEEE International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems, MASCOTS '10, pages 257--266, Washington, DC, USA, 2010. IEEE Computer Society.

Digital Library

[4]

https://aws.amazon.com/about-aws/globalinfrastructure/.

[5]

http://aws.amazon.com/ec2/instance-types/.

[6]

http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/using-spot-limits.html.

[7]

http://aws.amazon.com/ec2/sla/.

[8]

J. Baker, C. Bond, J. C. Corbett, J. Furman, A. Khorlin, J. Larson, J.-M. Léon, Y. Li, A. Lloyd, and V. Yushprakh. Megastore: Providing scalable, highly available storage for interactive services. In CIDR, volume 11, pages 223--234, 2011.

[9]

V. Barbu and N. Limnios. Semi-Markov Chains and Hidden Semi-Markov Models Toward Applications: Their Use in Reliability and DNA Analysis. Springer Publishing Company, Incorporated, 1 edition, 2008.

Digital Library

[10]

W. J. Bolosky, D. Bradshaw, R. B. Haagens, N. P. Kusters, and P. Li. Paxos replicated state machines as the basis of a high-performance data store. In Proceedings of the 8th USENIX Conference on Networked Systems Design and Implementation, NSDI'11, pages 141--154, Berkeley, CA, USA, 2011. USENIX Association.

Digital Library

[11]

https://github.com/boto/boto.

[12]

D. R. Brillinger, P. M. Guttorp, and F. P. Schoenberg. Point processes, temporal. In Encyclopedia of Environmetrics. John Wiley & Sons, Ltd, 2006.

[13]

M. Burrows. The chubby lock service for loosely-coupled distributed systems. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation, OSDI '06, pages 335--350, Berkeley, CA, USA, 2006. USENIX Association.

Digital Library

[14]

B. Calder, J. Wang, A. Ogus, N. Nilakantan, A. Skjolsvold, S. McKelvie, Y. Xu, S. Srivastav, J. Wu, H. Simitci, J. Haridas, C. Uddaraju, H. Khatri, A. Edwards, V. Bedekar, S. Mainali, R. Abbasi, A. Agarwal, M. F. u. Haq, M. I. u. Haq, D. Bhardwaj, S. Dayanand, A. Adusumilli, M. McNett, S. Sankaran, K. Manivannan, and L. Rigas. Windows azure storage: A highly available cloud storage service with strong consistency. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles, SOSP '11, pages 143--157, New York, NY, USA, 2011. ACM.

Digital Library

[15]

N. Chohan, C. Castillo, M. Spreitzer, M. Steinder, A. Tantawi, and C. Krintz. See spot run: using spot instances for mapreduce workflows. In Proceedings of the 2nd USENIX conference on Hot topics in cloud computing, pages 7--7. USENIX Association, 2010.

Digital Library

[16]

J. C. Corbett, J. Dean, M. Epstein, A. Fikes, C. Frost, J. J. Furman, S. Ghemawat, A. Gubarev, C. Heiser, P. Hochschild, W. Hsieh, S. Kanthak, E. Kogan, H. Li, A. Lloyd, S. Melnik, D. Mwaura, D. Nagle, S. Quinlan, R. Rao, L. Rolig, Y. Saito, M. Szymaniak, C. Taylor, R. Wang, and D. Woodford. Spanner: Google's globally-distributed database. In Proceedings of the 10th USENIX Conference on Operating Systems Design and Implementation, OSDI'12, pages 251--264, Berkeley, CA, USA, 2012. USENIX Association.

Digital Library

[17]

G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, and W. Vogels. Dynamo: Amazon's highly available key-value store. In Proceedings of Twenty-first ACM SIGOPS Symposium on Operating Systems Principles, SOSP '07, pages 205--220, New York, NY, USA, 2007. ACM.

Digital Library

[18]

D. K. Gifford. Weighted voting for replicated data. In Proceedings of the Seventh ACM Symposium on Operating Systems Principles, SOSP '79, pages 150--162, New York, NY, USA, 1979. ACM.

Digital Library

[19]

G. Grimmett and D. Stirzaker. Probability and random processes, volume 2. Oxford Univ Press, 1992.

[20]

http://hadoop.apache.org.

[21]

C. Huang, H. Simitci, Y. Xu, A. Ogus, B. Calder, P. Gopalan, J. Li, and S. Yekhanin. Erasure coding in windows azure storage. In Proceedings of the 2012 USENIX Conference on Annual Technical Conference, USENIX ATC'12, pages 2--2, Berkeley, CA, USA, 2012. USENIX Association.

Digital Library

[22]

B. Javadi, R. K. Thulasiramy, and R. Buyya. Statistical modeling of spot instance prices in public cloud environments. In Proceedings of the 2011 Fourth IEEE International Conference on Utility and Cloud Computing, UCC '11, pages 219--228, Washington, DC, USA, 2011. IEEE Computer Society.

Digital Library

[23]

L. Lamport. Paxos made simple. ACM Sigact News, 32(4):18--25, 2001.

[24]

H. Liu. Cutting mapreduce cost with spot market. In Proceedings of the 3rd USENIX Conference on Hot Topics in Cloud Computing, HotCloud'11, pages 6--6, Berkeley, CA, USA, 2011. USENIX Association.

Digital Library

[25]

M. Mao and M. Humphrey. A performance study on the vm startup time in the cloud. In Cloud Computing (CLOUD), 2012 IEEE 5th International Conference on, pages 423--430, June 2012.

Digital Library

[26]

S. Mu, K. Chen, Y. Wu, and W. Zheng. When paxos meets erasure code: Reduce network and storage cost in state machine replication. In Proceedings of the 23rd International Symposium on High-performance Parallel and Distributed Computing, HPDC '14, pages 61--72, New York, NY, USA, 2014. ACM.

Digital Library

[27]

D. Peleg and A. Wool. The availability of quorum systems. Information and Computation, 123(2):210--223, 1995.

Digital Library

[28]

L. Rizzo. Effective erasure codes for reliable computer communication protocols. SIGCOMM Comput. Commun. Rev., 27(2):24--36, Apr. 1997.

Digital Library

[29]

M. Sathiamoorthy, M. Asteris, D. Papailiopoulos, A. G. Dimakis, R. Vadali, S. Chen, and D. Borthakur. Xoring elephants: novel erasure codes for big data. In Proceedings of the 39th international conference on Very Large Data Bases, PVLDB'13, pages 325--336. VLDB Endowment, 2013.

Digital Library

[30]

http://aws.amazon.com/ec2/purchasing-options/spot-instances/.

[31]

Y. Song, M. Zafer, and K.-W. Lee. Optimal bidding in spot instance market. In INFOCOM, 2012 Proceedings IEEE, pages 190--198. IEEE, 2012.

[32]

M. Spasojevic and P. Berman. Voting as the optimal static pessimistic scheme for managing replicated data. Parallel and Distributed Systems, IEEE Transactions on, 5(1):64--73, Jan 1994.

Digital Library

[33]

Z. Tong and R. Kain. Vote assignments in weighted voting mechanisms. In Reliable Distributed Systems, 1988. Proceedings., Seventh Symposium on, pages 138--143, Oct 1988.

[34]

S. Wee. Debunking real-time pricing in cloud computing. In Cluster, Cloud and Grid Computing (CCGrid), 2011 11th IEEE/ACM International Symposium on, pages 585--590, May 2011.

Digital Library

[35]

S. Yi, A. Andrzejak, and D. Kondo. Monetary cost-aware checkpointing and migration on amazon cloud spot instances. IEEE Transactions on Services Computing, 5(4):512--524, 2012.

Digital Library

[36]

S. Yi, D. Kondo, and A. Andrzejak. Reducing costs of spot instances via checkpointing in the amazon elastic compute cloud. In Cloud Computing (CLOUD), 2010 IEEE 3rd International Conference on, pages 236--243, July 2010.

Digital Library

Cited By

Kim KLee KChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Making Cloud Spot Instance Interruption Events VisibleProceedings of the ACM Web Conference 202410.1145/3589334.3645548(2998-3009)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645548
Iqbal SLi HBergsma SBeschastnikh IHu AGavrilovska AAltınbüken DBinnig C(2022)CoSpotProceedings of the 13th Symposium on Cloud Computing10.1145/3542929.3563499(540-556)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3542929.3563499
Kadupitiya JJadhao VSharma P(2022)SciSpot: Scientific Computing On Temporally Constrained Cloud Preemptible VMsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.315727233:12(3575-3588)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3157272
Show More Cited By

Index Terms

Bidding for Highly Available Services with Low Price in Spot Instance Market

Recommendations

Perceptive bidding strategy for Amazon EC2 spot instance market

Spot pricing is an auction based market mechanism introduced by Amazon EC2 to sell available cloud resources at a low cost without any availability guarantee. Bid prices submitted by users directly affect reliability of the instance acquired. In ...
Interplay between Buy-It-Now price and last minute bidding on online bidding strategies

Sellers and buyers on online auction sites like eBay have the option of setting and executing auction parameters such as auction length, Buy-It-Now price, starting price, reserve price, etc. Understanding why bidders choose to execute the Buy-It-Now ...
False-name bidding in first-price combinatorial auctions with incomplete information
AAMAS '11: The 10th International Conference on Autonomous Agents and Multiagent Systems - Volume 2

False-name bids are bids submitted by a single agent under multiple fictitious names such as multiple e-mail addresses. False-name bidding can be a serious fraud in Internet auctions since identifying each participant is virtually impossible. It is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

HPDC '15: Proceedings of the 24th International Symposium on High-Performance Parallel and Distributed Computing

June 2015

296 pages

ISBN:9781450335508

DOI:10.1145/2749246

General Chair:
Thilo Kielmann
VU University Amsterdam, The Netherlands
,
Program Chairs:
Dean Hildebrand
IBM Research Almaden
,
Michela Taufer
University of Delaware

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

University of Arizona: University of Arizona
SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 15 June 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Chinese Special Project of Science and Technology
National High-Tech R&D (863) Program of China
Natural Science Foundation of China

Conference

HPDC'15

Sponsor:

University of Arizona
SIGARCH

HPDC'15: The 24th International Symposium on High-Performance Parallel and Distributed Computing

June 15 - 19, 2015

Oregon, Portland, USA

Acceptance Rates

HPDC '15 Paper Acceptance Rate 19 of 116 submissions, 16%;

Overall Acceptance Rate 166 of 966 submissions, 17%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
351
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)3

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kim KLee KChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Making Cloud Spot Instance Interruption Events VisibleProceedings of the ACM Web Conference 202410.1145/3589334.3645548(2998-3009)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645548
Iqbal SLi HBergsma SBeschastnikh IHu AGavrilovska AAltınbüken DBinnig C(2022)CoSpotProceedings of the 13th Symposium on Cloud Computing10.1145/3542929.3563499(540-556)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3542929.3563499
Kadupitiya JJadhao VSharma P(2022)SciSpot: Scientific Computing On Temporally Constrained Cloud Preemptible VMsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.315727233:12(3575-3588)Online publication date: 1-Dec-2022
https://doi.org/10.1109/TPDS.2022.3157272
Caton SBaughman MHaas CChard RFoster IChard K(2022)Assessing the Current State of AWS Spot Market Forecastability2022 IEEE/ACM International Workshop on Interoperability of Supercomputing and Cloud Technologies (SuperCompCloud)10.1109/SuperCompCloud56703.2022.00007(8-15)Online publication date: Nov-2022
https://doi.org/10.1109/SuperCompCloud56703.2022.00007
Lee SHwang JLee K(2022)SpotLake: Diverse Spot Instance Dataset Archive Service2022 IEEE International Symposium on Workload Characterization (IISWC)10.1109/IISWC55918.2022.00029(242-255)Online publication date: Nov-2022
https://doi.org/10.1109/IISWC55918.2022.00029
Liu JShen HChi HNarman HYang YCheng LChung W(2021)A Low-Cost Multi-Failure Resilient Replication Scheme for High-Data Availability in Cloud StorageIEEE/ACM Transactions on Networking10.1109/TNET.2020.302781429:4(1436-1451)Online publication date: Aug-2021
https://doi.org/10.1109/TNET.2020.3027814
Ghit BTantawi A(2021)Capri: Achieving Predictable Performance in Cloud Spot Markets2021 29th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS)10.1109/MASCOTS53633.2021.9614306(1-8)Online publication date: 3-Nov-2021
https://doi.org/10.1109/MASCOTS53633.2021.9614306
Kadupitige JJadhao VSharma PParashar MVlassov VIrwin DMohror K(2020)Modeling The Temporally Constrained Preemptions of Transient Cloud VMsProceedings of the 29th International Symposium on High-Performance Parallel and Distributed Computing10.1145/3369583.3392671(41-52)Online publication date: 23-Jun-2020
https://dl.acm.org/doi/10.1145/3369583.3392671
Khandelwal VChaturvedi AGupta C(2020)Amazon EC2 Spot Price Prediction Using Regression Random ForestsIEEE Transactions on Cloud Computing10.1109/TCC.2017.27801598:1(59-72)Online publication date: 1-Jan-2020
https://doi.org/10.1109/TCC.2017.2780159
Chittora VGupta C(2020)Dynamic Spot Price Forecasting Using Stacked LSTM Networks2020 3rd International Conference on Intelligent Sustainable Systems (ICISS)10.1109/ICISS49785.2020.9315988(1080-1085)Online publication date: 3-Dec-2020
https://doi.org/10.1109/ICISS49785.2020.9315988
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents