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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Все лояльные генералы получают один вектор $(1,2,f(x,y,z),4)$, где $f(x,y,z)$ есть число, которое встречается как минимум два раза среди значений $(x,y,z)$, или «неизвестность», если все три числа $(x,y,z)$ различны. Поскольку значения $x,y,z$ и функция $f$ у всех лояльных генералов одни и те же, то согласие достигнуто.

Общий случай

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

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

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

Применение

• Биткойн и другие криптовалюты.
• Синхронизация часов

См. также

• Надёжность
• Network Time Protocol (NTP)
• Задача двух генералов
• Алгоритм Паксос
• Алгоритм Raft

Ссылки

• Крюков В. А. Курс лекций «Распределенные ОС»
• The Byzantine Generals Problem (with Marshall Pease and Robert Shostak) ACM Transactions on Programming Languages and Systems 4, 3 (July 1982), 382—401." (англ.)
• Доказательство невозможности решения задачи о византийских генералах в случае N<3m+1 (рус.)