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

Візантія. Ніч напередодні великої битви. Візантійська армія складається з n легіонів, і кожен з них підпорядковується своєму генералу. Окрім цього, армія має головнокомандувача, котрий керує генералами. Однак імперія перебуває в занепаді і до третини генералів (разом із головнокомандувачем), можуть бути зрадниками. Протягом ночі кожен з генералів отримує від головнокомандувача наказ про дії вранці. Можливі два варіанти наказу: «атакувати» або «відступати». Якщо всі чесні генерали атакують, то вони перемагають. Якщо вони відступають, то їм вдається зберегти армію. Але якщо частина з них атакує, а частина відступає, то вони зазнають поразки. Якщо головнокомандувач буде зрадником, то він може дати генералам різні накази, тому накази головнокомандувача не варто виконувати беззаперечно. Якщо кожен генерал буде діяти незалежно від інших, то результат може бути поганим. Вочевидь, вони потребують обміну інформацією один з одним (стосовно отриманих наказів) для узгодженості дій.

Кожен із генералів має отримати один і той же вектор довжини n, у котрому i-й елемент або містить чисельність ${\displaystyle i}$-ї армії (якщо її командувач лояльний), або невизначений (якщо командувач — зрадник).

В результаті розв'язання цієї проблеми виникло дві математичні моделі — інтерактивна система доведень і доведення з нульовим розголошенням.

Інтерактивну систему доведень (Р, V, S) слід розуміти як протокол взаємодії двох абонентів: Р (той що доводить) та V (той що перевіряє). Абонент Р хоче довести V, що твердження S істинне. Абонент V самостійно, без допомоги Р, не може довести твердження S (тому V й називають перевіряльником). Абонент Р може бути й ворогом, котрий хоче довести V, що твердження S істинне, хоча воно хибне. Протокол може складатися з багатьох раундів обміну повідомленнями між Р та V і має відповідати двом умовам:

• 1) повнота — якщо S справді істинне, то абонент Р майже переконає абонента V визнати його істинним;
• 2) коректність — якщо S хибне, то абонент Р навряд чи переконає абонента V, що S — істинне.

Наголосимо на тому, що у визначенні системи (Р, V, S) не припускалося, що V може бути ворогом. А що, коли V є ворогом, котрий хоче дізнатися від Р якусь нову (цікаву для себе) інформацію про твердження S? У такому разі Р, звісно, не бажає, щоб це трапилось як наслідок роботи протоколу (Р, V, S). Протокол (Р, V, S), що розв'язує таку задачу, називається доведенням із нульовим розголошенням і має відповідати, окрім умов 1 і 2, ще такій умові:

• 3) нульове розголошення (або стійкість) — у результаті роботи протоколу (Р, V, S) абонент V не збільшує свої знання про твердження S або, іншими словами, не зможе здобути ніякої інформації про те, чи S істинне.

Відповідний рекурсивний алгоритм запропонував 1982 року Леслі Лампорт.

Наведемо приклад для випадку коли n=4 і m=1, де: n — загальна кількість генералів, m — кількість зрадників. У такому разі алгоритм має довжину 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 знову може надіслати неправильні значення).

Генерали отримують наступні вектори:

4-й крок. Кожен генерал перевіряє кожен елемент у всіх отриманих векторах. Якщо якесь значення збігається не менше, аніж у двох векторах, то воно потрапляє до остаточного вектора, інакше відповідний елемент остаточного вектора позначається невідомим.

Усі лояльні генерали отримують один вектор (1,2,невідомий,4) — згоди досягнуто.

Лампорт довів, що в системі, де m елементів працює неправильно, згоди можна досягти лише коли 2m+1 інших елементів працює правильно (лояльних генералів більше, ніж дві третини).

• 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."(англ.)
• Криптографія: нові напрямки