An asynchronous load balancing scheme for multi-server systems
Fang Cherry Liu, Yi Chen, Wing Shing Wong · 2016
In this paper, load balancing is defined as the process of allocating workload to reduce the mean job waiting time. In a distributed multi-server system, load balancing is a challenging task if there is no central coordination or time-synchronization among users. In this paper, we present a queuing model for a distributed asynchronous multi-server system. To realize load balancing, we propose a distributed algorithm based on protocol sequences, which are deterministic binary sequences and preassigned to users. The goal of this paper is to find optimal sequence sets which minimize the maximum mean job waiting time for all possible relative time shifts among users. We extend previous results reported in the literature to show that Shift-Invariant (SI) protocol sequences can ensure that the mean job waiting time is invariant for different time shifts. Moreover, our numerical studies indicate that the load balancing scheme based on SI sequences outperform the random sequence scheme, the completely random scheme and the probabilistic scheme.