СМЕШИВАТЬ СООБЩЕНИЯ ВЫГОДНЕЕ, ЧЕМ МАРШРУТИЗИРОВАТЬ, — ПОСЛЕ 22 ЛЕТ СОМНЕНИЙ

Представьте сеть кабелей, в которой несколько отправителей хотят связаться каждый со своим получателем. Классический подход — маршрутизация: каждое сообщение путешествует как посылка по одному или нескольким путям, и трафик можно даже делить между многими путями в любой пропорции. Сетевое кодирование (network coding) добавляет ещё одну степень свободы: промежуточные узлы могут комбинировать полученные сообщения — например, складывать их, — а не просто пересылать дальше.

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

Гипотеза, подтверждённая случай за случаем

В 2004 году Ли и Ли (Li and Li) выдвинули гипотезу, что в такой постановке кодирование не даёт никакого преимущества перед дробной маршрутизацией; Харви, Клейнберг и Расала Леман (Harvey, Kleinberg and Rasala Lehman) независимо сформулировали ту же гипотезу. За следующие два десятилетия её подтвердили для одного класса сетей за другим — две сессии, некоторые планарные сети, сети не более чем с шестью кодирующими узлами и другие, — но в общем виде вопрос так и не был решён. Другие результаты теории сложности, например нижние оценки для сортировки целых чисел во внешней памяти и для схем умножения, даже были доказаны в предположении, что она верна.

Известная теория уже ограничивала ставки: кодирование может превзойти маршрутизацию не более чем в логарифмическое число раз. А результат Бравермана, Гарга и Шварцмана (Braverman, Garg and Schvartzman) 2017 года показал, что одну-единственную сеть со строгим преимуществом кодирования можно усилить до гораздо большего разрыва. Всё сводилось к тому, чтобы найти один конечный пример.

Достаточно сложения

В приложении приведён базовый элемент, показывающий, почему смешивание может помочь. Разместите несколько источников вокруг узла-концентратора v, их получателей — вокруг другого концентратора w, и соедините v и w одним кабелем. У каждого источника есть также небольшие боковые пути к другим получателям. За три раунда средний кабель передаёт сумму всех сообщений; каждый получатель получает эту сумму плюс остальные сообщения по боковым путям и восстанавливает своё вычитанием. Без среднего кабеля каждый источник находится в пяти переходах от своего получателя.

Этот элемент из более ранней работы Хойплера, Вайца и Зузича (Haeupler, Wajc and Zuzic) делает кодирование быстрее, но сам по себе не позволяет передать больше: по длинному пути всё равно можно гнать высокоскоростной конвейер.

Схема, превращённая в сеть

Синьдань Чжан (Xindan Zhang) и Баочунь Ли (Baochun Li) из Университета Торонто и Цзунпэн Ли (Zongpeng Li) из Университета Цинхуа нашли недостающий шаг. Они превращают короткий код в обратимое вычисление — схему из обратимых целочисленных сложений, которая вычисляет, копирует результат, а затем отменяет промежуточную работу. Затем они строят новую сеть, физические кабели которой и есть провода этой схемы, и дают каждому регистру вычисления, включая вспомогательные, собственный запрос «отправитель — получатель».

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

Что доказано

• Конечная связная сеть, в которой каждый узел соединён не более чем с тремя другими, а пропускная способность каждого кабеля равна единице, и на которой простой двоичный линейный код превосходит наилучшую возможную дробную маршрутизацию. Гипотеза 2004 года неверна.
• Та же целочисленная конструкция работает сразу над любым конечным полем и любой нетривиальной конечной абелевой группой.
• Многократно комбинируя копии, авторы строят бесконечные семейства сетей, где кодирование приближается к полной скорости, а маршрутизация падает как степень 1/log n, — полилогарифмическое преимущество.

Число узлов в контрпримере в статье не указано. Один только его строительный блок — это код длиной 13 122 раунда.

Проверено машиной

И конечный контрпример, и теорема о семействах формализованы в системе доказательства Lean. По словам авторов, аудит 2472 объявлений и 1755 теорем показывает, что доказательства используют только три стандартные аксиомы Lean и не содержат незавершённых доказательств; независимая повторная проверка в чистом окружении также прошла успешно, хотя и с тем же ядром Lean.

Что остаётся открытым

Авторы перечисляют три вопроса: истинная величина преимущества на их конечном примере, достигается ли на самом деле известный логарифмический потолок и существует ли небольшой контрпример. Последняя фраза статьи подводит итог: «Кодирование, как выясняется, всё-таки помогает в неориентированных сетях; насколько сильно — ещё предстоит узнать».

Использование ИИ заявлено. В сноске указано, что GPT-6 Astra от OpenAI помогал в разработке доказательств и кода на Lean.