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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Формулировка[править | править вики-текст]

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

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

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

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

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

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

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

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

Определение[править | править вики-текст]

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

Формализация[править | править вики-текст]

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

Алгоритмы решения[править | править вики-текст]

Частный случай[править | править вики-текст]

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

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

1-й шаг. Каждый генерал посылает всем остальным сообщение, в котором указывает численность своей армии. Лояльные генералы указывают истинное количество, а предатели могут указывать различные числа в разных сообщениях. Генерал 1 указал число 1 (одна тысяча воинов), генерал 2 указал число 2, генерал 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-й шаг. Каждый генерал определяет для себя размер каждой армии. Чтобы определить размер -й армии, каждый генерал берёт три числа — размеры этой армии, пришедшие от всех командиров, кроме командира -й армии. Если какое-то значение повторяется среди этих трех чисел как минимум дважды, то оно помещается в результирующий вектор, иначе соответствующий элемент результирующего вектора помечается неизвестным (или нулём и т. п.).

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

Общий случай[править | править вики-текст]

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

Результаты исследования задачи[править | править вики-текст]

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

Применение[править | править вики-текст]

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

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

Ссылки[править | править вики-текст]