k серверов: почему ближайший не всегда лучший

Если умеешь считать цену движения обоих серверов - переходи к «Теперь сам».

Как думаешь: почему нельзя всегда посылать ближайшего?

Два сервера стоят в точках 1 и 10 прямой. Запросы чередуются между 0 и 1. Ближайший сервер из точки 1 каждый раз пробегает единицу туда или обратно; далёкий остаётся в точке 10. После ста повторений цена растёт, хотя достаточно один раз разместить серверы в 0 и 1 и больше не двигаться.

Онлайн-алгоритм не знает, насколько долго продлится серия. Но постоянное игнорирование далёкого ресурса означает, что знания о повторяющихся запросах никак не меняют конфигурацию. Нужен механизм, постепенно смещающий её к месту работы без предсказания длины серии.

На что это похоже

Представь две ремонтные бригады на длинной улице. Если всегда отправлять ближайшую, одна может ездить между двумя домами, пока вторая стоит далеко без работы. Двойное покрытие при запросе между бригадами сдвигает обе к месту поломки. Иногда это лишний путь прямо сейчас, зато конфигурация перестаёт бесконечно оплачивать одну и ту же ошибку размещения.

Механизм: геометрия и конкурентная граница

Метрика задаёт неотрицательное симметричное расстояние, нулевое только между совпадающими точками, с неравенством треугольника. Конфигурация - позиции всех серверов. Запрос обслужен, если хотя бы один сервер оказался в запрошенной точке. Цена шага складывает путь всех двигавшихся серверов, включая тех, кто до запроса не дошёл.

На прямой позиции упорядочены. Если запрос левее всех серверов, движется только крайний левый; справа - крайний правый. Внутри промежутка выбираются ближайший сервер слева и ближайший справа. Они идут навстречу запросу с одинаковой скоростью до первого достижения. При уже стоящем на запросе сервере движение не нужно. Порядок серверов сохраняется, поэтому они не перескакивают через соседей.

Конкурентность означает ALG(σ) ≤ k·OPT(σ) + C, где константа C зависит от начальной конфигурации, но не от последовательности запросов. Доказательство double coverage сравнивает минимальное сопоставление серверов алгоритма с серверами оптимума и сумму попарных расстояний между собственными серверами. Потенциал k умножить на цену сопоставления плюс сумма внутренних расстояний неотрицателен. Движение оптимума увеличивает его не больше чем в k раз от цены движения, а движение double coverage уменьшает достаточно, чтобы оплатить текущий шаг. При суммировании остаётся начальный потенциал. Это объясняет одновременно коэффициент и допустимую добавочную константу.

Для общего пространства детерминированная нижняя граница равна k при наличии хотя бы k+1 точек. Противник запрашивает точку без сервера; онлайн-алгоритм вынужден двигаться. Оптимум, знающий всю последовательность, выбирает конфигурации выгоднее. Гипотеза утверждает достижимость этой границы на любой метрике; результат для прямой сам по себе общего случая не решает. Рандомизированная версия и условия осведомлённости противника задают другой вопрос.

Метрическая система задач, MTS, обобщает модель. Есть конечные состояния с метрической ценой перехода. Приходит вектор стоимостей обслуживания: для каждого состояния указано, сколько стоит выполнить текущую задачу в нём. Алгоритм выбирает состояние и платит движение плюс обслуживание. Для k серверов состояние - вся конфигурация, расстояние - цена минимального сопоставления старых и новых позиций, а обслуживание нулевое в конфигурациях с сервером на запросе и запрещено в остальных. Число конфигураций может быть огромным, поэтому такое сведение объясняет модель, но не автоматически даёт быструю реализацию.

Правило

Цена k-серверного шага - весь путь всех серверов. На прямой double coverage k-конкурентен, а ближайший сервер без изменения конфигурационной стратегии такой гарантии не имеет. MTS добавляет к цене перехода стоимость выполнения задачи в выбранном состоянии.

Разбор: повторяющиеся запросы обучают конфигурацию

Файл сравнивает жадный выбор, double coverage и точный офлайн-оптимум для двух серверов. Оптимум хранит все возможные конечные конфигурации после очередного запроса. Это экспоненциально широкая идея в общем случае, но на трёх точках и двух серверах всё помещается в несколько состояний.

from bisect import bisect_left


def online(start, zaprosy, double):
    s = sorted(start)
    cena = 0
    for r in zaprosy:
        if r in s:
            continue
        i = bisect_left(s, r)
        if not double or i in (0, len(s)):
            j = min(range(len(s)), key=lambda j: abs(s[j] - r))
            cena += abs(s[j] - r)
            s[j] = r
        else:
            d = min(r - s[i - 1], s[i] - r)
            s[i - 1] += d
            s[i] -= d
            cena += 2 * d
        s.sort()
    return cena, tuple(s)


def offline(start, zaprosy):
    dp = {tuple(sorted(start)): 0}
    for r in zaprosy:
        novoe = {}
        for s, cena in dp.items():
            for j in range(len(s)):
                t = list(s)
                t[j] = r
                t = tuple(sorted(t))
                c = cena + abs(s[j] - r)
                novoe[t] = min(novoe.get(t, float('inf')), c)
        dp = novoe
    return min(dp.values())


for povtory in [5, 20, 100]:
    zaprosy = [0, 1] * povtory
    print('пар запросов', povtory,
          'жадно', online([1, 10], zaprosy, False)[0],
          'DC', online([1, 10], zaprosy, True)[0],
          'OPT', offline([1, 10], zaprosy))
print('конфигурация DC:', online([1, 10], [0, 1] * 20, True)[1])

пар запросов 5 жадно 10 DC 15 OPT 10
пар запросов 20 жадно 40 DC 28 OPT 10
пар запросов 100 жадно 200 DC 28 OPT 10
конфигурация DC: (0, 1)

Жадная цена растёт с числом запросов, а оптимальная ограничена. Double coverage сначала платит за приближение второго сервера, затем перестаёт двигаться. Серия сама проверяет, что алгоритм действительно меняет конфигурацию, а не просто обслуживает каждый запрос локально дёшево.

Разбор: запрос ровно посередине

Серверы стоят в 0 и 10, запрос в 5. Double coverage движет обоих на пять единиц, суммарная цена десять. Хотя хватило бы движения одного сервера за пять, правило не ошибочно: конкурентная гарантия сравнивает всю последовательность, а не каждый шаг отдельно. Если платить только за дошедший сервер, программа занизит стоимость и проверка гарантии станет фиктивной. При совпадении обоих в точке 5 следующий крайний запрос снова выбирает одну из совпавших копий.

Что ломается без этого

Оптимизация только текущего перемещения не обеспечивает конкурентность. Взвешенные серверы, асимметричные переходы и возможность отказаться от запроса меняют модель. Перенос прямолинейного правила «слева и справа» на произвольную метрику невозможен без определения соседства и нового доказательства. Связь с кешем действует для равномерной метрики, а не для любых стоимостей загрузки.

Зачем это в работе

Перемещение ресурсов между площадками, позиционирование манипуляторов и кеширование используют одинаковую идею: цена решения зависит от того, какую конфигурацию оставили будущему. MTS удобна, когда помимо миграции есть стоимость работы в текущем месте. Полезно явно записать обе цены, иначе алгоритм «всегда оставайся» или «всегда переезжай» победит только из-за пропущенного слагаемого.

Теперь сам

Серверы в 2 и 12, запрос в 6. Куда сдвинет их double coverage и сколько заплатит?