  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.
