Optimal Load Balancing on Distributed Homogeneous Unreliable Processors

Zhen Liu and Rhonda Righter
Additional contact information
Zhen Liu: INRIA Centre Sophia Antipolis, Valbonne, France
Rhonda Righter: Santa Clara University, Santa Clara, California

Operations Research, 1998, vol. 46, issue 4, 563-573

Abstract: We consider optimal load balancing in a distributed computing environment consisting of homogeneous unreliable processors. Each processor receives its own sequence of tasks from outside users, some of which can be redirected to the other processors. Processing times are independent and identically distributed with an arbitrary distribution. The arrival sequence of outside tasks to each processor may be arbitrary as long as it is independent of the state of the system. Processors may fail, with arbitrary failure and repair processes that are also independent of the state of the system. The only information available to a processor is the history of its decisions for routing work to other processors, and the arrival times of its own arrival sequence.We prove the optimality of the round-robin policy, in which each processor sends all the tasks that can be redirected to each of the other processors in turn. We show that, among all policies that balance workload, round robin stochastically minimizes the n th task completion time for all n , and minimizes response times and queue lengths in a separable increasing convex sense for the entire system. We also show that if there is a single centralized controller, round-robin is the optimal policy, and a single controller using round-robin routing is better than the optimal distributed system in which each processor routes its own arrivals. Again “optimal” and “better” are in the sense of stochastically minimizing task completion times, and minimizing response time and queue lengths in the separable increasing convex sense.

Keywords: Probability; stochastic model applications; distributed routing; Queues; cyclic; optimality of round-robin routing; Dynamic programming/optimal control; semi-Markow (search for similar items in EconPapers)
Date: 1998
References: View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.46.4.563 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:46:y:1998:i:4:p:563-573

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().