非服从性分布式系统中博弈分析法下的副本放置问题

为解决非服从性分布式系统中多数据、多节点、有容量限制的副本放置问题,建立了副本放置模型以及向博弈模型的映射,分析了在无容量限制及有容量限制下纳什均衡的存在性问题以及纳什均衡的优化程度。考虑到纳什均衡获取的时间不可行,提出了无删除副本放置局面的定义,设计了该局面的获取算法并分析算法的相关性质。模拟实验显示了无删除副本放置局面获取算法下系统平均副本数和总代价随节点的容量及放置代价变化的过程,同时在小节点规模下与最优副本放置结果进行比较,结果显示纳什均衡带来的系统总代价不会与最优系统总代价有大的差别,说明在保证个体利益最大化时,全局的效益并不会有大的损害。

Replica Placement Analysis Under Game Theory in Non-Obedient Distributed System

To solve the replica placement with multi-data and multi-node in non-obedient distributed system,the replica placement model is established and is reflected in game model.In replica placement game model,the existence of Nash equilibrium is discussed under situations with or without capacity restriction.Then price of anarchy（PoA） is also analyzed.To avoid the time infeasibility in Nash equilibrium obtaining,replica placement without deletion is defined,obtaining algorithm is presented and analyzed.Simulations show the relations among capacity,placement cost,system average number of replicas and system total cost during the algorithm executing process.Meanwhile,in small scale,total cost caused by Nash equilibrium threr is not much difference between total cost caused by optimal solution and,indicating that when individual utility is maximized,the global utility is not damaged greatly.