Нижняя граница для динамической связности: различия между версиями

Как ни удивительно, но Петрашку и Тарнице [7] удалось воспроизвести оптимальный компромисс теоремы 1 с минимальными изменениями рассуждений об эпохах. В старой версии этих рассуждений информация, раскрываемая эпохами <math>1, ..., i - 1</math> об эпохе <math>i</math>, ограничивалась количеством ячеек, записанных в эти эпохи. Ключевая идея заключается в том, что не менее удачным ограничением является количество ячеек, прочитанных в эпохи <math>1, ..., i - 1</math> и записанных в эпоху <math>i</math>.

В принципе, все операции чтения ячеек из эпохи <math>i - 1</math> могут читать данные из эпохи <math>i</math>, что делает эти две границы идентичными. Однако можно рандомизировать построение эпох, вставляя запрос после непредсказуемого количества обновлений. Такая рандомизация «сглаживает» распределение эпох, из которых считываются ячейки, то есть запрос считывает <math>O(t_q^{\Sigma}/log_r \; n)</math> ячеек из каждой эпохи, что выходит за рамки случайности в построении эпохи. Тогда <math>O(r^{i - 1})</math>обновлений в эпохи <math>1, ..., i - 1</math> читают только <math>O(r^{i-1} \cdot t_u^{\Sigma}/log_r \; n)</math> ячеек из эпохи <math>i</math>. Этой информации недостаточно, если <math>r \gg t_u^{\Sigma}/log_r \; n = \Theta(t_u^{\Sigma}/t_q^{\Sigma})</math>, из чего следует, что <math>t_q^{\Sigma} = \Omega(log_r \; n) = Omega(lg \; n/lg(t_u^{\Sigma}/t_q^{\Sigma}))</math>.

Нижние границы, описанные выше, основаны на том, что запрос '''sum''' должен выводить Q (<5) бит информации о каждом запросе. Если мы имеем дело с ''запросом о принятии решения'' для '''testsum''', то аргумент, основанный на энтропии вывода, уже не работает.

Наиболее удачной идеей для запросов на принятие решений было преобразование их в запросы с небулевым результатом в расширенной модели клеточного зонда, допускающей недетерминизм. В этой модели алгоритм запроса может порождать произвольное количество вычислительных потоков. Каждый поток может сделать <math>t_q</math> клеточных зондирований, после чего он должен либо завершиться ответом «отказ», либо вернуть ответ на запрос. Все потоки, не завершающиеся отказом, должны возвращать один и тот же результат. В этой модели запрос с произвольным результатом эквивалентен запросу на принятие решения, поскольку можно просто недетерминистским образом угадать ответ, а затем проверить его.

Исходя из вышесказанного, задача состоит в том, чтобы доказать хорошие нижние границы для суммы даже в недетерминистской модели. Недетерминизм поколебал представление о том, что при анализе эпохи i имеют значение только запросы к ячейкам эпохи <math>i</math>. Проблема в том, что запрос может не знать, ''какие'' из его зондирований действительно относятся к эпохе <math>i</math>. Зонд, считывающий ячейку из предыдущей эпохи, предоставляет по крайней мере некоторую информацию об эпохе <math>i</math>: ни одно обновление в эту эпоху не решило перезаписать клетку. Ранее это не было проблемой, поскольку целью было только исключить случай, когда в эпоху <math>i</math> существует ''ноль'' зондирований. Теперь, однако, различные потоки могут зондировать любую ячейку в памяти, и невозможно определить, какие потоки на самом деле избегают зондирования чего-либо в эпоху <math>i</math>. Другими словами, между эпохой <math>i</math> и запросом существует скрытый канал связи, в котором эпоха может использовать выбор того, какие ячейки записывать, чтобы передать информацию запросу.