Dynamic Load Balancing with Tokens

The assignment of jobs to servers in a computer cluster is subject to many practical constraints like data locality. This brings the need for simple load balancing schemes that capture these constraints in the assignment decision. In this paper, we propose a token-based mechanism that balances load without requiring an a priori knowledge on job arrival rates and server capacities.We show that this mechanism is a sequential implementation of the insensitive load balancing introduced by Bonald et al. We also observe numerically that it often outperforms the best static load balancing.