Задача византийских генералов

Задача византийских генералов — в криптологии задача взаимодействия нескольких удалённых абонентов, которые получили приказы из одного центра. Часть абонентов, включая центр, могут быть злоумышленниками (или злоумышленники подменили сообщения при передаче). Нужно выработать единую стратегию действий, которая будет выигрышной для абонентов.

Исходная формулировка

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

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

Ночью каждый из генералов получает от главнокомандующего приказ как надлежит поступить в 10 часов утра (время одинаковое для всех и известно заранее). Варианты приказа: «атаковать противника» или «отступать».

Возможные исходы сражения:

  1. Если все верные генералы атакуют — Византия уничтожит противника (благоприятный исход).
  2. Если все верные генералы отступят — Византия сохранит свою армию (промежуточный исход).
  3. Если некоторые верные генералы атакуют, а некоторые отступят — противник со временем по частям уничтожит всю армию Византии (неблагоприятный исход).

Также следует учитывать, что если главнокомандующий — предатель, то он может дать разным генералам противоположные приказы, чтобы обеспечить уничтожение армии. Следовательно, генералам надо учитывать такую возможность и не допускать несогласованных действий.

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

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

Уточнённое определение

Пусть «белых» генералов возглавляют армии в горах и готовятся атаковать «чёрных» в долине. Для связи атакующие используют надёжный канал (например, телефон), исключающий подмену сказанного. Однако из генералов являются предателями и активно пытаются воспрепятствовать согласию лояльных генералов. Согласие состоит в том, чтобы все лояльные генералы узнали о численности всех лояльных армий и пришли к одинаковым выводам (пусть и ложным) относительно состояния предательских армий. (Последнее условие важно, если генералы на основании полученных данных планируют выработать стратегию, и необходимо, чтобы все генералы выработали одинаковую стратегию.)

Формализация

По результатам обмена каждый из лояльных генералов должен получить вектор целых чисел длины n, в котором i-й элемент либо равен истинной численности i-й армии (если её генерал лоялен), либо содержит дезинформацию о численности i-й армии (если её генерал не лоялен). При этом векторы, полученные всеми лояльными командирами, должны быть полностью одинаковы.

Алгоритмы решения

Частный случай

Рекурсивный алгоритм решения для частного случая, когда количество генералов ограничено и не может динамически изменяться, был предложен в 1982 г. Лесли Лампортом. Алгоритм сводит задачу для случая предателей среди генералов к случаю предателя.

Для случая алгоритм тривиален, поэтому проиллюстрируем его для случая и . В этом случае алгоритм осуществляется в 4 шага.

1-й шаг. Каждый генерал посылает всем остальным сообщение, в котором указывает численность своей армии. Лояльные генералы указывают истинное количество, а предатели могут указывать различные числа в разных сообщениях. Генерал 1 указал число 1 (одна тысяча воинов), генерал 2 указал число 2, генерал 3 (предатель) указал трём остальным генералам соответственно , , (истинное значение – 3), а генерал 4 указал 4.

2-й шаг. Каждый формирует свой вектор из имеющейся информации:

  • Вектор генерала №1: (1,2,x,4);
  • Вектор генерала №2: (1,2,y,4);
  • Вектор генерала №3: (1,2,3,4);
  • Вектор генерала №4: (1,2,z,4).

3-й шаг. Каждый посылает свой вектор всем остальным (генерал 3 посылает опять произвольные значения).

После этого у каждого генерала есть по четыре вектора:

g1 g2 g3 g4
(1,2,x,4) (1,2,x,4) (1,2,x,4) (1,2,x,4)
(1,2,y,4) (1,2,y,4) (1,2,y,4) (1,2,y,4)
(a,b,c,d) (e,f,g,h) (1,2,3,4) (i,j,k,l)
(1,2,z,4) (1,2,z,4) (1,2,z,4) (1,2,z,4)

4-й шаг. Каждый генерал определяет для себя размер каждой армии. Чтобы определить размер -й армии, каждый генерал берёт чисел — размеры этой армии, пришедшие от всех командиров, кроме командира -й армии. Если какое-то значение повторяется среди этих чисел как минимум раз, то оно помещается в результирующий вектор, иначе соответствующий элемент результирующего вектора помечается неизвестным (или нулём и т. п.).

Все лояльные генералы получают один вектор , где есть число, которое встречается как минимум два раза среди значений , или «неизвестность», если все три числа различны. Поскольку значения и функция у всех лояльных генералов одни и те же, то согласие достигнуто.

Общий случай

Построение цепочек связанных последовательных блоков, объединённое с доказательством выполнения работы – впервые использованное в криптовалюте «Биткойн» – позволило с приемлемым уровнем риска получить механизм динамического принятия решений в более общем случае данной задачи, когда количество генералов (узлов сети) точно не известно и может динамически произвольно изменяться.

Результаты исследования задачи

Лампорт доказал, что в системе с неверно работающими процессорами («нелояльными генералами») можно достичь согласия только при наличии верно работающих процессоров («лояльных генералов»), то есть когда «правильных» строго больше от общего числа.

Применение

См. также

Примечания

  1. Марк Андрессен. Why Bitcoin Matters (англ.). The New York Times (21 января 2014). Дата обращения: 2 октября 2015. (Марк Андрессен. Почему Биткоин так важен?. Habrahabr.ru. Дата обращения: 2 октября 2015. — вариант перевода).

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.