Рандомизированный протокол связи. Часть 1

Flashback    Статьи и обзоры    

Пусть есть два компьютера, C_I и C_II, находящиеся очень далеко друг от друга – например, один в Европе, а другой в Америке. Сначала оба компьютера содержали одну и ту же базу данных; потом на каждом из них проводилась независимая работа с целью получения полной информации о предмете базы данных – например, о последовательности аминокислот некоторого генома. По прошествии некоторого времени мы захотели определить, успешно ли закончился этот процесс – т. е. действительно ли C_II и C_II содержат одни и те же данные.

Пусть n – размер базы данных в битах. Например, п может иметь порядок 10¹⁶ – это является реальным значением для биологических приложений. Наша цель состоит в том, чтобы разработать коммуникационный протокол между C_II и C_II, который дал бы возможность определить, действительно ли совпадают данные на этих компьютерах. Сложность коммуникационного протокола – это число битов, которые нужно переслать между C_II и C_II с целью получения ответа на данный вопрос. Очевидно, что мы стараемся минимизировать эту сложность.

Можно доказать, что любой детерминированный коммуникационный протокол для решения этой задачи должен переслать между C_II и C_II не менее п битов (Это означает, что оптимальная коммуникационная стратегия – это пересылка всех данных от C_II к C_II для их последующего сравнения.) – т. е. не существует детерминированных протоколов, которые решали бы эту проблему путём пересылки n — 1 или меньшего числа битов. Надо переслать 10¹⁶ битов, дополнительно убедиться, что все они успешно дошли… (Без ошибок в пересылке хотя бы одного из них – это тоже является нетривиальной задачей). Итак, вряд ли стоит идти по этому пути.

Продолжение в Рандомизированный протокол связи. Часть 2.