Коммуникационная сложность

Apache Spark JOIN двух таблиц по 1 TB каждая: сколько данных нужно перемещать по сети? Теория коммуникационной сложности даёт точную нижнюю оценку - и объясняет почему Spark использует именно такие алгоритмы join. Kafka использует Count-Min Sketch для lag estimation с O(log n) памятью.

• Count-Min Sketch: Apache Kafka consumer lag, Redis CMS модуль, Flink частоты событий
• HyperLogLog: Redis PFCOUNT, Google BigQuery approx_count_distinct - lower bound из Equality
• Join ordering в PostgreSQL: коммуникационная сложность ограничивает shuffle join cost
• GPU memory bandwidth: Roofline модель основана на идеях Thompson VLSI lower bounds

Модель коммуникационной сложности

Модель Яо (1979): два игрока Alice и Bob получают входы x и y. Цель - вычислить f(x, y) с минимальным числом переданных бит. Локальные вычисления бесплатны, только коммуникация стоит.

Коммуникационная матрица: строки = значения x, столбцы = значения y, ячейки = f(x,y). Детерминированная сложность = log2(число монохроматических прямоугольников необходимых для покрытия матрицы). Rank lower bound: сложность >= log2(rank(M)) над полем GF(2).

Протоколы и нижние оценки

Дерево протокола: бинарное дерево решений где каждый внутренний узел - сообщение Alice или Bob, листья - результат. Детерминированная сложность = глубина оптимального дерева.

• Rank method: D(f) >= log2(rank(M_f)) - самый простой нижний bound
• Fooling set: набор пар (x_i, y_i) с f=1 где любые два из одной строки/столбца дают f=0
• Discrepancy method: для рандомизированных протоколов, использует взвешенную дисперсию
• Disjointness Theta(n) рандомизированно - используется для нижних оценок Join в базах данных

Нижние оценки и VLSI

Коммуникационная сложность дает нижние оценки для схем, VLSI и параллельных алгоритмов. Если схема разрезается на две части, число проводов между частями >= коммуникационная сложность вычисляемой функции.

Streaming алгоритмы и скетчи

Streaming алгоритм обрабатывает поток данных за один проход с памятью o(n). Коммуникационная сложность даёт нижние оценки: если Alice видит первую половину потока, Bob - вторую, то memory >= коммуникационная сложность задачи.

Итоги

• Equality: детерминированно Theta(n), рандомизированно O(log n) - рандомизация помогает
• Inner Product и Disjointness: рандомизированно Theta(n) - рандомизация не помогает
• VLSI lower bound: площадь схемы для умножения матриц Omega(n^4)
• Streaming lower bounds: Disjointness Omega(n) -> точный set intersection требует Omega(n) памяти

Связанные темы

Коммуникационная сложность связывает теорию с архитектурой систем и алгоритмами:

• Рандомизированные алгоритмы — Randomized protocols для Equality: O(log n) бит против Theta(n) детерминированно
• Теория сложности схем — VLSI lower bounds: коммуникация через разрез схемы ограничивает площадь
• Дескриптивная сложность — Коммуникационная сложность связана с выразимостью в логике через Ehrenfeucht-Fraisse
• Алгоритмы баз данных — Нижние оценки join и aggregation в distributed SQL основаны на Disjointness

Вопросы для размышления

• Почему рандомизация экспоненциально снижает коммуникацию для Equality, но не для Inner Product?
• Как нижняя оценка для Disjointness доказывает, что точный HLL невозможен за o(n) памяти?
• Каким образом Roofline модель для GPU связана с коммуникационной сложностью?

Связанные уроки

• ml-02