МЕНЮ

Определения

ПРОТОКОЛЫ СОГЛАШЕНИЯ Протоколы AP
Прикладные протоколы
Термин

Протокол соглашения (agreement protocol) - криптографический протокол для решения задачи соглашения (agreement problem), заключающейся в следующем:

Дано конечное множество $ P={p_1, p_2, ..., p_n}$ взаимодействующих процессоров (сайтов, удаленных абонентов), которые пытаются достичь соглашения. Часть процессоров $ F$ являются неисправными. Каждый процессор $ p_i in P$ хранит значение $ v_i$. Во время выполнения протокола соглашения процессоры вычисляют значение соглашения $ a_i$. После окончания работы протокола должны выполняться следующие два условия:

1) для каждой пары исправных процессоров $ p_i$ и $ p_j$ $ a_i = a_j$, это значение является значением соглашения,

2) значение соглашения является функцией от начальных значений $ {v_i}$ исправных процессоров $ P-F$.

Процессоры могут напрямую взаимодействовать с другими процессорами путем передачи сообщений. Процессор, принимающий сообщение, всегда знает идентичность процессора, отправившего сообщение. Коммуникационная среда является надежной, т.е. все сообщения доставляются без ошибок. Только процессоры подвержены неисправностям. Вычисления могут быть синхронными или асинхронными. При синхронных вычислениях процессор получает сообщения (1 раунд), выполняет вычисления (2 раунд), и отправляет сообщения другим процессорам (3 раунд). При асинхронных вычислениях процессор может отправлять и получать сообщения и выполнять вычисления в любое время.

Процессор может иметь неисправности трех видов.

1) Аварийная ошибка: процессор перестает функционировать и так и не возобновляет работу.

2) Ошибка бездействия: процессор "забывает" отправлять сообщения другим процессорам.

3) Необъяснимая ошибка (злонамеренная ошибка, византийская ошибка): процессор ведет себя случайно и произвольно.

Передаваемые между процессорами сообщения могут быть заверенными (подписанные сообщения) и незаверенными (устные сообщения). В первом случае неисправный процессор не может подделать сообщение или изменить содержание полученного сообщения. Процессор может проверить подлинность полученного сообщения. Во втором случае неисправный процессор может подделать сообщение и утверждать, что получил его от другого процессора или изменить содержание полученного сообщения, прежде чем ретранслировать сообщение для других процессоров. Процессор не имеет возможности проверить подлинность полученного сообщения.

Рабочие характеристики протоколов соглашения.

Время: количество раундов.

Трафик сообщений: количество сообщений, которыми обмениваются для достижения соглашения.

Издержки памяти: количество информации, которая должна храниться в процессорах в ходе выполнения протокола.

Известны следующие задачи соглашения:

1) Задача византийского соглашения (Byzantine agreement problem).

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

2) Задача консенсуса (consensus problem).

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

3) Задача интерактивной согласованности (interactive consistency problem).

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

Задача византийского соглашения известна еще под названием задачи византийских генералов (Byzantine Generals Problem). Эта задача формулируется традиционно на историческом примере армии Византийской империи периода упадка. Имеются $ n+1$ участник — главнокомандующий и $ n$ генералов. Главнокомандующий посылает каждому генералу приказ, который имеет всего два возможных варианта: атаковать или отступать. Часть генералов, в т. ч. и главнокомандующий, могут оказаться предателями. Честные генералы, обмениваясь сообщениями по каналам связи (которые обычно предполагаются защищенными) должны достигнуть соглашения о единых действиях — атаковать или отступать. Нетривиальной задачу делает следующее требование: если главнокомандующий честный, то все честные генералы обязаны выполнить его приказ.

Соответственно различают следующие виды протоколов.

Протокол византийского соглашения (Byzantine agreement protocol) - криптографический протокол соглашения для решения задачи византийских генералов.

Протокол консенсуса (consensus protocol) - криптографический протокол соглашения для решения задачи консенсуса.

Протокол интерактивной согласованности (interactive consistency protocol) - криптографический протокол соглашения для решения задачи интерактивной согласованности.

 
Ссылки
  • Lamport L., Shostak R., Pease M. The Byzantine generals problem. ACM Transactionson ProgrammingLanguagesand Systems,Vol.4, No. 3, July 1982,Pages 382-401.