Load balancing without regret in the bulletin board model
Load balancing without regret in the bulletin board model
复制标题
布告栏模型中的负载均衡无悔
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
É. Tardos
中科院分区：
文献类型：
--
作者：
Robert D. Kleinberg;G. Piliouras;É. Tardos
我们根据在线学习理论中的无regret算法在分布式系统中进行负载平衡的协议的性能。最佳的策略是我们的方法。系统的性能和行为。玩家可以在所有机器上找到延迟，但是如果他们选择了另一台机器，则没有信息延迟的信息。所有玩家都使用众所周知的乘法算法，那么所得解决方案的质量呈指数优于最差的相关等效物，并且几乎与最差的NASH一样好。 - 代理学习系统。
We analyze the performance of protocols for load balancing in distributed systems based on no-regret algorithms from online learning theory. These protocols treat load balancing as a repeated game and apply algorithms whose average performance over time is guaranteed to match or exceed the average performance of the best strategy in hindsight. Our approach captures two major aspects of distributed systems. First, in our setting of atomic load balancing, every single process can have a significant impact on the performance and behavior of the system. Furthermore, although in distributed systems participants can query the current state of the system they cannot reliably predict the effect of their actions on it. We address this issue by considering load balancing games in the bulletin board model, where players can find out the delay on all machines, but do not have information on what their experienced delay would have been if they had selected another machine. We show that under these more realistic assumptions, if all players use the well-known multiplicative weights algorithm, then the quality of the resulting solution is exponentially better than the worst correlated equilibrium, and almost as good as that of the worst Nash. These tighter bounds are derived from analyzing the dynamics of a multi-agent learning system.