A game-theoretic analysis of shared/buy-in computing systems
Files
Published version
Date
2020
Authors
Shi, Zhenpeng
Bestavros, Azer
Orda, Ariel
Starobinski, David
Version
Published version
OA Version
Citation
Zhenpeng Shi, Azer Bestavros, Ariel Orda, David Starobinski. 2020. "A Game-Theoretic Analysis of Shared/Buy-in Computing Systems." IEEE Open Journal of the Communications Society, Volume 1, pp. 190 - 204. https://doi.org/10.1109/ojcoms.2020.2969646
Abstract
High performance computing clusters are increasingly operating under a shared/buy-in paradigm. Under this paradigm, users choose between two tiers of services: shared services and buy-in services. Shared services provide users with access to shared resources for free, while buy-in services allow users to purchase additional buy-in resources in order to shorten job completion time. An important feature of shared/buy-in computing systems consists of making unused buy-in resources available to all other users of the system. Such a feature has been shown to enhance the utilization of resources. Alongside, it creates strategic interactions among users, hence giving rise to a non-cooperative game at the system level. Specifically, each user is faced with the questions of whether to purchase buy-in resources, and if so, how much to pay for them. Under quite general conditions, we establish that a shared/buy-in computing game yields a unique Nash equilibrium, which can be computed in polynomial time. We provide an algorithm for this purpose, which can be implemented in a distributed manner. Moreover, by establishing a connection to the theory of aggregative games, we prove that the game converges to the Nash equilibrium through best response dynamics from any initial state. We justify the underlying game-theoretic assumptions of our model using real data from a computing cluster, and conduct numerical simulations to further explore convergence properties and the influence of system parameters on the Nash equilibrium. In particular, we point out potential unfairness and abuse issues and discuss solution venues.
Description
License
Copyright: © 2020 The Author(s). This work is licensed under a Creative Commons Attribution 4.0 License. For more information, see https://creativecommons.org/licenses/by/4.0/.