💻 computer science

Hermes: Low Tail-Latency Via Prefix Consensus

إن هيرميس (Hermes) هو بروتوكول توافق آراء (BFT) ذو جولة دورية للقائد مكون من جولتين لعدد $n=5f+1$ من العمليات، يعمل على القضاء على حالات توقف زمن الاستجابة المتأخرة الناتجة عن القادة البطيئين أو المنهارين عبر استخدام توافق بادئة (prefix consensus) لإتمام أثقل بادئة مشتركة من أي $n-f$ أصوات، مما يضمن استمرارية التقدم حتى عند انتهاء صلاحية الرؤى (views).

المؤلفون الأصليون: Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

نُشر 2026-07-29

📖 6 دقيقة قراءة🧠 قراءة متعمّقة

CC BY 4.0

المؤلفون الأصليون: Alejandro Ranchal-Pedrosa, Dakai Kang, Neil Giridharan, Dahlia Malkhi, Mohammad Sadoghi, Ben Marsh

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

تخيل مجموعة من الأصدقاء يحاولون اتخاذ قرار بشأن فيلم لمشاهدته، لكنهم مشتتون في جميع أنحاء العالم، وبعضهم لديه اتصال إنترنت ضعيف، وقليل منهم أصدقاء مشاكسون يحاولون تخريب القرار عن طريق إرسال روابط مزيفة أو التظاهر بأنهم غير متصلين بالإنترنت. هذا هو عالم "تحمل الخطأ البيزنطي" (Byzantine Fault Tolerance - BFT). في علوم الحاسوب، هذه هي الطريقة التي تتفق بها شبكة من الحواسيب على حقيقة واحدة — مثل ترتيب المعاملات في سلسلة الكتل (blockchain) — دون الاعتماد على مدير مركزي واحد. والهدف هو الوصول إلى اتفاق بسرعة (زمن استجابة منخفض) حتى عندما تتعطل بعض الحواسيب أو تتصرف بشكل خبيث.

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

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

المشكلة: "فخ المهلة الزمنية"

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

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

الحل: "هيرميس" و"الأرضية المشتركة"

يغير "هيرميس" قواعد اللعبة. بدلاً من معاملة القائد البطيء كفشل كلي، يعامل "هيرميس" الاتفاق الجزئي للمجموعة كأنه انتصار.

إليك كيف يعمل ذلك باستخدام تشبيه إبداعي: تخيل أن الفريق يحاول بناء برج طويل من المكعبات.

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

هذا هو الابتكار الجوهري: "إجماع البادئة" (Prefix Consensus). في الأيام الخوالي، إذا صوت شخصان على أبراج مختلفة قليلاً، كانت أصواتهما تعتبر خلافاً ويتم استبعادها. يقول "هيرميس": "انتظروا، إنهم يتفقون على الـ 90% السفلية من البرج! لنقم بتثبيت ذلك والمضي قدماً".

كيف يعمل "هيرميس": الرقصة ذات المرحلتين

يعمل "هيرميس" عبر "رؤى" (views/rounds)، لكل منها قائد معين. وهو يستخدم رقصة ذكية من خطوتين:

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

هذا يعني أنه حتى لو فشل القائد، فإن المجموعة لا تفقد الرؤية. إنهم ينهون الجزء المشترك من البرج ويبدأون الجولة التالية فوراً. "المهلة الزمنية"، التي كانت في السابق طريقاً مسدوداً، تنتج الآن نتيجة.

سحر "البوادئ" و"القفزات"

لجعل هذا يعمل مع مسارات متعددة من البيانات (مثل طريق سريع به العديد من مسارات حركة المرور)، يستخدم "هيرميس" ترميزاً خاصاً يسمى "نهايات طرفية نسبية للأب" (parent-relative delta tipcuts).

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

النتائج: السرعة والأمان

يثبت البحث رياضياً أن "هيرميس" آمن (لن يختلف شخصان صادقان أبداً على الجزء الذي تم تثبيته) وحي (النظام سيستمر دائماً في المضي قدماً).

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

يوضح المؤلفون أنه باستخدام "ترميز الإزالة" (erasure coding) (وهي طريقة لتجزئة البيانات بحيث يمكن إعادة بنائها حتى لو فُقدت بعض الأجزاء)، يحافظ "هيرميس" على تكاليف الاتصال منخفضة، حتى عند التعامل مع العديد من مسارات البيانات.

لماذا يهم هذا؟

يحل "هيرميس" معضلة "المهلة الزمنية" بجعل المهلة الزمنية نفسها مثمرة. إنه يحول لحظة الفشل إلى لحظة تقدم. بدلاً من السؤال: "هل وصل القائد؟" والانتظار لرؤية النتيجة، يسأل "هيرميس": "ما الذي اتفقنا عليه جميعاً؟" ويمضي قدماً.

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

