Zero-wait load balancing with sparse messaging

A key challenge in designing load balancing strategies is to achieve low delay in large-scale systems while only using minimal communication overhead. Motivated by these issues, we introduce a novel scheme in which the dispatcher becomes aware of idle servers without any explicit communication from either side, using absence of messages at predefined time instants. The proposed scheme achieves provably vanishing queueing delays while using strictly less than one message per job on average.