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