Сен
26

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

Автор Flashback    Рубрики Статьи и обзоры     Теги

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

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

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

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

Написать комментарий

XHTML: Вы можете использовать эти теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>