US Patent 10055262 Distributed load balancing with imperfect workload information

A load balancer obtains respective workload metrics of various worker nodes of a distributed system. In response to determining that a work request is to be assigned, the load balancer generates a workload variation estimate associated with the worker nodes. Using the workload variation estimate, the load balancer determines a size of a candidate pool of worker nodes for the work request. The load balancer assigns the work request to a selected worker node from the candidate pool.