Екі генералдың мәселесі немесе келісімге келу қиындығы

Кіріспе

Ой эксперименті

Компьютерлік есептерде Екі генералдың мәселесі – сенімсіз байланыс арқылы бірлескен әрекетті үйлестіруге тырысудың қиындықтары мен кемшіліктерін көрсету мақсатындағы ой эксперименті. Экспериментте екі генерал бір-бірімен тек жау территориясы арқылы хабаршы жіберіп қана байланыса алады. Эксперимент олардың шабуылды бастау уақыты туралы келісімге қалай келуі мүмкін екенін сұрайды, бірақ олар жіберген кез келген хабаршының қолға түсуі мүмкін екенін біледі. Екі генералдың мәселесі компьютерлік желілерге кіріспе курстарда (әсіресе, Трансмиссиялық басқару протоколына қатысты, онда TCP нүктелер арасындағы күйдің үйлесімділігіне кепілдік бере алмайтынын және мұның себебін көрсетеді) Византия генералдарының мәселесіне кіріспе ретінде жиі кездеседі, бірақ бұл екі тараптың кез келген түріндегі байланысқа қатысты, онда байланыс үзілу мүмкіндігі бар. Эпистемиялық логикадағы маңызды түсінік ретінде бұл мәселе ортақ білімнің маңыздылығын көрсетеді. Кейбір авторлар бұны Екі генералдың парадоксы, Екі армия мәселесі немесе Ұйымдастырылған шабуыл мәселесі деп те атайды. Екі генералдың мәселесі – компьютерлік байланыс мәселесінің шешілмейтіндігі алғаш рет дәлелденгені. Бұл дәлелдің маңызды салдары – Византия генералдарының мәселесі сияқты жалпылама жағдайлар да кездейсоқ байланыс ақаулары кезінде шешілмейтіндігі, соның салдарынан кез келген таратылған үйлесімділік протоколдары үшін реалистік үміттердің негізін қалайды.

Анықтама

Екі әскер, әрқайсысы әртүрлі қолбасшының басшылығымен, бекітілген қалаға шабуылдауға дайындалып жатыр. Әскерлер қаланың жанында, әрқайсысы өз алқабында орналасқан. Үшінші алқап екі төбенің арасын бөліп тұр, ал екі генералдың байланысудың жалғыз жолы – сол алқап арқылы хабаршы жіберу. Өкінішке орай, алқап қаланың қорғаушыларымен толып жатыр, сондықтан алқап арқылы жіберілген кез келген хабаршы тұтқындалуы мүмкін. Екі генерал шабуыл жасауға келіскенмен, шабуыл уақытын әлі келісімге келген жоқ. Сәттілік үшін екі генералдың әскерлері қалаға бір уақытта шабуылдауы қажет, әйтпесе жалғыз шабуылдаушы әскер тыйырылып қалуы мүмкін. Олар бір-бірімен байланысып, шабуыл уақытын анықтап, сол уақытта шабуылдауға келісуі керек, сондай-ақ әр генерал екінші генералдың шабуыл жоспарына келіскенін білуі тиіс. Хабардың түскенін растау бастапқы хабар сияқты жоғалуы мүмкін болғандықтан, консенсусқа жету үшін хабарлардың шексіз тізбегі қажет болуы мүмкін. Ой эксперименті олардың консенсусқа қалай келуі мүмкін екенін қарастыруды қамтиды. Ең қарапайым жағдайда, бір генералдың жетекші екені белгілі, ол шабуыл уақытын шешеді және осы уақытты екінші генералға жеткізуі керек. Мәселе – генералдар қолдана алатын алгоритмдерді табу, соның ішінде хабарламаларды жіберу және түскен хабарламаларды өңдеу, оларға дұрыс қорытынды жасауға мүмкіндік беретін алгоритмдерді табу: «Иә, біз келісілген уақытта шабуылдаймыз». Генералдардың шабуыл уақыты туралы келісімге келуі (яғни, сәтті хабарлама және сәтті растау) салыстырмалы түрде оңай болғанымен, «Екі генералдың мәселесінің» күрделігі – генералдарға жоғарыда аталған мәлімдемеге қауіпсіз келісуге мүмкіндік беретін алгоритмдерді құрудың мүмкін еместігінде.

Проблеманы көрсету

