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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Формулировка[править | править вики-текст]

Византия. В ночь перед великим сражением, Византийская армия содержит n легионов. Каждый из них подчиняется своему генералу. У всей византийской армии есть главнокомандующий, руководящий генералами. Империя находится в упадке и среди генералов, включая главнокомандующего, могут быть предатели. В течение всей ночи, каждый из генералов получает от предводителя приказ о действии на утро. Это может быть один из двух вариантов «атаковать» или «отступать». Если все честные генералы атакуют — они одержат победу. Если все отступят — им удастся сохранить армию. Если часть атакуют, а часть отступят — они терпят поражение. Если главнокомандующий предатель, он может дать разным генералам разные приказы, следовательно, его приказы не стоит выполнять беспрекословно. Если же каждый генерал будет действовать независимо от других, результаты битвы также могут быть плачевными. Поэтому генералы нуждаются в обмене информацией друг с другом, чтобы прийти к соглашению.

Определение[править | править вики-текст]

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

Применение[править | править вики-текст]

См. также[править | править вики-текст]

Ссылки[править | править вики-текст]