  In geographically-distributed systems, communication latencies are
non-negligible. The perceived processing time of a request is thus composed of
the time needed to route the request to the server and the true processing
time. Once a request reaches a target server, the processing time depends on
the total load of that server; this dependency is described by a load function.
We consider a broad class of load functions; we just require that they are
convex and two times differentiable. In particular our model can be applied to
heterogeneous systems in which every server has a different load function. This
approach allows us not only to generalize results for queuing theory and for
batches of requests, but also to use empirically-derived load functions,
measured in a system under stress-testing. The optimal assignment of requests
to servers is communication-balanced, i.e. for any pair of non
perfectly-balanced servers, the reduction of processing time resulting from
moving a single request from the overloaded to underloaded server is smaller
than the additional communication latency. We present a centralized and a
decentralized algorithm for optimal load balancing. We prove bounds on the
algorithms' convergence. To the best of our knowledge these bounds were not
known even for the special cases studied previously (queuing theory and batches
of requests). Both algorithms are any-time algorithms. In the decentralized
algorithm, each server balances the load with a randomly chosen peer. Such
algorithm is very robust to failures. We prove that the decentralized algorithm
performs locally-optimal steps. Our work extends the currently known results by
considering a broad class of load functions and by establishing theoretical
bounds on the algorithms' convergence. These results are applicable for servers
whose characteristics under load cannot be described by a standard mathematical
models.
