Decentralised load balancing in closed and open systems
Seminar Room 1, Newton Institute
We study the performance of random load resampling strategies in parallel server systems. Clients initially attach to an arbitrary server, but may switch server independently at random instants of time in an attempt to improve their service rate. Load resampling is particularly relevant in scenarios where clients cannot predict the load of a server before being actually attached to it.
We derive tight estimates of the time it takes for a given resampling strategy to achieve a perfect balance of the load across servers in a closed system. We also study open systems where clients arrive according to a random process and leave upon service completion. In this scenario, we characterize the stability region of various resampling strategies, and derive approximate estimates of the sojourn time obtained by letting the number of servers grow large.