Dual and multiple token based approaches for load balancing

In distributed systems uneven arrivals of the tasks may overload a few hosts while some of the hosts may be lightly loaded. This load imbalance prevents distributed systems from delivering its performance to its capacity. Load balancing has been advocated as a means of improving performance and reliability of distributed systems. We propose a distributed load balancing algorithm LoGTra to deal with this problem. LoGTra uses load graph and token based policy. The extensions to LoGTra based on dual tokens DTLB and multiple tokens m-LoGTra are proposed in this paper. m-LoGTra allows host to generate multiple tokens. This allows system to search host for load balancing in multiple directions and can avoid starvation of remote hosts. Local maxima and local minima are responsible for initiating transfer and that limits the number of hosts generating tokens at a time. As overheads are kept under control by limiting number of tokens, the algorithm promises for improved performance.