🤖 AI

Resilient Byzantine Agreement with Predictions

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

المؤلفون الأصليون: Julien Dallot, Darya Melnyk, Tijana Milentijevic, Stefan Schmid, Patrik Welters

نُشر 2026-05-20

📖 4 دقيقة قراءة☕ قراءة في استراحة قهوة

CC BY 4.0

المؤلفون الأصليون: Julien Dallot, Darya Melnyk, Tijana Milentijevic, Stefan Schmid, Patrik Welters

البحث الأصلي مرخَّص بموجب CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ هذا شرح مولَّده بالذكاء الاصطناعي للبحث أدناه. لم يكتبه المؤلفون ولم يصادقوا عليه. وللتحقق من الدقة التقنية، يرجى الرجوع إلى البحث الأصلي. اقرأ إخلاء المسؤولية الكامل

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

في علوم الحاسوب، يُسمى هذا "الاتفاق البيزنطي" (Byzantine Agreement). والسؤال الكبير هو: كم عدد المشاغبين الذين يمكن للمجموعة أن تتحملهم قبل أن تعجز عن الاتفاق تماماً؟

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

هذه الورقة البحثية تطرح سؤالاً جديداً: ماذا لو كان لدى الأصدقاء "تنبؤ" أو "شعور داخلي" بشأن من هم المشاغبون؟ رب Maybe لديهم تطبيق ذكي يراقب السلوك ويقول: "أعتقد أن أليس وبوب صادقان، لكن تشارلي يبدو مريباً".

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

إليك تفصيل لنتائجهم باستخدام تشبيهات بسيطة:

1. "مفتاح الثقة" (المقايضة)

صمم الباحثون نظاماً حيث يمكنك تدوير "مفتاح الثقة" (معامل يسمى $\alpha$ ).

تدوير المفتاح للأعلى (ثقة عالية): أنت تخبر الخوارزمية: "أنا أثق حقاً في تطبيق التنبؤ هذا!" ستقوم الخوارزمية حينها بتجاهل أي شخص يقول التطبيق إنه مريب، وتكتفي بالاستماع إلى "الصادقين" فقط.
- الفائدة: إذا كان التطبيق دقيقاً تماماً، يمكن للمجموعة أن تنجو بوجود عدد أكبر بكثير من المشاغبين مما هو معتاد.
- المخاطرة: إذا كان التطبيق خاطئاً تماماً (يعتقد أن المشاغبين صادقون)، فستصبح المجموعة هشة جداً وقد تفشل حتى مع وجود عدد قليل من المشاغبين.
تدوير المفتاح للأسفل (ثقة منخفضة): أنت تخبر الخوارزمية: "أنا لا أثق في التطبيق كثيراً." الخوارزمية هنا تلعب دور الحذر.
- النتيجة: لا تكتسب الخوارزمية قوة إضافية كبيرة عندما يكون التطبيق صحيحاً، لكنها لا تخسر الكثير من الأمان عندما يكون التطبيق خاطئاً.

الاكتشاف الكبير: لا يمكنك الحصول على الأمرين معاً بشكل مثالي. لا يمكنك الحصول على الأمان الفائق لسيناريو "التنبؤ المثالي" والأمان الفائق لسيناريو "عدم وجود تنبؤ" في آن واحد. عليك اختيار توازنك.

2. "المنزلق الناعم" (السلاسة)

هناك خوف شائع من التنبؤات وهو: "ماذا لو كان التطبيق صحيحاً في معظم الأحيان، لكنه يرتكب بعض الأخطاء؟ هل سينهار النظام بالكامل فوراً؟"

وجد المؤلفون أن خوارزميتهم سلسة، مثل منزلق لطيف وليس كمنحدر حاد.

التشبيه: تخيل أن قدرة المجموعة على تحمل المشاغبين هي بمثابة دلو من الماء.
- في الإعداد القياسي (غير الموثق)، في كل مرة يرتكب فيها تطبيق التنبؤ خطأً واحداً (يتنبأ بكاذب على أنه صادق، أو بصادق على أنه كاذب)، يفقد الدلو وحدة واحدة من الماء. كلما زادت الأخطاء، قل الماء الذي تملكه، لكنه ينقص تدريجياً.
- في الإعداد الموثق (حيث يوقع الجميع رسائلهم بختم رقمي)، يكون الدلو أكثر متانة. يتطلب الأمر خطأين من التطبيق لفقدان وحدة واحدة فقط من الماء. النظام أكثر تسامحاً مع الأخطاء.

هذا يعني أن النظام لا يتعطل فجأة عندما تكون دقة التنبؤ 90%؛ بل يضعف قليلاً فقط مع انخفاض الدقة.

3. مشكلة "المحلي مقابل العالمي"

نظرت الورقة أيضاً فيما يحدث إذا كان لكل فرد تطبيق تنبؤ خاص به قد يختلف عن تطبيق جاره.

