Fast load balancing via bounded best response
Fast load balancing via bounded best response
复制标题
通过有界最佳响应实现快速负载平衡
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
R. Khandekar
中科院分区：
文献类型：
--
作者：
B. Awerbuch;Y. Azar;R. Khandekar
众所周知，当用户顺序播放时，在非合件用户环境中最佳响应的动态可能会收敛到一个好的解决方案，但是当用户同时播放时，可能会偏离全局最佳解决方案。我们介绍了有限最佳响应的概念，其中用户应对最佳响应做出反应，但要受系统本地强迫的规则。我们研究了双方图模型中计算机上负载平衡任务的问题，并表明并发有限的最佳响应的动力学快速收敛到接近最佳的解决方案，即使用多同伴数量的回合数。这与并发的最佳响应动力学相反，该动力学距离最佳和任何顺序动力学，该动力学至少需要线性数量的回合才能达到合理的解决方案。
It is known that the dynamics of best response in an environment of non-cooperative users may converge to a good solution when users play sequentially, but may cycle far away from the global optimum solution when users play concurrently. We introduce the notion of bounded best response where users react with best response subject to rules that are forced locally by the system. We investigate the problem of load balancing tasks on machines in a bipartite graph model and show that the dynamics of concurrent bounded best response converges to a near-optimum solution quickly, i.e., with poly-logarithmic number of rounds. This is in contrast to the concurrent best response dynamics which cycles far away from the optimum and to any sequential dynamics which requires at least a linear number of rounds to get to a reasonable solution.