Бірінші генерал "4 тамызда сағат 0900-де шабуыл жасаңыз" деген хабарлама жіберуі мүмкін. Бірақ, хабаршы жіберілген соң, бірінші генералдың хабар жеткеніне сенімді болуының жолы жоқ. Бұл белгісіздік бірінші генералға жалғыз шабуылдау қаупінен сақтандырып, шабуылға барудан тартындыруы мүмкін. Әрине, екінші генерал біріншісіне: "Мен сіздің хабарыңызды алдым, 4 тамызда сағат 0900-де шабуыл жасаймын" деп растау жіберуі мүмкін. Алайда, растауды жеткізген хабаршы тұтқындалуы мүмкін, және екінші генерал біріншісі растау келмесе шабуылдамай қалуы мүмкін екенін біліп, күмәнмен қарауы мүмкін. Көбірек растаулар шешімдей көрінуі мүмкін – бірінші генерал екінші растау жіберсін: "Мен сіздің жоспарланған шабуыл туралы растауыңызды 4 тамызда сағат 0900-де алдым". Бірақ, бірінші генералдың жаңа хабаршысы да тұтқындалуы мүмкін. Осылайша, қанша рет растау жасалса да, екінші талапты – әр генералдың екіншісі шабуыл жоспарына келіскеніне толық сенімді болуын қамтамасыз етудің жолы жоқ екені анық көрінеді. Екі генерал да соңғы хабаршыларының жеткеніне күмәндана береді.

Дәлел

Бұл протокол детерминистік болғандықтан, бір немесе бірнеше сәтті жеткізілген, ал бір немесе бірнеше хабарлама жеткізілмеген, белгілі бір саны бар тізбек бар деп есептейік. Екі генералдың да шабуылға келісуі үшін ортақ нақтылық болуы керек. Соңғы сәтті жеткізілген хабарламаны қарастырайық. Егер соңғы хабарлама сәтті жеткізілмесе, онда кем дегенде бір генерал (көбінесе алушы) шабуылға шықпауға шешім қабылдайды. Алайда, соңғы хабарламаны жіберушінің көзқарасынан, жіберілген және жеткізілген хабарламалардың тізбегі, егер бұл хабарлама жеткізілген болса да, дәл сол болар еді. Протокол детерминистік болғандықтан, соңғы хабарламаны жіберген генерал шабуылға шығуға шешім қабылдайды. Енді біз бір генералдың шабуылға, ал екіншісінің шабуылға шықпауына әкелетін жағдай жасадық, бұл протокол мәселені шешеді деген болжамға қайшы. Өзгермелі хабарламалар саны бар детерминистік емес протоколды жиектері таңбаланған шекті ағаш ретінде қарастыруға болады, онда ағаштағы әрбір түйін белгілі бір уақытқа дейін зерттелген жағдайды көрсетеді. Ешқандай хабарлама жібермей тоқтатылатын протокол тек түбір түйіні бар ағашпен бейнеленеді. Түйінден әрбір балаға дейінгі жиектер баланың күйіне жету үшін жіберілген хабарламалармен таңбаланады. Жапырақ түйіндері протокол тоқтатылатын нүктелерді көрсетеді. Екі генералдың мәселесін шешетін детерминистік емес протокол P бар деп есептейік. Онда, жоғарыдағы белгілі ұзындығы бар детерминистік протоколдар үшін қолданылған сияқты аргумент бойынша, P' де екі генералдың мәселесін шешуі керек, мұнда P'-ті білдіретін ағаш P үшін барлық жапырақ түйіндерін және оларға жететін жиектерді алып тастау арқылы алынады. P шекті болғандықтан, ешқандай хабарлама жібермей тоқтатылатын протокол мәселені шешеді деген қорытындыға келеміз. Бірақ бұл анық емес. Сондықтан, мәселені шешетін детерминистік емес протокол болуы мүмкін емес.

Инженерлік тәсілдер

