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

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

Формулировка

Византия. Ночь перед великим сражением с противником. Византийская армия состоит из <math>n</math> легионов, каждым из которых командует свой генерал. Также, у армии есть главнокомандующий, которому подчиняются генералы.

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

Ночью каждый из генералов получает от предводителя приказ о варианте действий в 10 часов утра (время одинаковое для всех и известно заранее), а именно: «атаковать противника» или «отступать».

Возможные исходы сражения:

1. Если все генералы атакуют — Византия уничтожит противника (благоприятный исход).
2. Если все генералы отступят — Византия сохранит свою армию (промежуточный исход).
3. Если некоторые генералы атакуют, а некоторые отступят — противник уничтожит всю армию Византии (неблагоприятный исход).

Также следует учитывать, что если главнокомандующий — предатель, то он может дать разным генералам противоположные приказы, чтобы обеспечить уничтожение армии. Следовательно, генералам лучше не доверять его приказам.

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

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

Определение

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

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

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

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

Частный случай

Рекурсивный алгоритм решения для частного случая, когда количество генералов ограничено и не может динамически изменяться, был предложен в 1982 г. Лесли Лампортом. Алгоритм сводит задачу для случая <math>m</math> предателей среди <math>n</math> генералов к случаю <math>m-1</math> предателя.

Для случая <math>m=0</math> алгоритм тривиален, поэтому проиллюстрируем его для случая <math>n=4</math> и <math>m=1</math>. В этом случае алгоритм осуществляется в 4 шага.

1-й шаг. Каждый генерал посылает всем остальным сообщение, в котором указывает численность своей армии. Лояльные генералы указывают истинное количество, а предатели могут указывать различные числа в разных сообщениях. Генерал 1 указал число 1 (одна тысяча воинов), генерал 2 указал число 2, генерал 3 (предатель) указал трём остальным генералам соответственно <math>x</math>, <math>y</math>, <math>z</math>, а генерал 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-й шаг. Каждый генерал определяет для себя размер каждой армии. Чтобы определить размер <math>i</math>-й армии, каждый генерал берёт три числа — размеры этой армии, пришедшие от всех командиров, кроме командира <math>i</math>-й армии. Если какое-то значение повторяется среди этих трех чисел как минимум дважды, то оно помещается в результирующий вектор, иначе соответствующий элемент результирующего вектора помечается неизвестным (или нулём и т. п.).

Все лояльные генералы получают один вектор <math>(1,2,f(x,y,z),4)</math>, где <math>f(x,y,z)</math> есть число, которое встречается как минимум два раза среди значений <math>(x,y,z)</math>, или «неизвестность», если все три числа <math>(x,y,z)</math> различны. Поскольку значения <math>x, y, z</math> и функция <math>f</math> у всех лояльных генералов одни и те же, то согласие достигнуто.

Общий случай

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

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

Лампорт доказал, что в системе с <math>m</math> неверно работающими процессорами ("нелояльными генералами") можно достичь согласия только при наличии <math>2m+1</math> верно работающих процессоров ("лояльных генералов"), т.е. строго больше двух третей от общего числа процессоров.

Применение

• Синхронизация часов
• Биткойн — пиринговая платёжная система.

См. также

• Надёжность
• Network Time Protocol (NTP)
• Задача двух генералов

Ссылки

