More Web Proxy on the site http://driver.im/

research-article

Auction Mechanisms in Cloud/Fog Computing Resource Allocation for Public Blockchain Networks

Authors:

Kongrath SuankaewmaneeAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 30, Issue 9

Pages 1975 - 1989

https://doi.org/10.1109/TPDS.2019.2900238

Published: 01 September 2019 Publication History

Abstract

As an emerging decentralized secure data management platform, blockchain has gained much popularity recently. To maintain a canonical state of blockchain data record, proof-of-work based consensus protocols provide the nodes, referred to as miners, in the network with incentives for confirming new block of transactions through a process of “block mining” by solving a cryptographic puzzle. Under the circumstance of limited local computing resources, e.g., mobile devices, it is natural for rational miners, i.e., consensus nodes, to offload computational tasks for proof of work to the cloud/fog computing servers. Therefore, we focus on the trading between the cloud/fog computing service provider and miners, and propose an auction-based market model for efficient computing resource allocation. In particular, we consider a proof-of-work based blockchain network, which is constrained by the computing resource and deployed as an infrastructure for decentralized data management applications. Due to the competition among miners in the blockchain network, the allocative externalities are particularly taken into account when designing the auction mechanisms. Specifically, we consider two bidding schemes: the constant-demand scheme where each miner bids for a fixed quantity of resources, and the multi-demand scheme where the miners can submit their preferable demands and bids. For the constant-demand bidding scheme, we propose an auction mechanism that achieves optimal social welfare. In the multi-demand bidding scheme, the social welfare maximization problem is NP-hard. Therefore, we design an approximate algorithm which guarantees the truthfulness, individual rationality and computational efficiency. Through extensive simulations, we show that our proposed auction mechanisms with the two bidding schemes can efficiently maximize the social welfare of the blockchain network and provide effective strategies for the cloud/fog computing service provider.

References

[1]

S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” 2008.

[2]

Y. Guo and C. Liang, “Blockchain application and outlook in the banking industry,” Financial Innovation, vol. 2, no. 1, 2016, Art. no.

[3]

K. Christidis and M. Devetsikiotis, “Blockchains and smart contracts for the Internet of Things,” IEEE Access, vol. 4, pp. 2292–2303, 2016.

[4]

D. Chatzopoulos, M. Ahmadi, S. Kosta, and P. Hui, “FlopCoin: A cryptocurrency for computation offloading,” IEEE Trans. Mobile Comput., vol. 17, no. 5, pp. 1062–1075, May 2018.

[5]

“Blockchain for enterprise applications,” Tech. Rep., Tractica, https://www.tractica.com/research/blockchain-for-enterprise-applications/. The latest publication date is 3Q 2018.

[6]

J. Garay, A. Kiayias, and N. Leonardos, “The bitcoin backbone protocol: Analysis and applications,” in Proc. Annu. Int. Conf. Theory Appl. Cryptographic Techn., 2015, pp. 281–310.

[7]

H. Shafagh, L. Burkhalter, A. Hithnawi, and S. Duquennoy, “Towards blockchain-based auditable storage and sharing of IoT data,” in Proc. Cloud Comput. Secur. Workshop, 2017, pp. 45–50.

[8]

J. Kang, R. Yu, X. Huang, S. Maharjan, Y. Zhang, and E. Hossain, “Enabling localized peer-to-peer electricity trading among plug-in hybrid electric vehicles using consortium blockchains,” IEEE Trans. Ind. Informat., vol. 13, no. 6, pp. 3154–3164, Dec. 2017.

[9]

G. Zyskind, O. Nathan, et al., “Decentralizing privacy: Using blockchain to protect personal data,” in Proc. IEEE Secur. Privacy Workshops, 2015, pp. 180–184.

[10]

Z. Xiong, Y. Zhang, D. Niyato, P. Wang, and Z. Han, “When mobile blockchain meets edge computing,” IEEE Commun. Mag., vol. 56, no. 8, pp. 33–39, Aug. 2018.

Digital Library

[11]

Q. Li, L. Zhao, J. Gao, H. Liang, L. Zhao, and X. Tang, “SMDP-based coordinated virtual machine allocations in cloud-fog computing systems,” IEEE Internet Things J., vol. 5, no. 3, pp. 1977–1988, Jun. 2018.

