Какой вопрос решают
В разных точках сети стоят k серверов. Приходит запрос в точке без сервера: кого переместить, не зная следующих запросов? Пример — кэш, если все расстояния одинаковы; произвольная метрика существенно шире этой модели.
Рукопись заявляет O(log²(k+1))-конкурентную случайную онлайн-стратегию на любой метрике. Сопутствующая работа превращает существование в равномерный алгоритм для конечных рациональных метрик, но допускает огромную цену начального периода.
Почему выбрано: Выбрано как пример важной онлайн-гарантии с особенно опасным разрывом между существованием, вычислимостью и полезностью.
До и после
Введение сопоставляет результат с прежней зависимостью от числа точек n и с нижней границей порядка log²k для худших метрик. Это не утверждение, что всякая метрика требует двух логарифмов: равномерная метрика кэширования проще. Исторические приоритеты здесь сверены по введению, а не по полному независимому обзору.
Это сопоставление по введению рукописи. Независимый исчерпывающий обзор приоритета не выполнен.
Точное утверждение и условия
110-01, теорема 1.1, PDF с. 2: k≥2, как минимум k+1 точек; для каждой конечной последовательности запросов, выбранной независимо от случайности алгоритма, E[cost] ≤ C log²(k+1)·OPT + B. C универсальна; B зависит от метрики, k и начальной конфигурации, но не от горизонта. При различных начальных точках B=0. 110-02, теорема 1.1, с. 1: конечная рациональная метрика, n≥3 и 2≤k<n; подготовка p(L), обработка запроса t — p(L+⌈log₂(t+1)⌉), один фиксированный полином.
Источник: указанные теоремы в локальных PDF ниже. Формулировка пересказана, но ключевые кванторы, модель и оговорки сохранены.
Три уровня объяснения
Следующие аналогии и объяснения — наша интерпретация, не дополнительные теоремы.
Архитектура доказательства
Пересказ вводного обзора, а не построчная проверка доказательства.
Свести геометрию запросов к согласованным иерархическим представлениям и распределению ранговых ресурсов.
Контролировать округление, изменение разбиений и перенос вероятностного состояния общей потенциальной оценкой.
В отдельной работе получить конечное битовое описание политики. На с. 2 прямо обсуждается чрезвычайно долгий начальный период обслуживания фиксированным сервером.
Что известно о проверке
Каталог scope notes связывает формализацию с основной оценкой и вычислительным дополнением. Здесь доступны только описания охвата: исходного Lean-кода, Comparator и запуска нет. Нельзя считать проверенными конкретную политику, сложность или B по одному этому описанию.
Читать локальное описание формального охвата
Наличие PDF, извлечение текста, успешный маленький эксперимент и внешний результат-предшественник — разные виды свидетельств. Ни один из них здесь не отмечен как независимое подтверждение всей новой теоремы.
Практика: наш вывод, не обещание автора
Ближайший проект — стенд воспроизведения потоков и сравнения полной стоимости, включая запуск. Он реализуем известными методами и не требует принять новое доказательство. Перенос самой политики — отдельная исследовательская задача.
Ограничения переноса
Неизвестные большие степени и константы; огромная аддитивная цена B у вычислимой версии; затраты на хранение метрики; реальные задержки и пропускная способность не равны расстоянию. Полиномиальная обработка запроса не обещает полезной конкурентности на коротком горизонте.
Планы проверки: Стенд конечного горизонта для k-server и кэширования.
Исходники и реальный охват чтения
Номера страниц относятся к физическим страницам PDF, начиная с 1. Ссылки на GitHub не закреплены на текущем commit; воспроизводимый источник — локальный путь и SHA-256.
110-01 · Squared-logarithmic randomized k-server on arbitrary metrics
Реальный охват: Просмотрены PDF с. 1–3: Введение, теорема 1.1 и архитектура; доказательство целиком не прочитано. Полный объём PDF: 71 с.
math_sources/math_research_07_of_08/preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdfSHA-256: db9f0de04f757cf331b18404e7816d1fdbcf4842d79266cfd40f51d69926969eКаталог: context/CONTENTS.md, строка 2718. Путь и хеш относятся к загруженной версии.
110-02 · Uniform computation of the squared-logarithmic k-server bound
Реальный охват: Просмотрены PDF с. 1–2: Теорема и оговорка о начальном периоде. Полный объём PDF: 16 с.
math_sources/math_research_07_of_08/preprints/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026.pdfSHA-256: 2e665c0419f62ed427a64157dc31b6e3abf76b40810f0596d12ae5ef4ede8554Каталог: context/CONTENTS.md, строка 2727. Путь и хеш относятся к загруженной версии.
Семейство в CONTENTS.md, строка 2711. Структурированные заметки · Журнал внешней сверки.