النتيجة: إذا كان لدى الجميع قائمة مختلفة عمن يعتقدون أنه صادق، فإن النظام ينهار تماماً. إذا وثقت المجموعة في التنبؤات ولو قليلاً (أكثر من 50%)، وكانت التنبؤات تختلف بين الأشخاص، فلا يمكن للمجموعة ضمان الأمان على الإطلاق.
التشبيه: إذا كان نصف المجموعة يعتقد أن "أليس كاذبة" والنصف الآخر يعتقد أن "أليس قديسة"، ولم يتمكنوا من التواصل لمقارنة ملاحظاتهم، فلن يتمكنوا أبداً من الاتفاق على خطة. تثبت الورقة أنه في سيناريو "التنبؤ المحلي" هذا، لا يمكنك حقاً تحسين الأمان فوق الطرق القياسية القديمة.

ملخص "قواعد اللعبة"

تقدم الورقة خريطة رياضية لهذه السيناريوهات:

التنبؤات العالمية (الجميع يرى نفس القائمة): يمكنك المقايضة بين "الأمان الفائق إذا كان التنبؤ صحيحاً" وبين "الأمان إذا كان التنبؤ خاطئاً". كلما زدت ثقتك في التنبؤ، زاد ما تكسبه عندما يكون صحيحاً، ولكن زاد ما تخسره عندما يكون خاطئاً.
تكلفة الأخطاء: النظام يتدهور تدريجياً. إنه لا ينهار فجأة؛ بل يفقد ببطء قدرته على التعامل مع المشاغبين مع سوء جودة التنبؤ.
الحد الأقصى: لا يمكنك استخدام التنبؤات لكسر القوانين الأساسية للحوسبة الموزعة (مثل حدود 1/3 أو 1/2) في كل الحالات. إذا كان التنبؤ سيئاً، فأنت تعود إلى نقطة الصفر.

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

ملخص تقني: اتفاق بيزنطي مرن مع التنبؤات

بيان المشكلة

تتطلب مشكلة الاتفاق البيزنطي (Byzantine Agreement - BA) مجموعة من $n$ من العقد الموزعة للاتفاق على قيمة مخرجات مشتركة رغم وجود أعطال عشوائية (بيزنطية) في العقد. في الإعدادات القياسية بدون توثيق، يستحيل تحقيق الاتفاق إذا تجاوز عدد العقد المعيبة $f$ نسبة $n/3$ ؛ ومع وجود قنوات موثقة (توقيعات رقمية)، يتحسن هذا الحد ليصل إلى $f < n/2$ .

تبحث هذه الورقة فيما إذا كان استخدام تنبؤات تعلم الآلة (ML) المتعلقة بسلوك العقد يمكن أن يحسن حدود المرونة هذه. وتحديدًا، ينظر المؤلفون في حالة حيث تتلقى كل عقدة، بالإضافة إلى مدخلها الثنائي، مجموعة تنبؤ $P$ تشير إلى العقد الصادقة. التحدي الجوهري هو أن التنبؤات بطبيعتها غير موثوقة؛ لذا يجب على الخوارزمية الموازنة بين الاتساق (تحسين المرونة عندما تكون التنبؤات صحيحة) والمتانة (الحفاظ على السلامة عندما تكون التنبؤات خاطئة أو معادية). كما تستكشف الورقة مفهوم النعومة (Smoothness)، والمتمثل في معدل تدهور المرونة مع انخفاض دقة التنبؤ.

المنهجية

يحلل المؤلفون خوارزميات معززة بالتنبؤ تحت نموذجين للاتصال:

القنوات غير الموثقة: الرسائل غير مشفرة؛ ويمكن للعقد المعيبة تزوير أو تعديل سجلات الاتصال.
القنوات الموثقة: الرسائل موقعة رقميًا؛ لا يمكن للعقد المعيبة تزوير الرسائل ولكن لا يزال بإمكانها قراءتها.

علاوة على ذلك، يميزون بين نموذجين للتنبؤ:

التنبؤات العالمية (Global Predictions): تتلقى جميع العقد نفس مجموعة التنبؤ $P$ (على سبيل المثال، من نظام مراقبة مركزي).
التنبؤات المحلية (Local Predictions): تتلقى كل عقدة $i$ مجموعة التنبؤ الخاصة بها $P_i$ ، والتي قد تختلف من عقدة لأخرى.

تستخدم الخوارزميات المقترحة معامل ثقة $\alpha \in [0, 1]$ . يحدد هذا المعامل سلوك الخوارما: فكلما زادت قيمة $\alpha$ ، زاد اعتماد الخوارزمية على المتنبئ، بهدف تحقيق اتساق أعلى (تحمل المزيد من الأعطال عند كمال التنبؤات) ولكن مع احتمال انخفاض المتانة. تعمل الخوارزميات عمومًا في مرحلتين:

مرحلة الاختيار: تقوم العقد ببناء مجموعة فرعية $L$ من العقد "النشطة" بناءً على التنبؤ $P$ . ولضمان المتانة، تفرض الخوارزمية حدًا أدنى لحجم $L$ ، حيث يتم إضافة عقد بشكل حتمي إذا كانت مجموعة التنبؤ صغيرة جدًا.
مرحلة الاتفاق: يتم تنفيذ بروتوكول اتفاق بيزنطي قياسي (مثل Phase King للقنوات غير الموثقة، أو Dolev-Strong للقنوات الموثقة) فقط بين العقد الموجودة في $L$ . أما العقد خارج $L$ فتتصرف بشكل سلبي، حيث تتبنى القيمة التي تم الاتفاق عليها.

