مشكلة الجنرالين

في مجال الحوسبة، تُعدّ معضلة الجنرالين (أو معضلة الجنرالين الصينيين ^{[ 1 ]} ) تجربة فكرية تهدف إلى توضيح مخاطر وتحديات تصميم محاولة تنسيق عمل عسكري عبر التواصل من خلال رابط غير موثوق. في هذه التجربة، لا يستطيع جنرالان التواصل إلا بإرسال رسول عبر أراضي العدو. وتطرح التجربة سؤالًا حول كيفية التوصل إلى اتفاق بشأن توقيت شنّ الهجوم، مع العلم أن أي رسول يرسلانه قد يُؤسر.

تُطرح معضلة الجنرالين غالبًا كمقدمة لمعضلة الجنرالات البيزنطيين الأكثر عمومية في المقررات التمهيدية لشبكات الحاسوب (خاصةً فيما يتعلق ببروتوكول التحكم بالنقل ، حيث تُبين أن هذا البروتوكول لا يضمن اتساق الحالة بين نقاط النهاية، وتُوضح أسباب ذلك)، مع أنها تنطبق على أي نوع من أنواع الاتصالات الثنائية التي قد تحدث فيها أعطال. تُعد هذه المعضلة مفهومًا أساسيًا في المنطق المعرفي ، إذ تُبرز أهمية المعرفة المشتركة . ويُشير إليها بعض المؤلفين أيضًا باسم مفارقة الجنرالين ، أو معضلة الجيشين ، أو معضلة الهجوم المنسق . ^{[ 2 ] [ 3 ]} كانت معضلة الجنرالين أول معضلة في اتصالات الحاسوب يُثبت استحالة حلها. ^{[ 4 ]} ومن النتائج المهمة لهذا الإثبات أن التعميمات، مثل معضلة الجنرالات البيزنطيين، لا يُمكن حلها أيضًا في حال حدوث أعطال عشوائية في الاتصال، مما يُوفر أساسًا لتوقعات واقعية لأي بروتوكولات اتساق موزعة.

جيشان ، يقود كل منهما قائد مختلف ، يستعدان لمهاجمة مدينة محصنة. يعسكر الجيشان بالقرب من المدينة، كلٌ في وادٍ خاص به. يفصل وادٍ ثالث بين التلتين، والطريقة الوحيدة للتواصل بين القائدين هي إرسال الرسل عبر هذا الوادي. لسوء الحظ، يحتل المدافعون عن المدينة الوادي، وهناك احتمال أن يُؤسر أي رسول يُرسل عبره. ^{[ 5 ]}

على الرغم من اتفاق الجنرالين على الهجوم، إلا أنهما لم يتفقا على موعده. ولضمان النجاح، يجب أن يهاجم جيشاهما المدينة في وقت واحد، وإلا سيهلك الجيش المهاجم الوحيد. لذا، يجب عليهما التواصل لتحديد موعد الهجوم والاتفاق عليه، مع ضرورة أن يعلم كل جنرال أن الآخر على علم بموافقته على خطة الهجوم. ولأن إشعار استلام الرسالة قد يُفقد بسهولة كما تُفقد الرسالة الأصلية، فإن التوصل إلى اتفاق يتطلب سلسلة لا نهائية من الرسائل . ^{[ 6 ]}

تتضمن التجربة الفكرية التفكير في كيفية التوصل إلى توافق في الآراء. في أبسط صورها، يُعرف أحد الجنرالات بأنه القائد، ويحدد وقت الهجوم، ويجب عليه إبلاغ الجنرال الآخر بهذا الوقت. تكمن المشكلة في ابتكار خوارزميات يمكن للجنرالين استخدامها، بما في ذلك إرسال الرسائل ومعالجة الرسائل الواردة، والتي تمكنهم من التوصل إلى استنتاج صحيح.

مع التسليم بأنه من السهل جدًا على الجنرالات التوصل إلى اتفاق بشأن وقت الهجوم (أي رسالة ناجحة واحدة مع تأكيد ناجح)، فإن دقة مشكلة الجنرالين تكمن في استحالة تصميم خوارزميات يمكن للجنرالات استخدامها للموافقة بأمان على البيان المذكور أعلاه.