• [parallel.ru/krukov/lec7.html Крюков В. А. Курс лекций «Распределенные ОС»]
• [research.microsoft.com/users/lamport/pubs/pubs.html#byz The Byzantine Generals Problem (with Marshall Pease and Robert Shostak) ACM Transactions on Programming Languages and Systems 4, 3 (July 1982), 382—401."] (англ.)
• [blog.artlives.ru/programming/%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC-%D0%B2%D0%B8%D0%B7%D0%B0%D0%BD%D1%82%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D1%85-%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D0%BE%D0%B2/ Решение задачи о византийских генералах] (рус.)
• [blog.artlives.ru/programming/%D0%B2%D0%B8%D0%B7%D0%B0%D0%BD%D1%82%D0%B8%D0%B9%D1%81%D0%BA%D0%B8%D0%B5-%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D1%8B-%D0%B4%D0%BE%D0%BA%D0%B0%D0%B7%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D1%81%D1%82/ Доказательство невозможности решения задачи о византийских генералах в случае N<3m+1] (рус.)

Отрывок, характеризующий Задача византийских генералов

– А, знамена! – сказал Кутузов, видимо с трудом отрываясь от предмета, занимавшего его мысли. Он рассеянно оглянулся. Тысячи глаз со всех сторон, ожидая его сло ва, смотрели на него.
Перед Преображенским полком он остановился, тяжело вздохнул и закрыл глаза. Кто то из свиты махнул, чтобы державшие знамена солдаты подошли и поставили их древками знамен вокруг главнокомандующего. Кутузов помолчал несколько секунд и, видимо неохотно, подчиняясь необходимости своего положения, поднял голову и начал говорить. Толпы офицеров окружили его. Он внимательным взглядом обвел кружок офицеров, узнав некоторых из них.
– Благодарю всех! – сказал он, обращаясь к солдатам и опять к офицерам. В тишине, воцарившейся вокруг него, отчетливо слышны были его медленно выговариваемые слова. – Благодарю всех за трудную и верную службу. Победа совершенная, и Россия не забудет вас. Вам слава вовеки! – Он помолчал, оглядываясь.
– Нагни, нагни ему голову то, – сказал он солдату, державшему французского орла и нечаянно опустившему его перед знаменем преображенцев. – Пониже, пониже, так то вот. Ура! ребята, – быстрым движением подбородка обратись к солдатам, проговорил он.
– Ура ра ра! – заревели тысячи голосов. Пока кричали солдаты, Кутузов, согнувшись на седле, склонил голову, и глаз его засветился кротким, как будто насмешливым, блеском.
– Вот что, братцы, – сказал он, когда замолкли голоса…
И вдруг голос и выражение лица его изменились: перестал говорить главнокомандующий, а заговорил простой, старый человек, очевидно что то самое нужное желавший сообщить теперь своим товарищам.
В толпе офицеров и в рядах солдат произошло движение, чтобы яснее слышать то, что он скажет теперь.
– А вот что, братцы. Я знаю, трудно вам, да что же делать! Потерпите; недолго осталось. Выпроводим гостей, отдохнем тогда. За службу вашу вас царь не забудет. Вам трудно, да все же вы дома; а они – видите, до чего они дошли, – сказал он, указывая на пленных. – Хуже нищих последних. Пока они были сильны, мы себя не жалели, а теперь их и пожалеть можно. Тоже и они люди. Так, ребята?
Он смотрел вокруг себя, и в упорных, почтительно недоумевающих, устремленных на него взглядах он читал сочувствие своим словам: лицо его становилось все светлее и светлее от старческой кроткой улыбки, звездами морщившейся в углах губ и глаз. Он помолчал и как бы в недоумении опустил голову.
– А и то сказать, кто же их к нам звал? Поделом им, м… и… в г…. – вдруг сказал он, подняв голову. И, взмахнув нагайкой, он галопом, в первый раз во всю кампанию, поехал прочь от радостно хохотавших и ревевших ура, расстроивавших ряды солдат.
Слова, сказанные Кутузовым, едва ли были поняты войсками. Никто не сумел бы передать содержания сначала торжественной и под конец простодушно стариковской речи фельдмаршала; но сердечный смысл этой речи не только был понят, но то самое, то самое чувство величественного торжества в соединении с жалостью к врагам и сознанием своей правоты, выраженное этим, именно этим стариковским, добродушным ругательством, – это самое (чувство лежало в душе каждого солдата и выразилось радостным, долго не умолкавшим криком. Когда после этого один из генералов с вопросом о том, не прикажет ли главнокомандующий приехать коляске, обратился к нему, Кутузов, отвечая, неожиданно всхлипнул, видимо находясь в сильном волнении.


8 го ноября последний день Красненских сражений; уже смерклось, когда войска пришли на место ночлега. Весь день был тихий, морозный, с падающим легким, редким снегом; к вечеру стало выясняться. Сквозь снежинки виднелось черно лиловое звездное небо, и мороз стал усиливаться.
Мушкатерский полк, вышедший из Тарутина в числе трех тысяч, теперь, в числе девятисот человек, пришел одним из первых на назначенное место ночлега, в деревне на большой дороге. Квартиргеры, встретившие полк, объявили, что все избы заняты больными и мертвыми французами, кавалеристами и штабами. Была только одна изба для полкового командира.
Полковой командир подъехал к своей избе. Полк прошел деревню и у крайних изб на дороге поставил ружья в козлы.
Как огромное, многочленное животное, полк принялся за работу устройства своего логовища и пищи. Одна часть солдат разбрелась, по колено в снегу, в березовый лес, бывший вправо от деревни, и тотчас же послышались в лесу стук топоров, тесаков, треск ломающихся сучьев и веселые голоса; другая часть возилась около центра полковых повозок и лошадей, поставленных в кучку, доставая котлы, сухари и задавая корм лошадям; третья часть рассыпалась в деревне, устраивая помещения штабным, выбирая мертвые тела французов, лежавшие по избам, и растаскивая доски, сухие дрова и солому с крыш для костров и плетни для защиты.
Человек пятнадцать солдат за избами, с края деревни, с веселым криком раскачивали высокий плетень сарая, с которого снята уже была крыша.
– Ну, ну, разом, налегни! – кричали голоса, и в темноте ночи раскачивалось с морозным треском огромное, запорошенное снегом полотно плетня. Чаще и чаще трещали нижние колья, и, наконец, плетень завалился вместе с солдатами, напиравшими на него. Послышался громкий грубо радостный крик и хохот.
– Берись по двое! рочаг подавай сюда! вот так то. Куда лезешь то?
– Ну, разом… Да стой, ребята!.. С накрика!
Все замолкли, и негромкий, бархатно приятный голос запел песню. В конце третьей строфы, враз с окончанием последнего звука, двадцать голосов дружно вскрикнули: «Уууу! Идет! Разом! Навались, детки!..» Но, несмотря на дружные усилия, плетень мало тронулся, и в установившемся молчании слышалось тяжелое пыхтенье.
– Эй вы, шестой роты! Черти, дьяволы! Подсоби… тоже мы пригодимся.
Шестой роты человек двадцать, шедшие в деревню, присоединились к тащившим; и плетень, саженей в пять длины и в сажень ширины, изогнувшись, надавя и режа плечи пыхтевших солдат, двинулся вперед по улице деревни.
– Иди, что ли… Падай, эка… Чего стал? То то… Веселые, безобразные ругательства не замолкали.
– Вы чего? – вдруг послышался начальственный голос солдата, набежавшего на несущих.
– Господа тут; в избе сам анарал, а вы, черти, дьяволы, матершинники. Я вас! – крикнул фельдфебель и с размаху ударил в спину первого подвернувшегося солдата. – Разве тихо нельзя?
Солдаты замолкли. Солдат, которого ударил фельдфебель, стал, покряхтывая, обтирать лицо, которое он в кровь разодрал, наткнувшись на плетень.
– Вишь, черт, дерется как! Аж всю морду раскровянил, – сказал он робким шепотом, когда отошел фельдфебель.
– Али не любишь? – сказал смеющийся голос; и, умеряя звуки голосов, солдаты пошли дальше. Выбравшись за деревню, они опять заговорили так же громко, пересыпая разговор теми же бесцельными ругательствами.