[12]

X. Zhang, Z. Huang, C. Wu, Z. Li, and F. C. Lau, “Online auctions in IaaS clouds: Welfare and profit maximization with server costs,” IEEE/ACM Trans. Netw., vol. 25, no. 2, pp. 1034–1047, Apr. 2017.

Digital Library

[13]

A. Kiayias, E. Koutsoupias, M. Kyropoulou, and Y. Tselekounis, “Blockchain mining games,” in Proc. ACM Conf. Econ. Comput., 2016, pp. 365–382.

[14]

C. Catalini and J. S. Gans, “Some simple economics of the blockchain,” Tech. Rep., National Bureau of Economic Research, 2016, http://www.nber.org/papers/w22952

[15]

Y. Jiao, P. Wang, D. Niyato, and Z. Xiong, “Social welfare maximization auction in edge computing resource allocation for mobile blockchain,” in Proc. IEEE Next Generation Netw. Internet Symp., May 2018, pp. 1–6.

[16]

D. T. T. Anh, M. Zhang, B. C. Ooi, and G. Chen, “Untangling blockchain: A data processing view of blockchain systems,” IEEE Trans. Knowl. Data Eng., vol. 30, no. 7, pp. 1366–1385, Jul. 2018.

[17]

F. Tschorsch and B. Scheuermann, “Bitcoin and beyond: A technical survey on decentralized digital currencies,” IEEE Commun. Surv. Tut., vol. 18, no. 3, pp. 2084–2123, Jul.–Sep. 2016.

Digital Library

[18]

H. Kopp, D. Mödinger, F. Hauck, F. Kargl, and C. Bösch, “Design of a privacy-preserving decentralized file storage with financial incentives,” in Proc. IEEE Eur. Symp. Secur. Privacy Workshops, 2017, pp. 14–22.

[19]

J. Backman, S. Yrjölä, K. Valtanen, and O. Mämmelä, “Blockchain network slice broker in 5G: Slice leasing in factory of the future use case,” in Proc. Internet Things Bus. Models Users Netw., Nov. 2017, pp. 1–8.

[20]

N. Houy, “The bitcoin mining game,” Ledger, vol. 1, pp. 53–68, 2016.

[21]

Y. Lewenberg, Y. Bachrach, Y. Sompolinsky, A. Zohar, and J. S. Rosenschein, “Bitcoin mining pools: A cooperative game theoretic analysis,” in Proc. Int. Conf. Auton. Agents Multiagent Syst., 2015, pp. 919–927.

[22]

X. Zhang, Z. Yang, W. Sun, Y. Liu, S. Tang, K. Xing, and X. Mao, “Incentives for mobile crowd sensing: A survey,” IEEE Commun. Surv. Tut., vol. 18, no. 1, pp. 54–67, Jan.–Mar. 2016.

Digital Library

[23]

D. Yang, G. Xue, X. Fang, and J. Tang, “Incentive mechanisms for crowdsensing: Crowdsourcing with smartphones,” IEEE/ACM Trans. Netw., vol. 24, no. 3, pp. 1732–1744, Jun. 2016.

Digital Library

[24]

H. Jin, L. Su, D. Chen, K. Nahrstedt, and J. Xu, “Quality of information aware incentive mechanisms for mobile crowd sensing systems,” in Proc. 16th ACM Int. Symp. Mobile Ad Hoc Netw. Comput., 2015, pp. 167–176.

[25]

L. Mashayekhy, M. M. Nejad, and D. Grosu, “Physical machine resource management in clouds: A mechanism design approach,” IEEE Trans. Cloud Comput., vol. 3, no. 3, pp. 247–260, Jul.–Sep. 2015.

[26]

A. Kiani and N. Ansari, “Toward hierarchical mobile edge computing: An auction-based profit maximization approach,” IEEE Internet Things J., vol. 4, no. 6, pp. 2082–2091, Dec. 2017.

[27]

Z. Zheng, F. Wu, and G. Chen, “A strategy-proof combinatorial heterogeneous channel auction framework in noncooperative wireless networks,” IEEE Trans. Mobile Comput., vol. 14, no. 6, pp. 1123–1137, Jun. 2015.

[28]

