WikiSort.ru - Не сортированное

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

Рекурсивный алгоритм решения для частного случая, когда количество генералов ограничено и не может динамически изменяться, был предложен в 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}$ , а генерал 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 i}$ -й армии. Если какое-то значение повторяется среди этих трех чисел как минимум дважды, то оно помещается в результирующий вектор, иначе соответствующий элемент результирующего вектора помечается неизвестным (или нулём и т. п.).

Все лояльные генералы получают один вектор ${\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}$ у всех лояльных генералов одни и те же, то согласие достигнуто.

Общий случай

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