Исследователи Google, Рави Кумар и Маниш Пурохит, представили новые достижения в области балансировки нагрузки для систем управления кластером. В своей работе они акцентируют внимание на классических задачах планирования, исследуя, как оптимально распределять вычислительные нагрузки при случайном порядке поступления задач.
Балансировка нагрузки — это ключевой аспект современных кластеров, таких как Borg от Google, которые обрабатывают сотни тысяч задач на десятках тысяч машин. Основная цель таких систем — максимизация производительности и устойчивости. Улучшая алгоритмы, которые минимизируют максимальную нагрузку на машины, ученые установили новые нижние и верхние границы работоспособности для детерминированных алгоритмов в условиях неопределенности.
Особое внимание уделяется играми, где необходимо ориентировать графы без предварительной информации о будущих задачах. Результаты показывают, что эффективность алгоритмов ограничена, но новые методы позволяют значительно улучшить конкурентные коэффициенты, что открывает новые возможности для оптимизации систем управления ресурсами.