Екі генералдың мәселесімен күресудің прагматикалық тәсілі – байланыс арнасының белгісіздігін қабылдап, оны жоюға тырыспай, оны қанағаттанарлық деңгейде азайтуға бағытталған схемаларды қолдану. Мысалы, бірінші генерал 100 хабаршы жіберіп, олардың бәрінің тұтқындалу ықтималдығы төмен деп есептеуі мүмкін. Осы тәсілмен бірінші генерал жағдай қандай болмасын шабуыл жасайды, ал екінші генерал кез келген хабарлама алса шабуыл жасайды. Балама ретінде, бірінші генерал хабарламалар ағынын жіберсе, екінші генерал әрқайсысына растама жіберуі мүмкін, бұл әр генерал алған әрбір хабарламамен көбірек сенімділікке ие болады. Дегенмен, дәлелдемеде көрсілгендей, шабуылдың үйлестірілетініне ешкім толық сенімді бола алмайды. Олар қолдана алатын ешқандай алгоритм жоқ (мысалы, егер төрттен артық хабарлама алынса шабуыл жасау), біреуі екіншісіз шабуыл жасауына кепілдік беретін алгоритм жоқ. Сонымен қатар, бірінші генерал әр хабарламада оның n-нің 1, 2, 3-ші хабарламасы екенін көрсететін белгі қоюы мүмкін. Бұл әдіс екінші генералга арнаның қаншалықты сенімді екенін білуге және кем дегенде бір хабарламаның алынуын қамтамасыз ету үшін тиісті мөлшерде хабарламаларды қайтаруға мүмкіндік береді. Егер арна сенімді болу үшін жасалса, бір хабарлама жеткілікті болады және қосымша хабарламалар көмектеспейді. Соңғы хабарлама да біріншісі сияқты жоғалуы мүмкін. Егер генералдар хабаршы жіберілген және ұсталған сайын өмірлерін құрбан етуге мәжбүр болса, шабуылдың үйлестірілуіне максималды сенімділікке жету үшін қажетті хабаршылар санын азайтуға бағытталған алгоритм жасалуы мүмкін. Ынғайлы үйлесімділікке қол жеткізу үшін жүздеген өмірді құрбан етуден сақтау үшін генералдар хабаршылардың болмауын транзакцияны бастаған генерал кем дегенде бір растама алғанын және шабуылға уәде бергенін көрсететін сигнал ретінде пайдалануға келісе алады. Егер хабаршының қауіпті аймақты кесіп өтуіне 1 минут керек болса, растамалар алынғаннан кейін 200 минут үнсіздікке жол беру хабаршылардың өмірін құрбан етусіз өте жоғары сенімділікке қол жеткізуге мүмкіндік береді. Бұл жағдайда хабаршылар тек тарап шабуыл уақытын алмаған жағдайда ғана қолданылады. 200 минуттан кейін әр генерал былай ойлай алады: "Мен 200 минуттан бері қосымша хабарлама алмадым; немесе 200 хабаршы қауіпті аймақты кесіп өте алмады, немесе бұл екінші генерал шабуылға кіріскенін растады және мен де солай боламын деп сенімді".

A pragmatic approach to dealing with the Two Generals' Problem is to use schemes that accept the uncertainty of the communications channel and not attempt to eliminate it, but rather mitigate it to an acceptable degree. For example, the first general could send 100 messengers, anticipating that the probability of all being captured is low. With this approach, the first general will attack no matter what, and the second general will attack if any message is received. Alternatively, the first general could send a stream of messages and the second general could send acknowledgments to each, with each general feeling more comfortable with every message received. As seen in the proof, however, neither can be certain that the attack will be coordinated. There is no algorithm that they can use (e. g. attack if more than four messages are received) that will be certain to prevent one from attacking without the other. Also, the first general can send a marking on each message saying it is message 1, 2, 3 of n. This method will allow the second general to know how reliable the channel is and send an appropriate number of messages back to ensure a high probability of at least one message being received. If the channel can be made to be reliable, then one message will suffice and additional messages do not help. The last is as likely to get lost as the first. Assuming that the generals must sacrifice lives every time a messenger is sent and intercepted, an algorithm can be designed to minimize the number of messengers required to achieve the maximum amount of confidence the attack is coordinated. To save them from sacrificing hundreds of lives to achieve very high confidence in coordination, the generals could agree to use the absence of messengers as an indication that the general who began the transaction has received at least one confirmation and has promised to attack. Suppose it takes a messenger 1 minute to cross the danger zone, allowing 200 minutes of silence to occur after confirmations have been received will allow us to achieve extremely high confidence while not sacrificing messenger lives. In this case, messengers are used only in the case where a party has not received the attack time. At the end of 200 minutes, each general can reason: "I have not received an additional message for 200 minutes; either 200 messengers failed to cross the danger zone, or it means the other general has confirmed and committed to the attack and has confidence I will too".

Тарих

Екі генералдың проблемасы және оның мүмкін еместігін дәлелдеуі алғаш рет 1975 жылы Э. А. Аккоюнлу, К. Эканадхам және Р. В. Губер «Желілік коммуникацияларды жобалаудағы кейбір шектеулер мен сауда-саттықтар» деген еңбегінде жарияланды, онда ол 73-беттен бастап екі топ қылмыскер арасындағы байланыс контекстінде сипатталған. Бұл мәселеге 1978 жылы Джим Грей «Деректер базасының операциялық жүйелері туралы ескертулер» еңбегінде 465-беттен бастап «Екі генералдың парадоксы» деген атау берді. Бұл сілтеме проблеманың анықтамасы мен мүмкін еместігін дәлелдеудің көзі ретінде кеңінен пайдаланылады, бірақ екеуі де жоғарыда айтылғандай, бұрын жарияланған.