Online client-server load balancing without global information
Baruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton · 2005
We consider distributed online algorithms for maximizing throughput in a network of clients and servers, modeled as a bipartite graph. Unlike most prior work on online load balancing, we do not assume centralized control and seek algorithms and lower bounds for decentralized algorithms in which each participant has only local knowledge about the state of itself and its neighbors. Our problem can be seen as analogous to the recent work on oblivious routing in [8, 14, 19], but with the objective of maximizing throughput rather than minimizing congestion. In contrast to that work, we prove a strong lower bound (polynomial in n, the size of the graph) on the competitive ratio of any oblivious algorithm. This is accompanied by simple algorithms achieving upper bounds which are tight in terms of k, the maximum throughput achievable by an omniscient algorithm. Finally, we examine a restricted model in which clients, upon becoming active, must remain so for at least log(n) time steps. In contrast to the primarily negative results in the oblivious case, here we present an algorithm which is constantcompetitive. Our lower bounds justify the intuition, implicit in earlier work on the subject [2], that some such restriction (i.e. requiring some stability in the demand pattern over time) is necessary in order to achieve a constant — or even polylogarithmic — competitive ratio. 1