James Aspnes, Yang Richard Yang, and Yitong Yin. Path-independent load balancing with unreliable machines. Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, January 2007, pp. 814–823. Available as arXiv:cs.DS/0607026.

We consider algorithms for load balancing on unreliable machines.
The objective is to optimize the two criteria of minimizing the makespan
and minimizing job reassignments in response to machine failures.
We assume that the set of jobs is known in advance but that the
pattern of machine failures is unpredictable. Motivated by the
requirements of BGP routing, we consider
*path-independent* algorithms, with the property that the job
assignment is completely determined by the subset of available
machines and not the previous history of the assignments.
We examine first the question of performance measurement of path-independent
load-balancing algorithms, giving the measure of makespan and the normalized measure of
reassignments cost. We then describe two classes of algorithms for
optimizing these measures against an oblivious adversary for
identical machines.
The first, based on independent random
assignments, gives expected reassignment costs within a factor of 2
of optimal
and gives a makespan within a factor of
O(log m/log log m) of optimal with high probability, for
unknown job sizes.
The second, in which jobs are first grouped into bins and at most one bin
is assigned to each machine,
gives constant-factor ratios on both reassignment cost and makespan, for
known job sizes.
Several open problems are discussed.

- SODA 2007 proceedings version:
**PDF**. - ArXiv version: arXiv:cs.DS/0607026.

@inproceedings{AspnesYY2007, author = {James Aspnes and Yang Richard Yang and Yitong Yin}, title = {Path-independent load balancing with unreliable machines}, month = jan, year = {2007}, booktitle="Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms", pages = {814--823} }

Consolidated BibTeX file

Return to James Aspnes's publications

Return to James Aspnes's home page