Deterministic and Randomized Algorithms for Distributed On-Line Task Assignment and Load Balancing without Load Status Information

We find two interesting thresholds for the number of tasks generated under a new model of distributed on-line task assignment and load balancing environment, in which tasks are assigned without any information of current load status and load balancing is achieved together with task assignment. It is shown that balanced load distribution can be obtained deterministically when the number of tasks exceeds the first threshold. Otherwise, a simple randomized strategy can achieve balanced load distribution with high probability if the number of tasks exceeds the second threshold. Received October 30, 2000, and in revised form May 10, 2001. Online publication October 30, 2001.