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

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

Определение.

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).

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

Вопрос 16.