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

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

Определение

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-й шаг. Каждый формирует свой вектор из имеющейся информации.

Получается:

vect1 (1,2,x,4)

vect2 (1,2,y,4)

vect3 (1,2,3,4)

vect4 (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 (рус.)