Robust Load Balancing with Machine Learned Advice
Sara Ahmadian, Hossein Esfandiari, Vahab Mirrokni, Binghui Peng; 24(44):1−46, 2023.
Abstract
This study introduces and examines a theoretical model for load balancing of large databases, specifically commercial search engines, in order to efficiently manage computational resources. The model is an enhanced version of the well-received \\bab model, with an additional constraint that restricts the number of servers that store each data piece. This constraint is crucial when dealing with extremely large data sets that cannot be copied entirely onto each server, while also considering time-dependent changes in query demand for each data piece. The paper presents an almost optimal load balancing algorithm that operates based on load estimates for each data piece. The algorithm demonstrates robustness even when facing incorrect load estimates, achieving a performance level of $1-1/e$, which is provably optimal. Additionally, the study develops techniques for analyzing the balls-into-bins process under certain correlations and establishes a unique connection with the multiplicative weights update scheme.
[abs]