Abstract Load balancing is a classical and important problem arising in a number of
application scenarios. Consider the following canonical abstraction: Jobs arrive according to
an arrival process at a bank of N identical servers each having a separate queue. The
arriving jobs need to be assigned to the servers so that load on the servers is well balanced.
The policy” join the server with shortest remaining work” is known to be an optimal policy
(Winston, 1977). When N is large, the complexity of implementing this optimal scheme …