قد يبدأ القائد الأول بإرسال رسالة: "الهجوم الساعة 09:00 يوم 4 أغسطس". ولكن بمجرد إرسال الرسالة، لا يعلم القائد الأول ما إذا كانت قد وصلت أم لا. هذا الغموض قد يدفع القائد الأول إلى التردد في الهجوم خشية أن يكون المهاجم الوحيد.

من المؤكد أن الجنرال الثاني قد يرسل تأكيداً إلى الأول: "لقد تلقيت رسالتك وسأهاجم في الساعة 0900 يوم 4 أغسطس". ومع ذلك، قد يواجه الرسول الذي يحمل التأكيد الأسر، وقد يتردد الجنرال الثاني، لعلمه أن الأول قد يتراجع بدون التأكيد.

قد تبدو التأكيدات الإضافية حلاً، كأن يرسل الجنرال الأول تأكيدًا ثانيًا: "تلقيت تأكيدك على الهجوم المخطط له في تمام الساعة 9:00 صباحًا يوم 4 أغسطس". إلا أن هذا المرسل الجديد من الجنرال الأول معرضٌ للوقوع في الأسر أيضًا. وهكذا، يتضح سريعًا أنه مهما تعددت جولات التأكيد، فلا سبيل لضمان الشرط الثاني، وهو أن يكون كل جنرال متأكدًا من موافقة الآخر على خطة الهجوم. سيبقى كلا الجنرالين يتساءلان دائمًا عما إذا كان مرسلهما الأخير قد وصل. ^{[ 7 ]}

بما أن هذا البروتوكول حتمي ، فلنفترض وجود سلسلة من عدد ثابت من الرسائل، تم تسليم واحدة أو أكثر منها بنجاح، وواحدة أو أكثر لم يتم تسليمها. يفترض هذا البروتوكول وجود يقين مشترك لدى كلا القائدين بالهجوم . لننظر إلى آخر رسالة تم تسليمها بنجاح. لو لم يتم تسليم هذه الرسالة الأخيرة بنجاح، لكان أحد القائدين على الأقل (يُفترض أنه المُستقبِل) سيقرر عدم الهجوم. مع ذلك، من وجهة نظر مُرسِل تلك الرسالة الأخيرة، فإن سلسلة الرسائل المُرسَلة والمُسلَّمة هي نفسها تمامًا كما لو تم تسليم تلك الرسالة. بما أن البروتوكول حتمي، فإن القائد الذي أرسل تلك الرسالة الأخيرة سيُقرر الهجوم. لقد خلقنا الآن وضعًا يدفع فيه البروتوكول المُقترح أحد القائدين إلى الهجوم والآخر إلى عدم الهجوم، وهو ما يُناقض الافتراض القائل بأن البروتوكول كان حلًا للمشكلة.

يمكن تشبيه البروتوكول غير الحتمي ذي عدد الرسائل المتغير بشجرة محدودة مُعَلَّمة الحواف ، حيث يُمثل كل عقدة في الشجرة مثالًا مُستكشفًا حتى نقطة مُحددة. يُمثَّل البروتوكول الذي ينتهي قبل إرسال أي رسائل بشجرة تحتوي على عقدة جذرية فقط. تُعَلَّم الحواف من أي عقدة إلى كل فرع بالرسائل المُرسلة للوصول إلى حالة الفرع. تُمثل العقد الطرفية النقاط التي ينتهي عندها البروتوكول. لنفترض وجود بروتوكول غير حتمي P يحل مسألة الجنرالين. عندئذٍ، وبحجة مماثلة لتلك المُستخدمة للبروتوكولات الحتمية ذات الطول الثابت أعلاه، يجب أن يحل P' أيضًا مسألة الجنرالين، حيث تُستخلص الشجرة التي تُمثل P' من شجرة P بإزالة جميع العقد الطرفية والحواف المؤدية إليها. بما أن P محدودة، فإنه يترتب على ذلك أن البروتوكول الذي ينتهي قبل إرسال أي رسائل سيحل المسألة. لكن من الواضح أنه لا يفعل. لذلك، لا يمكن أن يوجد بروتوكول غير حتمي يحل المسألة.

يتمثل أحد الحلول العملية لمشكلة الجنرالين في استخدام آليات تقبل عدم اليقين في قناة الاتصال ، ولا تسعى إلى القضاء عليه تمامًا، بل إلى تخفيفه إلى حد مقبول. على سبيل المثال، يمكن للجنرال الأول إرسال 100 رسالة، متوقعًا أن احتمال وقوعها جميعًا ضئيل. وبهذا الحل، سيهاجم الجنرال الأول مهما حدث، بينما سيهاجم الجنرال الثاني إذا تلقى أي رسالة. أو بدلاً من ذلك، يمكن للجنرال الأول إرسال سلسلة من الرسائل، ويرسل الجنرال الثاني إشعارات استلام لكل رسالة، مع شعور كل منهما براحة أكبر عند تلقي أي رسالة. ولكن كما هو موضح في البرهان، لا يمكن لأي منهما التأكد من تنسيق الهجوم. فلا توجد خوارزمية يمكنهما استخدامها (كالهجوم عند تلقي أكثر من أربع رسائل) تضمن منع أحدهما من الهجوم دون الآخر. كما يمكن للجنرال الأول وضع علامة على كل رسالة تُشير إلى أنها الرسالة رقم 1، 2، 3، ... من أصل n. ستُمكّن هذه الطريقة القائد الثاني من معرفة مدى موثوقية القناة، وإرسال عدد مناسب من الرسائل لضمان احتمال كبير لاستلام رسالة واحدة على الأقل. إذا أمكن ضمان موثوقية القناة، فستكفي رسالة واحدة، ولن تُجدي الرسائل الإضافية نفعًا، إذ إن احتمال ضياع الأخيرة يُعادل احتمال ضياع الأولى.

بافتراض أن على الجنرالات التضحية بأرواحهم في كل مرة يُرسل فيها رسول ويُعترض، يمكن تصميم خوارزمية لتقليل عدد الرسل المطلوبين لتحقيق أعلى مستوى من الثقة في تنسيق الهجوم. ولتجنب التضحية بمئات الأرواح لتحقيق ثقة عالية جدًا في التنسيق، يمكن للجنرالات الاتفاق على استخدام غياب الرسل كمؤشر على أن الجنرال الذي بدأ العملية قد تلقى تأكيدًا واحدًا على الأقل ووعد بالهجوم. لنفترض أن عبور الرسول لمنطقة الخطر يستغرق دقيقة واحدة، فإن السماح بمرور 200 دقيقة من الصمت بعد تلقي التأكيدات سيمكننا من تحقيق ثقة عالية للغاية دون التضحية بأرواح الرسل. في هذه الحالة، يُستخدم الرسل فقط في حالة عدم تلقي أحد الأطراف وقت الهجوم. في نهاية الـ 200 دقيقة، يمكن لكل جنرال أن يستنتج: "لم أتلقَ رسالة إضافية لمدة 200 دقيقة؛ إما أن 200 رسول فشلوا في عبور منطقة الخطر، أو أن هذا يعني أن الجنرال الآخر قد أكد التزامه بالهجوم ويثق في أنني سأفعل ذلك أيضًا".

تم نشر مشكلة الجنرالين وبرهان استحالة حلها لأول مرة بواسطة إي إيه أكويونلو، وك. إيكانادهام، وآر في هوبر في عام 1975 في "بعض القيود والمقايضات في تصميم اتصالات الشبكة"، ^{[ 8 ]} حيث تم وصفها بدءًا من الصفحة 73 في سياق الاتصال بين مجموعتين من رجال العصابات.

أطلق جيم جراي ^{[ 9 ]} على هذه المشكلة اسم مفارقة الجنرالين في عام 1978 في "ملاحظات حول أنظمة تشغيل قواعد البيانات" ^{[ 10 ]} بدءًا من الصفحة 465. ويُستشهد بهذا المرجع على نطاق واسع كمصدر لتعريف المشكلة وبرهان استحالتها، على الرغم من أن كليهما قد نُشر سابقًا كما ذكر أعلاه.

• خوارزمية الإجماع