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

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

Определение

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

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

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

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

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

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

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

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

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

Все лояльные генералы получают один вектор $(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)
• Задача двух генералов

Ссылки

• Крюков В. А. Курс лекций «Распределенные ОС»
• 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 (рус.)