Справедливость в задаче о k-серверах: новый взгляд на баланс нагрузки

В рассматриваемой конфигурации, сложный случай для теоремы 12 демонстрирует, как запросы, последовательно сдвигающие сервер [latex]s_1[/latex] вдоль магистрали, вынуждают его пройти всю длину, в то время как остальные серверы несут лишь незначительные дополнительные затраты, порядка [latex]O(1)[/latex].

В статье представлена формальная оценка справедливости алгоритмов обслуживания в классической задаче о k-серверах и предложены методы достижения оптимального баланса без потери эффективности.