M. Salek and D. Kempe, “Auctions for share-averse bidders,” in Proc. Int. Workshop Internet Netw. Econ., 2008, pp. 609–620.

[29]

P. Jehiel and B. Moldovanu, “Efficient design with interdependent valuations,” Econometrica, vol. 69, no. 5, pp. 1237–1259, 2001.

[30]

D. Zhao, X.-Y. Li, and H. Ma, “How to crowdsource tasks truthfully without sacrificing utility: Online incentive mechanisms with budget constraint,” in Proc. IEEE Conf. Comput. Commun., 2014, pp. 1213–1221.

[31]

N. C. Luong, D. Niyato, P. Wang, and Z. Xiong, “Optimal auction for edge computing resource management in mobile blockchain networks: A deep learning approach,” in Proc. IEEE Int. Conf. Commun., May 2018, pp. 1–6.

[32]

N. Nisan, T. Roughgarden, E. Tardos, and V. V. Vazirani, Algorithmic Game Theory, vol. 1. Cambridge, U.K.: Cambridge Univ. Press, 2007.

[33]

D. Kraft, “Difficulty control for blockchain-based consensus systems,” Peer-to-Peer Netw. Appl., vol. 9, no. 2, pp. 397–413, 2016.

[34]

A. Narayanan, J. Bonneau, E. Felten, A. Miller, and S. Goldfeder, Bitcoin and Cryptocurrency Technologies: A Comprehensive Introduction. Princeton, NJ, USA: Princeton Univ. Press, 2016.

Digital Library

[35]

N. Z. Aitzhan and D. Svetinovic, “Security and privacy in decentralized energy trading through multi-signatures, blockchain and anonymous messaging streams,” IEEE Trans. Depend. Sec. Comput., vol. 15, no. 5, pp. 840–852, Sep./Oct. 2018.

[36]

M. Li, J. Weng, A. Yang, W. Lu, Y. Zhang, L. Hou, L. Jia-Nan, Y. Xiang, and R. Deng, “CrowdBC: A blockchain-based decentralized framework for crowdsourcing,” IEEE Trans. Parallel Distrib. Syst., 2018.

[37]

R. B. Myerson, “Optimal auction design,” Math. Operations Res., vol. 6, no. 1, pp. 58–73, 1981.

Digital Library

[38]

V. Krishna, Auction Theory. Cambridge, MA, USA: Academic Press, 2009.

[39]

J. C. Lagarias and A. M. Odlyzko, “Solving low-density subset sum problems,” J. ACM, vol. 32, no. 1, pp. 229–246, 1985.

Digital Library

[40]

L. Lovász, “Submodular functions and convexity,” in Mathematical Programming The State of the Art, Berlin, Germany: Springer, 1983, pp. 235–257.

[41]

J. Lee, V. S. Mirrokni, V. Nagarajan, and M. Sviridenko, “Non-monotone submodular maximization under matroid and knapsack constraints,” in Proc. 41st Annu. ACM Symp. Theory Comput., 2009, pp. 323–332.

[42]

N. Nisan, “Chapter 9-Algorithmic mechanism design: Through the lens of multiunit auctions,” Handbook of Game Theory with Economic Applications, vol. 4, Amsterdam, Netherlands: Elsevier, 2015, pp. 477–515.

[43]

K. Suankaewmanee, D. T. Hoang, D. Niyato, S. Sawadsitang, P. Wang, and Z. Han, “Performance analysis and application of mobile blockchain,” in Proc. Int. Conf. Comput. Netw. Commun., Mar. 2018, pp. 642–646.

Cited By

Ghasemi A(2025)A New Blockchain-Based Auction Method for Resource Allocation in Fog Computing EnvironmentJournal of Network and Systems Management10.1007/s10922-024-09883-z33:1Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1007/s10922-024-09883-z
Peng CAlatas B(2024)An Exploratory Study on the Application of Blockchain Technology to the Chinese Ship Auction MarketInternational Journal of Information Technologies and Systems Approach10.4018/IJITSA.34681917:1(1-18)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.4018/IJITSA.346819
Zhang JWang ZVasilakos ALi W(2024)A resource competition-based truthful mechanism for IoV edge computing resource allocation with a lowest revenue limitJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00572-x13:1Online publication date: 10-Jan-2024
https://dl.acm.org/doi/10.1186/s13677-023-00572-x
Show More Cited By

