Правильно сконструированная компьютерная система должна сохранять работоспособность при отказе одной или нескольких ее компонент. Вышедшая из строя компонента может демонстрировать поведение, которое часто бывает трудно предусмотреть, а именно: отсылка противоречивой информации различным частям системы. Проблема отработки подобной ситуации может быть представлена в виде абстрактной Проблемы византийских генералов.

Предположим, что несколько — скажем, $ n \in \mathbb N $ — подразделений византийской армии располагаются в окрестности осаждаемого ими города и разнесены территориально. При этом каждое подразделение возглавляется своим генералом. Генералы могут обмениваться друг с другом сообщениями. После рекогнисцировки они должны принять согласованный план действий. Среди генералов могут оказаться предатели ¹⁾, которые будут препятствовать оставшимся верными генералам в принятии плана. Ни точное количество, ни поименный состав этой группы «изменников Родины» заранее не известен. Генеральское собрание должно иметь алгоритм действий, гарантирующий

A. Все лояльные генералы принимают одинаковый план действий

Лояльные генералы поступают так, как им предпишет алгоритм, а предатели могут при этом поступать как им заблагорассудится.

B. Небольшое количество предателей не сможет заставить лояльных генералов принять плохой план.

Как генералы принимают решение? Каждый из них оценивает противника и делится своим заключением с остальными. Пусть $ v_i $ — информация, передаваемая остальным $ i $-м генералом. Каждый генерал использует некоторый метод, позволяющий вывести из информационных сообщений $ v_1,\dots, v_n $ план его действий. Пусть, к примеру, возможные варианты этих действий ограничены двумя: атаковать или отступать. Тогда $ v_i $ может быть выбором $ i $-го генерала из этих двух возможностей, а совместный план действий получается подсчетом большинства голосов. Небольшое количество предателей может повлиять на окончательный план только при условии, что мнения лояльных генералов разделились примерно поровну.

Предложенный алгоритм принятия решения предполагает, что каждый генерал способен донести свое решение $ v_i $ до остальных и каждый из лояльных генералов принимает решение на основе одинакового набора $ v_1.\dots, v_n $. В то же время, предатель может посылать разную информацию разным генералам. Следовательно, для соблюдения условия A необходимо. чтобы

1. Каждый лояльный генерал должен получить одинаковую информацию $ v_1,\dots, v_n $.

2. Если $ i $-й генерал лоялен, то решение которое он всем отсылает, каждым лояльным генералом должно приниматься за $ v_i $

Фактически, проблема сводится к тому, как $ i $-й генерал доводит свое решение до остальных. С учетом этого обстоятельства, можно перефразировать проблему в виде

Проблемы византийских генералов. Главнокомандующий рассылает подчиненным $(n-1)$-му генералу приказания с теми условиями, что

IC1. Все лояльные генералы выполняют один и тот же приказ.

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

Условия IC1 и IC2 назовем условиями согласованности взаимодействия²⁾. В частности, если главнокомандующий лоялен, то IC1 следует из IC2. Для решения исходной задачи, $ i $й генерал посылает свое значение $ v_i $ как если бы оно было решением проблемы византийских генералов: «использовать $ v_i $ в качестве моего значения»; при этом все остальные генералы считаются его подчиненными.

Решение ПВГ зависит от того какой тип имеют сообщения — устные или подписанные. Устными считаются такие сообщения, содержимое которых находится под абсолютным контролем отправителя.

Теорема. В случае только устных сообщений и наличия $ m $ предателей, ПВГ не имеет решения если число лояльных генералов $ \le 2m $.

Доказательство может быть сведено к случаю $ n=3 $ генералов, из которых $ 1 $ — предатель.

В случае наличия $ \ge 2m+1 $ лояльных генералов, ПВГ может быть решена. Сделаем следующие предположения относительно устных сообщений:

A1. Каждое посланное сообщение доставляется неповрежденным.

A2. Получателю сообщения известен его отправитель.

A3. Отсутствие сообщения может быть установлено.

В настоящем параграфе предположим, что каждый генерал имеет возможность прямой коммуникации с любым другим генералом. Отсутствие сообщения от какого-то генерала будет, по договоренности, считаться его решением «ОТСТУПАТЬ».

Алгоритм $ OM(m) $ определяется индуктивно по $ m \in \mathbb N $, он определяет правило, по которому каждый генерал рассылает свое решение другим генералам. Алгоритм основан на функции $ \operatorname{majority} $, которая определяется как $$ \operatorname{majority}(v_1,\dots,v_{n-1}) = v \mbox{ если большинство из чисел } \{v_1,\dots,v_{n-1}\} \mbox{ равно } v \, .$$

Алгоритм OM

Алгоритм $ OM(0) $.

(1) Генерал посылает свое решение другим генералам

(2) Каждый генерал использует решение, переданное ему другим генералом или же принимает решение «ОТСТУПАТЬ» если не получает сообщений.

Алгоритм $ OM(m), m>0 $.

(1) Генерал посылает свое решение другим генералам.

(2) Каждый $ i $-й генерал, получивший от другого генерала решение $ v_i $ (или не получивший от него решение, в этом случае считает его «ОТСТУПАТЬ»), высылает всем оставшимся $ n-2 $ генералам это решение принятое по алгоритму $ OM(m-1) $.

(3) Для каждого $ i $ и для каждого $ j \ne i $, пусть $ v_j $ — решение, которое генерал $ i $ получает от генерала $ j $ на этапе (2) (используя алгоритм $ OM(m-1) $) или считая этим решением «ОТСТУПАТЬ» в случае, если решение не получено. Генерал $ i $ принимает решение $ \operatorname{majority}(v_1,\dots,v_{n-1}) $.

Пример. $ n=4, m=1 $ : лояльные генералы 1,2,3 и предатель — генерал 4. Рассмотрим, что происходит с сообщением, идущим от лояльного генерала (стадия (1) алгоритма). Будучи честным служакой, он отправляет одно и то же сообщение $ v_1 $ оставшимся генералам.

В стадии (2) каждый из генералов 2, 3, 4 должен переслать $ v_1 $ всем остальным генералам, следуя алгоритму $ OM(0) $. Именно это делают генералы 2 и 3, а вот предатель может переслать вместо $ v_1 $ совершенно произвольные значения. На рисунке показано, какие сообщения приходят генералу 3.

В стадии (3) генерал 3 применяет функцию $ \operatorname{majority} $ к набору $ v_1,v_1,x $: $$ \operatorname{majority} (v_1,v_1,x) = v_1 \, . $$ Именно его он принимает за истинное мнение генерала 1. Аналогичное решение принимает и другой лояльный генерал — генерал 2.

Теперь посмотрим, что происходит с рассылкой сообщений предателем — генералом 4. Он посылает всем остальным генералам сообщения $ x, y, z$, которые могут быть произвольными (противоречивыми).

В стадии (2) каждый из генералов 2, 3, 4 долежн переслать полученные им сообщения оставшимся генералам, и он делает это честно (все эти генералы лояльные), не искажая полученного. В стадии (3) каждый из генералов применяет функцию $ \operatorname{majority} $ к набору $ x,y,z $. Вывод, полученный ими, будет одинаков, а именно $ \operatorname{majority} (x,y,z) $ вне зависимости от комбинации значений $x,y,z $. ♦

Рекурсивный алгоритм $ OM(m) $ вызывает $ n-1 $ отдельное выполнение алгоритма $ OM(m-1) $, каждый из которых вызывает выполнение $ n-2 $ отдельное выполнение алгоритма $ OM(m-2) $ и т.д. Это значит, что при $ m>1 $ каждый генерал посылает множество сообщений другим генералам.

[1]. Lamport L., Shostak R., Pease M. The Byzantian Generals Problem. ACM Trans. Programming Languages and Systems. 1982, V.4, N 3, pp.382–401