Задача двох генералів

Задача двох генералів (задача двох армій, проблема скоординованої атаки) — в обчислювальній техніці уявний експеримент, що ілюструє проблему синхронізації стану двох систем по ненадійному каналу зв'язку. Ця задача подібна на більш загальну задачу візантійських генералів, хоча і була сформульована пізніше за неї. Задача часто згадується на початку курсу комп'ютерних мереж (зокрема при розгляді протоколу TCP). Назву для цієї задачі придумав Джим Грей.

Визначення

Посильні між арміями A1 та A2 можуть бути перехоплені ворогом B.

Дві армії, кожна під проводом свого генерала, готуються до штурму міста. Табори армій розділені ворожою територією. Єдиним засобом зв'язку для генералів є відправка посильних через ворожу територію, де вони можуть бути перехоплені.

Для успішного штурму генерали повинні атакувати місто одночасно. Атака однією армією приречена на поразку. Потрібно розробити алгоритм обміну повідомленнями, що дозволяє кожному генералу бути впевненому в узгодженні часу атаки.

Ілюстрація проблеми

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

В свою чергу, другий генерал отримавши повідомлення з часом атаки і пославши повідомлення з підтвердженням, не може бути впевненим, що перший генерал отримає його підтвердження. Йому теж необхідне підтвердження доставки свого повідомлення.

Таким чином задача не має розв'язку.

Доведення від супротивного

Припустимо, що існує деяка мінімальна послідовність доставлених чи перехоплених повідомлень, що гарантує обом генералам впевненість в узгодженні часу штурму. Розглянемо останнє повідомлення цієї послідовності. Воно теж може бути перехоплене. В такому випадку його отримувач не буде мати підтвердження і може не розпочати атаку. В іншого ж генерала є впевненість в узгодженості дій, тому він розпочне атаку. Тобто, при існуванні алгоритму узгодження можлива ситуація поразки, що суперечить припущенню про існування алгоритму.

Інженерний підхід

Прагматичний підхід до розв'язку задачі не бореться з усуненням ненадійності каналу зв'язку, а зводить його до допустимого рівня.

Наприклад:

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

Посилання