A Game-Theoretic Analysis of Shared/Buy-in Computing Systems
A Game-Theoretic Analysis of Shared/Buy-in Computing Systems
复制标题
共享/购买计算系统的博弈论分析
DOI：
10.1109/ojcoms.2020.2969646
复制
发表时间：
2020
影响因子：
7.9
通讯作者：
Starobinski, David
中科院分区：
文献类型：
--
作者：
Shi, Zhenpeng;Bestavros, Azer;Orda, Ariel;Starobinski, David
高性能计算集群越来越多地在共享/买入范例下操作。在这种模式下，用户可以在两个服务层之间进行选择：共享服务和购买服务。共享服务为用户提供免费访问共享资源的权限，而购买服务允许用户购买额外的购买资源，以缩短作业完成时间。共享/买入计算系统的一个重要特征包括使未使用的买入资源对系统的所有其他用户可用。这种特征已被证明可以提高资源的利用率。同时，它在用户之间创建了策略交互，从而在系统层面上产生了非合作游戏。具体来说，每个用户都面临着是否购买购买资源的问题，如果是这样，需要支付多少钱。在相当一般的条件下，我们建立了一个共享/买入计算游戏产生一个唯一的纳什均衡，它可以在多项式时间内计算。我们为此提供了一个算法，它可以以分布式的方式实现。此外，通过建立一个连接到聚合博弈理论，我们证明了游戏收敛到纳什均衡，通过最佳反应动力学从任何初始状态。我们证明了我们的模型使用真实的数据从计算集群的基本博弈论假设，并进行数值模拟，以进一步探索收敛特性和系统参数的纳什均衡的影响。特别是，我们指出潜在的不公平和滥用问题，并讨论解决方案的场所。
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.
登录
查看更多内容
共享/购买计算生态系统的案例研究
DOI：
10.1007/s10586-018-2256-2
发表时间：
2018
期刊：
Cluster Computing
影响因子：
--
作者：
Liao, Christopher;Klausner, Yonatan;Starobinski, David;Simhon, Eran;Bestavros, Azer
通讯作者：
Bestavros, Azer
提前预约游戏
影响因子：
0.6
作者：
Eran Simhon;D. Starobinski
通讯作者：
D. Starobinski
影响因子：
16.4
作者：
E. Meirom;Shie Mannor;A. Orda
通讯作者：
A. Orda
DOI：
--
发表时间：
2006
期刊：
--
影响因子：
--
作者：
Iroon Polytechniou-
通讯作者：
Iroon Polytechniou-
DOI：
10.1111/j.1467-9779.2007.00304.x
发表时间：
2006
期刊：
PSN: Game Theory & Experiments (Topic)
影响因子：
--
作者：
R. Cornes
通讯作者：
R. Cornes