ملخص تقني: هيرميس (Hermes): زمن استجابة ذيل منخفض عبر إجماع البادئة

1. بيان المشكلة

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

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

في كلتا الحالتين، تكون الرؤية المنتهية مهدرة، ويجب أن تنتظر الطلب عملية تغيير الرؤية وجولة القائد التالي لإتمام الإنهاء. هذه المقايضة، بدلاً من أداء "الحالة الجيدة"، هي التي تحكم زمن استجابة الذيل (tail latency) للنظام. علاوة على ذلك، غالباً ما تفصل البنى الحديثة بين نشر البيانات (مثل الـ DAGs أو التصميمات القائمة على المسارات/lanes) وبين ترتيب الإجماع. في هذه الإعدادات، تكون المقترحات عبارة عن بادئات (prefixes) لتدفق بيانات، وغالباً ما تختلف المقترحات الصادقة ضمن رؤية واحدة فقط في "اللاحقة" (suffix) بسبب اضطراب الشبكة. البروتوكولات الحالية تستبعد هذه الأصوات غير المتطابقة باعتبارها خلافات، وتفشل في الاستفادة من البادئة المشتركة التي تتشاركها.

2. المنهجية

هيرميس هو بروتوكول يدور فيه القائد (rotating-leader) يتكون من جولتين، مصمم لـ $n = 5f + 1$ من العمليات تحت ظروف التزامن الجزئي. يقدم إجماع البادئة (Prefix Consensus)، وهي آلية تحمل فيها الأصوات قيماً مرتبة حسب علاقة بادئة ( $\preceq$ )، وتتطلب النصابات (quorums) القابلية للمقارنة بدلاً من التطابق.

الآليات الجوهرية

هيكل الجولتين:
1. الجولة الأولى (الاقتراح): تقوم كل عملية ببث اقتراح مبرر. يكون اقتراح القائد (الذي يتبع نظام التدوير) واحداً من بين $n$ .
2. الجولة الثانية (التصويت): تقوم كل عملية بالإدلاء بصوت واحد.
  - إذا تم تسليم اقتراح القائد في الوقت المحدد، تصوت العمليات لصالحه.
  - إذا انقضت مهلة زمنية ( $2\Delta$ ) وتم استلام $n-f$ من الاقتراحات الصالحة، تصوت العمليات لـ اقتراح احتياطي يتم اختياره من المجموعة المتاحة.
- من المهم ملاحظة أنه لا توجد أصوات إبطال (nullify votes).
تعريفات النصاب (Quorum Definitions):
- التوثيق بـ M (M-notarization): مجموعة من $2f+1$ من الأصوات القابلة للمقارنة زوجياً. هذا يسمح للرؤية بالانتقال إلى الرؤية التالية.
- التوثيق بـ L (L-notarization): مجموعة من $n-f = 4f+1$ من الأصوات الصالحة (التي لا يجب أن تكون متطابقة). تقوم هذه المجموعة بإنهاء أثقل بادئة مشتركة (Heaviest Common Prefix - HCP) للأصوات.
التعامل مع المهلة الزمنية:
بدلاً من إبطال الرؤية عند بطء القائد، يستخدم هيرميس مسار المهلة الزمنية لإنهاء الـ HCP لـ $n-f$ من الأصوات المجموعة. المهلة الهجومية الآن لا تكلف سوى "اللاحقة" (suffix) حيث تختلف الأصوات، وليس كامل الرماية (view). يتم إنهاء الـ HCP عند $2\Delta + \delta$ .
تجسيدات فضاء القيم (Value Space Instantiations):
تم تجسيد البروتوكول فوق فضاء مجرد مرتب بالبادئة، وطُبق على سيناريوهين محددين:
1. المسار الواحد (أداة الإنهاء - Single-Lane): فوق سلسلة متاحة ديناميكياً (مثل Ethereum). القيم هي أطراف السلسلة (chain tips)؛ وعلاقة البادئة هي النسب (ancestry).
2. المسارات المتعددة (نمط Autobahn): يرتب المسارات المتزامنة للبيانات. هذا يطرح ثلاثة تحديات محددة تمت معالجتها بواسطة:
  - التداخل الحتمي (Deterministic Interleaving): ترتيب عالمي لمواقع المسارات.
  - القطع النسبي للأب (Parent-Relative Delta Tipcuts): تمثيل مدمج باستخدام معرفات الأب وعلامات تخطي صريحة للتعامل مع سرعات المسارات غير المتجانسة دون نقل القيم الكاملة.
  - التضخيم المرمز عبر خطأ المرسل (Sender-Indexed Erasure-Coded Amplification): لضمان التوافر دون تضخيم التعقيد الاتصالي إلى $O(n^3 \hat{m})$ ، يتم تضخيم المقترحات عبر أكواد التصحيح (erasure codes). تحمل التبريرات معرفات، ويتم إعادة بناء الأجزاء عند الطلب.

