  With the rapid increase in the size and volume of cloud services and data
centers, architectures with multiple job dispatchers are quickly becoming the
norm. Load balancing is a key element of such systems. Nevertheless, current
solutions to load balancing in such systems admit a paradoxical behavior in
which more accurate information regarding server queue lengths degrades
performance due to herding and detrimental incast effects. Indeed, both in
theory and in practice, there is a common doubt regarding the value of
information in the context of multi-dispatcher load balancing. As a result,
both researchers and system designers resort to more straightforward solutions,
such as the power-of-two-choices to avoid worst-case scenarios, potentially
sacrificing overall resource utilization and system performance. A principal
focus of our investigation concerns the value of information about queue
lengths in the multi-dispatcher setting. We argue that, at its core, load
balancing with multiple dispatchers is a distributed computing task. In that
light, we propose a new job dispatching approach, called Tidal Water Filling,
which addresses the distributed nature of the system. Specifically, by
incorporating the existence of other dispatchers into the decision-making
process, our protocols outperform previous solutions in many scenarios. In
particular, when the dispatchers have complete and accurate information
regarding the server queues, our policies significantly outperform all existing
solutions.
