Distributed selfish load balancing

被引:34
作者
Berenbrink, Petra [1 ]
Friedetzky, Tom [2 ]
Goldberg, Leslie Ann [3 ]
Goldberg, Paul W. [3 ]
Hu, Zengjian [1 ]
Martin, Russell [3 ]
机构
[1] Simon Fraser Univ, Sch Comp Sci, Burnaby, BC V5A 1S6, Canada
[2] Univ Durham, Dept Comp Sci, Sci Labs, Durham DH1 3LE, England
[3] Univ Liverpool, Dept Comp Sci, Liverpool L69 3BX, Merseyside, England
基金
英国工程与自然科学研究理事会;
关键词
load balancing; reallocation; equilibrium; convergence;
D O I
10.1137/060660345
中图分类号
TP301 [理论、方法];
学科分类号
081202 [计算机软件与理论];
摘要
Suppose that a set of m tasks are to be shared as equally as possible among a set of n resources. A game-theoretic mechanism to find a suitable allocation is to associate each task with a "selfish agent" and require each agent to select a resource, with the cost of a resource being the number of agents that select it. Agents would then be expected to migrate from overloaded to underloaded resources, until the allocation becomes balanced. Recent work has studied the question of how this can take place within a distributed setting in which agents migrate selfishly without any centralized control. In this paper we discuss a natural protocol for the agents which combines the following desirable features: It can be implemented in a strongly distributed setting, uses no central control, and has good convergence properties. For m >> n, the system becomes approximately balanced (an epsilon-Nash equilibrium) in expected time O(log log m). We show using a martingale technique that the process converges to a perfectly balanced allocation in expected time O(log log m+ n(4)). We also give a lower bound of Omega(max{log log m, n}) for the convergence time.
引用
收藏
页码:1163 / 1181
页数:19
相关论文
共 29 条
[1]
Ackermann H, 2006, ANN IEEE SYMP FOUND, P613
[2]
Blum Avrim, 2006, Proc. 25th ACM Symp. on Principles of Distributed Computing, P45
[3]
Chien S, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P169
[4]
Czumaj A, 2003, LECT NOTES COMPUT SC, V2764, P240
[5]
Czumaj A, 2002, SIAM PROC S, P413
[6]
Czumaj A., 2002, ACM S THEORY COMPUTI, P287
[7]
Even-Dar E, 2003, LECT NOTES COMPUT SC, V2719, P502
[8]
Even-Dar E, 2005, PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P772
[9]
Fabrikant A, 2004, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, P604
[10]
FELDMANN R, 2003, P 30 INT C AUT LANG, V2719, P514