Tight Bounds for Selfish and Greedy Load Balancing
Lists
Only you see this
Abstract
We study the load balancing problem in the context of a set of clients each wishing to run a job on a server selected among a subset of permissible servers for the particular client. We consider two different scenarios. In selfish load balancing, each client is selfish in the sense that it selects to run its job to the server among its permissible servers having the smallest latency given the assignments of the jobs of other clients to servers. In online load balancing, clients appear online and, when a client appears, it has to make an irrevocable decision and assign its job to one of its permissible servers. Here, we assume that the clients aim to optimize some global criterion but in an online fashion. A natural local optimization criterion that can be used by each client when making its decision is to assign its job to that server that gives the minimum increase of the global objective. This gives rise to greedy online solutions. The aim of this paper is to determine how much the quality of load balancing is affected by selfishness and greediness.
BibTeX
@inproceedings{caragiannis2006tight,
author = {Ioannis Caragiannis and Michele Flammini and Christos Kaklamanis and Panagiotis Kanellopoulos and Luca Moscardelli},
title = {{Tight Bounds for Selfish and Greedy Load Balancing}},
booktitle = {ICALP},
year = {2006},
doi = {10.1007/11786986\_28},
}Loading related content...