المساهمات والنتائج الرئيسية

1. توصيف مقايضات الاتساق والمتانة (التنبؤات العالمية)

تقدم الورقة توصيفًا كاملًا للمقايضات بين الاتساق والمتانة بالنسبة للتنبؤات العالمية.

إعداد القنوات غير الموثقة: من أجل تحقيق اتساق مستهدف قدره $\alpha \cdot n$ (تحمل ما يصل إلى $\alpha \cdot n$ من الأعطال عندما تكون التنبؤات مثالية)، تحقق الخوارزمية متانة قدرها $\frac{1-\alpha}{2} \cdot n - 1$ من العقد المعيبة عندما تكون التنبؤات عشوائية.
إعداد القنوات الموثقة: تتحسن حدود المتانة لتصل إلى $(1 - \alpha) \cdot n - 1$ .
نتائج الاستحالة: يثبت المؤلفون نتائج استحالة مطابقة باستخدام حجج عدم التمييز. حيث أظهروا أنه لأي خوارزمية ذات اتساق $\alpha$ ، لا يمكن أن تتجاوز المتانة هذه الحدود. ومن الأهمية بمكان أنهم أثبتوا أنه، على عكس تعقيد الجولات، من المستحيل استخدام التنبؤات لتحسين الخوارزمية بشكل صارم في جميع الحالات (على سبيل المثال، عبر تشغيل خوارزمية احتياطية) لأنه لا يمكن اكتشاف متى فشلت الخوارزمية المعززة بالتنبؤ.

2. تحليل النعومة

تحلل الورقة كيفية تدهور المرونة مع زيادة خطأ التنبؤ $\eta$ (عدد العقد التي تم التنبؤ بها بشكل خاطئ).

التدهور الخطي: في الإعداد غير الموثق، تنخفض المرونة خطيًا مع زيادة عدد التنبؤات الخاطئة: كل خطأ إضافي يقلل من عدد الأعطال التي يمكن تحملها بمقدار وحدة واحدة (حتى نقطة التحول).
الإعداد الموثق: يتراجع التدهور إلى النصف؛ حيث يتطلب الأمر خطأين في التنبؤ لفقدان وحدة واحدة من المرونة.
نقاط التحول: يحدد المؤلفون عتبات خطأ محددة يتغير عندها ميل منحنى النعومة، مما يوضح أن الانتقال هو انتقال أمثل ولا يمكن تجنبه.

3. استحالة التنبؤات المحلية

بالنسبة لنموذج التنبؤ المحلي (حيث تمتلك العقد رؤى مختلفة للنظام)، تقدم الورقة نتيجة استحالة قوية.

النتيجة: أي خوارزمية تحقق اتساقًا قدره $\alpha \geq 1/2$ (في الحالة الموثقة) أو $\alpha \geq 1/3$ (في الحالة غير الموثقة) تحت التنبؤات المحلية يجب أن تمتلك متانة صفرية ( $\beta = 0$ ).
الآثار المترتبة: لا تقدم التنبؤات المحلية ضمانات أفضل من الخوارزميات القياسية الخالية من التنبؤ فيما يتعلق بالمقايضة بين الاتساق والمتانة. وتترك الورقة مسألة وجود مقايضات غير بديهية لقيم الاتساق في النطاق $[1/3, 1/2)$ للقنوات غير الموثقة دون إجابة.

الأهمية

تؤسس هذه الورقة حقيقة أن التنبؤات يمكن أن تحسن بالفعل مرونة بروتوكولات الاتفاق البيزنطي، ولكن هذا التحسين يأتي مع مقايضات صارمة وقابلة للقياس الكمي.

المثالية: تحقق الخوارزميات المقترحة الحدود النظرية للمقايضة بين الاتساق والمتانة، مما يثبت أن الحدود المستمدة دقيقة ومستقلة عن نظام التنبؤ المستخدم.
النعومة: يوضح العمل أن المرونة لا تنهار فجأة عندما تكون التنبؤات غير دقيقة؛ بل تتدهور بسلاسة، مما يسمح للأنظمة بالبقاء وظيفية حتى مع وجود أخطاء تنبؤ كبيرة.
القيود: تسلط النتائج الضوء على حد جوهري لأنظمة التنبؤ اللامركزية: بدون رؤية عالمية متسقة لموثوقية العقد (التنبؤات العالمية)، تتلاشى فوائد التعزيز بالتنبؤ فيما يتعلق بمتطلبات الاتساق العالية.

يخلص المؤلفون إلى أن عملهم يمثل بداية لدراسة المرونة في الأنظمة الموزعة المعززة بالتنبؤ، مما يوفر أساسًا نظريًا لتصميم بروتوكولات تستفيد من تنبؤات تعلم الآلة مع الحفاظ على ضمانات سلامة قابلة للإثبات.