Index Terms

Auction Mechanisms in Cloud/Fog Computing Resource Allocation for Public Blockchain Networks

Index terms have been assigned to the content through auto-classification.

Recommendations

A combinatorial double auction resource allocation model in cloud computing

Users and providers have different requirements and objectives in an investment market. Users will pay the lowest price possible with certain guaranteed levels of service at a minimum and providers would follow the strategy of achieving the highest ...
A truthful and budget-balanced double auction model for resource allocation in cloud computing
Abstract
This study aimed to improve the truthfulness and efficiency of double auction mechanism in the cloud computing environment. In an auction, bidders have a high incentive to announce an unrealistic price, that is, each cloud user tends to announce a ...
A systematic study of double auction mechanisms in cloud computing

A detailed study of the double auction mechanisms in cloud is provided.A framework for double auction in cloud is proposed for a future cloud market.A model TMDA is proposed to infer how a truthful double auction can be designed.TMDA is asymptotically ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 30, Issue 9

Sept. 2019

228 pages

ISSN:1045-9219

Issue’s Table of Contents

1045-9219 © 2019 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications standards/publications/rights/index.html for more information.

Publisher

IEEE Press

Publication History

Published: 01 September 2019

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 30 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ghasemi A(2025)A New Blockchain-Based Auction Method for Resource Allocation in Fog Computing EnvironmentJournal of Network and Systems Management10.1007/s10922-024-09883-z33:1Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1007/s10922-024-09883-z
Peng CAlatas B(2024)An Exploratory Study on the Application of Blockchain Technology to the Chinese Ship Auction MarketInternational Journal of Information Technologies and Systems Approach10.4018/IJITSA.34681917:1(1-18)Online publication date: 21-Jun-2024
https://dl.acm.org/doi/10.4018/IJITSA.346819
Zhang JWang ZVasilakos ALi W(2024)A resource competition-based truthful mechanism for IoV edge computing resource allocation with a lowest revenue limitJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-023-00572-x13:1Online publication date: 10-Jan-2024
https://dl.acm.org/doi/10.1186/s13677-023-00572-x
Yang HZhang XWu ZWang LChen XLiu L(2024)Co-Sharding: A Sharding Scheme for Large-Scale Internet of Things ApplicationDistributed Ledger Technologies: Research and Practice10.1145/36412903:1(1-16)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1145/3641290
Chen LGao FBai YWu JZhou PXu Z(2024)Privacy-Preserving Blockchained Edge Resource Auction With Fraud ResistanceIEEE Transactions on Network and Service Management10.1109/TNSM.2024.337767321:4(4076-4089)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TNSM.2024.3377673
Zhang JZong MVasilakos ALi W(2024)UAV Base Station Network Transmission-Based Reverse Auction Mechanism for Digital Twin Utility MaximizationIEEE Transactions on Network and Service Management10.1109/TNSM.2023.330152221:1(324-340)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TNSM.2023.3301522
Zuo YGui LCui KGuo JXiao FJin S(2024)Mobile Blockchain-Enabled Secure and Efficient Information Management for Indoor Positioning With Federated LearningIEEE Transactions on Mobile Computing10.1109/TMC.2024.340779223:12(12176-12194)Online publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1109/TMC.2024.3407792
Zhang JZhang YWu HLi W(2024)An Ordered Submodularity-Based Budget-Feasible Mechanism for Opportunistic Mobile Crowdsensing Task Allocation and PricingIEEE Transactions on Mobile Computing10.1109/TMC.2022.323251323:2(1278-1294)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1109/TMC.2022.3232513
Lin GZeng MShan ZWu KWang GLei K(2024)Blockchain-based cooperative game bilateral matching architecture for shared storageFuture Generation Computer Systems10.1016/j.future.2024.04.016158:C(122-137)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1016/j.future.2024.04.016
Zhang JSun HLi W(2024)Lowest revenue limit-based truthful auction mechanism for cloud resource allocationThe Journal of Supercomputing10.1007/s11227-023-05839-380:8(10637-10666)Online publication date: 1-May-2024
https://dl.acm.org/doi/10.1007/s11227-023-05839-3
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents