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

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

Определение

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

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

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

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

Соответствующий рекурсивный алгоритм был предложен в 1982 г. Лесли Лампортом.

Проиллюстрируем его для случая 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,y,4)	(1,2,x,4)	(1,2,x,4)	(1,2,x,4)
(a,b,c,d)	(e,f,g,h)	(1,2,y,4)	(1,2,y,4)
(1,2,z,4)	(1,2,z,4)	(1,2,z,4)	(i,j,k,l)

4-ый шаг. Каждый генерал проверяет каждый элемент во всех полученных векторах. Если какое-то значение совпадает по меньшей мере в двух векторах, то оно помещается в результирующий вектор, иначе соответствующий элемент результирующего вектора помечается неизвестен.

Все лояльные генералы получают один вектор (1,2,неизвестен,4) — согласие достигнуто.

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

Лампорт доказал, что в системе с 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."(англ.)