Load Balancing and the Power of Preventive Probing

Consider a randomized load balancing problem consisting of a large number n of server sites each equipped with K servers. Under the greedy policy, clients randomly probe a site to check whether there is still a server available. If not, d - 1 other sites are probed and the task is assigned to the site with the fewest number of busy servers. If all the servers are also busy in each of these d - 1 sites, the task is lost. This paper analyzes a set of policies, i.e., (L; d) policies, that will occasionally probe additional sites even when there is still a server available at the site that was probed first.