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

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

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

1-й шаг. Каждый генерал посылает всем остальным сообщение, в котором указывает численность своей армии. Лояльные генералы указывают истинное количество, а предатели могут указывать различные числа в разных сообщениях. Генерал 1 указал число 1 (одна тысяча воинов), генерал 2 указал число 2, генерал 3 (предатель) указал трём остальным генералам соответственно ${\displaystyle x}$, ${\displaystyle y}$, ${\displaystyle 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 посылает опять произвольные значения).

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

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

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

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