3. المساهمات الرئيسية

بروتوكول هيرميس: بروتوكول دوري للقائد يتكون من جولتين عند $n=5f+1$ $n = 5 f + 1$ بدون مسار إبطال.
- الحالة الجيدة: إنهاء في $2\delta$ تحت وجود قائد صادق وفي الوقت المحدد.
- الحالة السيئة: إنهاء الـ HCP لأي $n-f$ من الأصوات عند $2\Delta + \delta$ .
- السلامة والنشاط (Safety & Liveness): تم إثباتهما عبر فضاء قيم بادئة مجرد.
تجسيد المسار الواحد: أداة إنهاء للسلاسل المتاحة حيث تكون القيم هي أطراف السلسلة.
تجسيد المسارات المتعددة: تصميم لمسارات نمط Autobahn يتميز بـ:
- التداخل الحتمي.
- قطع (tipcuts) نسبي للأب مع شهادة تخطي صريحة.
- تضخيم مرمز عبر خطأ المرسل.
- التعقيد: $O(n^2 \hat{m} + \lambda n^3)$ بت و $O(n^2)$ رسائل لكل رؤية (حيث $\hat{m}$ هو عدد المسارات و $\lambda$ هو معامل الأمان).
التنفيذ والتقييم: يتضمن البحث تنفيذاً وتقييماً (القسم 8)، رغم أن النتائج الرقمية المحددة معلمة بـ "إضافة النتائج" في النص المقدم.

4. النتائج والأداء

زمن الاستجابة (Latency):
- القائد في الوقت المحدد: يتم الإنهاء في $2\delta$ .
- القائد البطيء/المتعطل: يتم إنهاء الـ HCP في $2\Delta + \delta$ . هذا يمثل تحسناً كبيراً مقارنة بالبروتوكولات التقليدية حيث يؤدي القائد البطيء إلى تغيير كامل للرؤية ودورة $2\delta$ لاحقة، مما يجعل المجموع $2\Delta + 3\delta$ أو أكثر قبل أول عملية إنهاء.
الاتصال:
- في إعداد المسارات المتعددة مع التضخيم، يتجنب البروتوكول التعقيد الرباعي ( $O(n^3 \hat{m})$ ) المرتبط بتمرير القيم الكاملة.
- تحافظ الحالة الجيدة على تعقيد رسائل قدره $O(n^2)$ . في حالات الأعطال، قد يرتفع تعقيد الرسائل إلى $O(n^3)$ بسبب حركة مرور التضخيم، لكن تعقيد البتات يظل مضبوطاً.
زمن استجابة الذيل (Tail Latency): بجعل مسار المهلة الزمنية منتجاً، يلغي هيرميس عقوبة "الرؤية الضائعة". الطلب الذي يقع في رؤية سيئة يدفع ثمن المهلة الزمنية وإنهاء الـ HCP، بدلاً من الانتظار لدورة تغيير رؤية كاملة.

5. الأهمية

يزعم البحث أن هيرميس يغير بشكل جذري المقايضة بين الاستجابة (مدى سرعة تغيير الرؤية) والاستقرار (كم عدد تغييرات الرؤية التي تحقق تقدماً).

المهل الزمنية المنتجة: على عكس التصميمات السابقة حيث تعني المهلة الزمنية رؤية باطلة، يضمن هيرميس أنه حتى الرؤية ذات القائد الفاشل تنهي بادئة مفيدة لتدفق البيانات.
التوافق مع البنى الحديثة: يسد هيرميس الفجوة بين طبقات نشر البيانات المتاحة (مثل الـ DAGs أو الأنظمة القائمة على المسارات) وبين الإجماع، مما يسمح لأداة الإنهاء بترتيب الكتل التي تم نشرها بالفعل ولكنها قد تباينت قليلاً في طبقة النشر.
المثالية (Optimality): يحقق هيرميس الحد الأدنى النظري البالغ $2\delta$ للحالة الجيدة، بينما يحل مشكلة زمن استجابة الذيل التي استمرت في أنظمة الإجماع القائمة على القائد، دون الحاجة إلى بروتوكول استرداد منفصل أو آليات سباق (racing mechanisms).

يضع البحث هيرميس كبروتوكول وحيد في فئته حيث يتم إنهاء رؤية القائد الفاشل نفسها، على عكس بروتوكولات مثل Minimmit (الذي يبطل مثل هذه الرؤى) أو Raptr (الذي يستخدم التصويت بالبادئة من أجل التوافر ولكن ضمن مقترح قائد واحد).