الإجماع (علوم الحاسوب)

📅 آخر تحديث: ٢١ يوليو ٢٠٢٦
✍️ نُشر في: ٢١ يوليو ٢٠٢٦
📷 يحتوي على 2 صور
الموسوعة الحرة

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

وصف المشكلة

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

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

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

إنهاء الخدمة
في النهاية، تحدد كل عملية صحيحة قيمة ما.
نزاهة
إذا اقترحت جميع العمليات الصحيحة نفس القيمةv{\displaystyle v}إذن، يجب على أي عملية صحيحة أن تقررv{\displaystyle v}.
اتفاق
يجب أن تتفق جميع العمليات الصحيحة على نفس القيمة.

قد تكون هناك اختلافات في تعريف النزاهة مناسبة، بحسب التطبيق. على سبيل المثال، يتمثل أحد أنواع النزاهة الأضعف في أن تكون قيمة القرار مساوية لقيمة اقترحتها عملية صحيحة ما - وليس بالضرورة جميعها. [ 1 ] كما يوجد في الأدبيات شرط يُعرف باسم الصلاحية ، ويشير إلى خاصية وجوب تسليم الرسالة المرسلة من عملية ما. [ 1 ]

يُقال عن البروتوكول الذي يمكنه ضمان الإجماع بشكل صحيح بين n عملية والتي لا تفشل منها أكثر من t عملية، أنه بروتوكول مرن من حيث t .

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

نماذج الحوسبة

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

قنوات اتصال مع مصادقة مباشرة أو قابلة للتحويل

في معظم نماذج بروتوكولات الاتصال، يتواصل المشاركون عبر قنوات موثقة. هذا يعني أن الرسائل ليست مجهولة المصدر، وأن المتلقين يعرفون مصدر كل رسالة يتلقونها. تفترض بعض النماذج شكلاً أقوى من التوثيق ، قابلاً للتحويل ، حيث تُوقّع كل رسالة من قِبل المرسل، بحيث يعرف المتلقي ليس فقط المصدر المباشر لكل رسالة، بل أيضاً المشارك الذي أنشأ الرسالة في الأصل. يتحقق هذا النوع الأقوى من التوثيق بواسطة التوقيعات الرقمية، وعند توفره، تستطيع البروتوكولات تحمل عدد أكبر من الأخطاء. [ 2 ]

يُطلق على نموذجي التوثيق المختلفين عادةً اسم نموذج الاتصال الشفهي ونموذج الاتصال الكتابي . في نموذج الاتصال الشفهي، يكون المصدر المباشر للمعلومات معروفًا، بينما في نماذج الاتصال الكتابي الأقوى، يتعرف المتلقي في كل خطوة ليس فقط على المصدر المباشر للرسالة، بل أيضًا على تاريخ اتصال الرسالة. [ 3 ]

مدخلات ومخرجات التوافق

في بروتوكولات الإجماع التقليدية ذات القيمة الواحدة مثل Paxos ، تتفق العقد المتعاونة على قيمة واحدة مثل عدد صحيح، والذي قد يكون ذا حجم متغير لترميز البيانات الوصفية المفيدة مثل معاملة تم الالتزام بها في قاعدة بيانات.

تُقيّد حالة خاصة من مشكلة التوافق أحادي القيمة، تُسمى التوافق الثنائي ، نطاق الإدخال، وبالتالي نطاق الإخراج، إلى رقم ثنائي واحد {0،1}. وعلى الرغم من أنها ليست مفيدة للغاية في حد ذاتها، إلا أن بروتوكولات التوافق الثنائي غالبًا ما تكون مفيدة كعناصر بناء في بروتوكولات توافق أكثر عمومية، وخاصة للتوافق غير المتزامن.

في بروتوكولات الإجماع متعددة القيم، مثل Multi-Paxos و Raft ، يكمن الهدف في الاتفاق ليس على قيمة واحدة فحسب، بل على سلسلة من القيم بمرور الوقت، لتشكيل سجل تاريخي متنامٍ تدريجيًا. ورغم إمكانية تحقيق الإجماع متعدد القيم بشكل بسيط من خلال تشغيل عدة دورات متتالية من بروتوكول إجماع أحادي القيمة، إلا أن العديد من التحسينات والاعتبارات الأخرى، مثل دعم إعادة التكوين، يمكن أن تجعل بروتوكولات الإجماع متعددة القيم أكثر كفاءة في الواقع العملي.

حوادث وفشل معقد

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

وبالتالي، يجب أن يكون بروتوكول الإجماع الذي يتحمل حالات الفشل البيزنطية مرنًا في مواجهة كل خطأ محتمل يمكن أن يحدث.

يتم تقديم نسخة أقوى من الإجماع تتسامح مع حالات الفشل البيزنطية من خلال تعزيز قيد النزاهة:

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

الأنظمة غير المتزامنة والمتزامنة

يمكن النظر في مشكلة التوافق في حالة الأنظمة غير المتزامنة أو المتزامنة. في حين أن الاتصالات في العالم الحقيقي غالباً ما تكون غير متزامنة بطبيعتها، إلا أنه من العملي والأسهل في كثير من الأحيان نمذجة الأنظمة المتزامنة، [ 4 ] نظراً لأن الأنظمة غير المتزامنة تنطوي بطبيعتها على مشاكل أكثر من الأنظمة المتزامنة.

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

نتيجة استحالة FLP للتوافق الحتمي غير المتزامن

في نظام موزّع يعتمد على تمرير الرسائل غير المتزامن بالكامل، حيث قد تتعرض عملية واحدة على الأقل لعطل مفاجئ ، فقد ثبت في نتيجة استحالة FLP الشهيرة لعام 1985 التي توصل إليها فيشر ولينش وباترسون أن الخوارزمية الحتمية لتحقيق الإجماع مستحيلة. [ 5 ]

في النموذج غير المتزامن، يمكن معالجة بعض أنواع الأعطال بواسطة بروتوكول توافق متزامن. على سبيل المثال، يمكن نمذجة فقدان رابط الاتصال كعملية تعرضت لعطل بيزنطي.

يمكن لخوارزميات الإجماع العشوائية تجاوز نتيجة استحالة FLP من خلال تحقيق كل من السلامة والحيوية باحتمالية كبيرة، حتى في أسوأ سيناريوهات الجدولة مثل وجود مهاجم ذكي لحجب الخدمة في الشبكة. [ 6 ]

الإجماع المصرح به مقابل الإجماع غير المصرح به

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

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

مشاكل تكافؤ الاتفاق

فيما يلي ثلاث مسائل اتفاق ذات أهمية.

إنهاء البث الموثوق

تتواصل مجموعة من n عملية، مرقمة من 0 إلى n − 1 ، عن طريق إرسال رسائل فيما بينها. يجب على العملية 0 إرسال قيمة v إلى جميع العمليات بحيث:

  1. إذا كانت العملية 0 صحيحة، فإن كل عملية صحيحة تتلقى v
  2. بالنسبة لأي عمليتين صحيحتين، تحصل كل عملية على نفس القيمة.

وتُعرف أيضاً باسم مشكلة الجنرال.

إجماع

قد تتضمن المتطلبات الرسمية لبروتوكول التوافق ما يلي:

  • الاتفاق : يجب أن تتفق جميع العمليات الصحيحة على نفس القيمة.
  • الصلاحية الضعيفة : لكل عملية صحيحة، يجب أن يكون ناتجها مدخلاً لعملية صحيحة أخرى.
  • الصلاحية القوية : إذا تلقت جميع العمليات الصحيحة نفس قيمة الإدخال، فيجب أن تُخرج جميعها تلك القيمة.
  • الإنهاء : يجب على جميع العمليات في النهاية أن تقرر قيمة الإخراج.

اتساق تفاعلي ضعيف

بالنسبة لعدد n من العمليات في نظام متزامن جزئيًا (يتناوب النظام بين فترات تزامن جيدة وأخرى سيئة)، تختار كل عملية قيمة خاصة. تتواصل العمليات فيما بينها عبر جولات لتحديد قيمة عامة وتوليد متجه توافق وفقًا للمتطلبات التالية: [ 7 ]

  1. إذا أرسلت عملية صحيحة v ، فإن جميع العمليات الصحيحة تتلقى إما v أو لا شيء (خاصية التكامل).
  2. يتم استلام جميع الرسائل المرسلة في جولة واحدة بواسطة عملية صحيحة في نفس الجولة بواسطة جميع العمليات الصحيحة (خاصية الاتساق).

يمكن إثبات أن تنويعات هذه المشكلات متكافئة، بمعنى أن حل مشكلة في نوع معين من النماذج قد يكون حلاً لمشكلة أخرى في نوع آخر. على سبيل المثال، يؤدي حل مشكلة بيزنطة العامة الضعيفة في نموذج تمرير الرسائل المتزامن والموثق إلى حل لمشكلة الاتساق التفاعلي الضعيف. [ 8 ] يمكن لخوارزمية الاتساق التفاعلي حل مشكلة التوافق من خلال جعل كل عملية تختار القيمة الأكثر شيوعًا في متجه التوافق الخاص بها كقيمة توافقها. [ 9 ]

نتائج قابلية الحل لبعض مسائل التوافق

يوجد بروتوكول متزامن مجهول الهوية مقاوم لـ t يحل مشكلة الجنرالات البيزنطيين ، [ 10 ] [ 11 ] إذا كان t / n < 1 / 3 وحالة الجنرالات البيزنطيين الضعفاء [ 8 ] حيث t هو عدد حالات الفشل و n هو عدد العمليات.

بالنسبة للأنظمة التي تحتوي على n معالجًا، منها f معالجات بيزنطية، فقد ثبت أنه لا توجد خوارزمية تحل مشكلة التوافق لـ n ≤ 3f في نموذج الرسائل الشفوية . [ 12 ] ويُبنى البرهان أولًا على إثبات استحالة ذلك في حالة العقد الثلاث n = 3 ، ثم استخدام هذه النتيجة للنقاش حول تقسيمات المعالجات. أما في نموذج الرسائل المكتوبة، فتوجد بروتوكولات يمكنها تحمل n = f + 1. [ 2 ]

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

بعض بروتوكولات الإجماع

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

تم تطوير بروتوكولات أخرى، مثل سيربيروس، لتطبيق إجماع متسامح مع الأخطاء البيزنطية على السجلات الموزعة المجزأة، وقد كانت موضوعًا للتحليل الأكاديمي. [ 14 ]

من الأمثلة على بروتوكولات التوافق الثنائي ذات الوقت متعدد الحدود والتي تتحمل أخطاء بيزنطية خوارزمية "ملك المرحلة" لغاراي وبيرمان. [ 15 ] تحل هذه الخوارزمية مشكلة التوافق في نموذج تمرير الرسائل المتزامن مع n عملية وما يصل إلى f من الأخطاء، بشرط أن يكون n > 4f . في خوارزمية "ملك المرحلة"، توجد f + 1 مرحلة، تتكون كل مرحلة من جولتين. تحتفظ كل عملية بسجل لمخرجاتها المفضلة (والتي تساوي مبدئيًا قيمة مدخلاتها). في الجولة الأولى من كل مرحلة، تبث كل عملية قيمتها المفضلة إلى جميع العمليات الأخرى. ثم تستقبل القيم من جميع العمليات وتحدد القيمة الأكثر شيوعًا وعدد مرات حدوثها. في الجولة الثانية من المرحلة، تُعيّن العملية التي يتطابق معرّفها مع رقم المرحلة الحالية ملكًا لتلك المرحلة. يبث الملك القيمة الأكثر شيوعًا التي لاحظها في الجولة الأولى ويُستخدم لحسم التعادل. بعد ذلك، تُحدّث كل عملية قيمتها المفضلة على النحو التالي. إذا كان عدد القيم الأكثر شيوعًا التي رصدتها العملية في الجولة الأولى أكبر من n / 2 + f ، فإن العملية تُغيّر تفضيلها إلى تلك القيمة الأكثر شيوعًا؛ وإلا فإنها تستخدم قيمة ملك المرحلة. في نهاية f + 1 مرحلة ، تُخرج العمليات قيمها المُفضّلة.

طوّرت جوجل مكتبة خدمة تأمين موزعة تُسمى تشابي . [ 16 ] تحتفظ تشابي بمعلومات التأمين في ملفات صغيرة تُخزّن في قاعدة بيانات مُكرّرة لتحقيق توافر عالٍ في حال حدوث أعطال. تُنفّذ قاعدة البيانات فوق طبقة سجلات مقاومة للأعطال تعتمد على خوارزمية باكسوس للتوافق . في هذا النظام، تتواصل عملاء تشابي مع خادم باكسوس الرئيسي للوصول إلى السجل المُكرّر وتحديثه؛ أي قراءة الملفات وكتابتها. [ 17 ]

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

هناك نهج آخر معروف يسمى خوارزميات من نوع MSR، والتي تم استخدامها على نطاق واسع في مجالات تتراوح من علوم الحاسوب إلى نظرية التحكم . [ 18 ] [ 19 ] [ 20 ]

مصدرالتزامنالمصادقةعتبةجولاتملحوظات
بيز-شوستاك-لامبورت [ 10 ]متزامنشفوين > 3 وf + 1إجمالي الاتصالات O ( n f )
بيز-شوستاك-لامبورت [ 10 ]متزامنمكتوبن > ف + 1f + 1إجمالي الاتصالات O ( n f )
بن أور [ 21 ]غير متزامنشفوين > 5 وO (2 n ) (متوقع)من المتوقع O (1) جولة عندماو<ن{\displaystyle f<{\sqrt {n}}}
سيربيروس [ 22 ]متزامن جزئياًمكتوبن > 3 ومتعدد الأجزاء؛ مزامنة مضفرة
دوليف وآخرون [ 23 ]متزامنشفوين > 3 و2 f + 3إجمالي الاتصال O ( f 3 log f )
دوليف-سترونج [ 2 ]متزامنمكتوبن > ف + 1f + 1إجمالي الاتصال O ( n 2 )
دوليف-سترونج [ 2 ]متزامنمكتوبن > ف + 1f + 2إجمالي الاتصالات O ( n f )
فيلدمان-ميكالي [ 24 ]متزامنشفوين > 3 وO (1) (متوقع)
كاتز-كو [ 25 ]متزامنمكتوبن > 2 وO (1) (متوقع)يتطلب بنية المفاتيح العامة (PKI)
PBFT [ 26 ]غير متزامن  (للسلامة) متزامن  (للحيوية)شفوين > 3 و
غرير العسل [ 27 ]غير متزامنشفوين > 3 وO (log n ) (متوقع)الاتصال لكل عملية إرسال O ( n ) - يتطلب تشفير المفتاح العام
أبراهام وآخرون [ 28 ]متزامنمكتوبن > 2 و8
الاتفاق البيزنطي أصبح تافهاً [ 29 ] [ 30 ]متزامنالتوقيعاتن > 3 و9 (متوقع)يتطلب توقيعات رقمية
لوخر [ 31 ]متزامنالتوقيعاتن > 4 و6 (متوقع)يتطلب توقيعات رقمية

بروتوكولات الإجماع بدون إذن

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

تستخدم العملات المشفرة الأخرى (مثل إيثيريوم ، ونيو، وستراتيس، وغيرها) آلية إثبات الحصة ، حيث تتنافس العُقد لإضافة كتل جديدة وكسب مكافآت تتناسب مع قيمة الحصة ، أي العملات المشفرة الموجودة والمخصصة والمُودعة لفترة زمنية محددة. من مزايا آلية إثبات الحصة مقارنةً بآلية إثبات العمل، استهلاكها العالي للطاقة. فعلى سبيل المثال، تشير التقديرات إلى أن تعدين البيتكوين (عام 2018) يستهلك من مصادر الطاقة غير المتجددة كميةً تُعادل استهلاك دولتي جمهورية التشيك أو الأردن، بينما يبلغ إجمالي استهلاك الطاقة لإيثيريوم، أكبر شبكة إثبات حصة، أقل بقليل من استهلاك 205 أسر أمريكية متوسطة. [ 32 ] [ 33 ] [ 34 ]

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

الخطوة 1: يقوم كل خادم بتجميع قائمة بالمعاملات المرشحة الصالحة؛
الخطوة 2: يقوم كل خادم بدمج جميع المرشحين القادمين من قائمة العقد الفريدة (UNL) الخاصة به ويصوت على صحتهم؛
الخطوة 3: يتم تمرير المعاملات التي تتجاوز الحد الأدنى إلى الجولة التالية؛
الخطوة الرابعة: تتطلب الجولة النهائية موافقة 80%. [ 35 ]

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

على النقيض من قواعد المشاركة غير المصرح بها المذكورة أعلاه، والتي تكافئ المشاركين بما يتناسب مع حجم استثمارهم في إجراء أو مورد معين، تهدف بروتوكولات إثبات الشخصية إلى منح كل مشارك بشري حقيقي وحدة واحدة بالضبط من قوة التصويت في الإجماع غير المصرح به، بغض النظر عن الاستثمار الاقتصادي. [ 36 ] [ 37 ] تشمل الأساليب المقترحة لتحقيق توزيع قوة الإجماع بنسبة 1 لكل شخص لإثبات الشخصية: أحزابًا مادية بأسماء مستعارة، [ 38 ] وشبكات التواصل الاجتماعي، [ 39 ] وهويات حكومية مجهولة الهوية، [ 40 ] والبيانات البيومترية. [ 41 ]

رقم الإجماع

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

يُعرَّف عدد الإجماع لكائن متزامن بأنه الحد الأقصى لعدد العمليات في النظام التي يمكن أن تصل إلى إجماع بواسطة هذا الكائن في تطبيق خالٍ من الانتظار. [ 42 ] يمكن للكائنات ذات عدد الإجماع n تنفيذ أي كائن ذي عدد إجماع n أو أقل، ولكن لا يمكنها تنفيذ أي كائنات ذات عدد إجماع أعلى. تُشكِّل أعداد الإجماع ما يُسمى بتسلسل هيرليهي الهرمي لكائنات التزامن . [ 43 ]

رقم الإجماعأشياء
1سجلات القراءة/الكتابة الذرية ، mutex
2اختبار وتعيين ، تبديل ، جلب وإضافة ، قائمة انتظار أو مكدس بدون انتظار
⋮⋮
2 ن − 2تعيين السجل n
⋮⋮
∞مقارنة وتبديل ، تحميل/ربط مشروط/تخزين مشروط ، [ 44 ] نقل وتبديل من ذاكرة إلى ذاكرة، قائمة انتظار مع عملية معاينة، جلب وربط، بايت ثابت

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

انظر أيضاً

مراجع

  1. 1 2 3 كولوريس، جورج؛ دوليمور، جين؛ كيندبيرج، تيم (2001). الأنظمة الموزعة: المفاهيم والتصميم (  الطبعة الثالثة). أديسون-ويسلي. ص  452. ISBN 978-0201-61918-8.
  2. 1 2 3 4 دوليف، د.؛ سترونج، إتش آر (1983). "خوارزميات موثقة للاتفاق البيزنطي". مجلة SIAM للحوسبة . 12 (4): 656-666 . doi : 10.1137/0212045 .
  3. ↑ غونغ، لي؛ لينكولن ، باتريك؛ راشبي، جون (1995). "اتفاقية بيزنطية مع المصادقة" . الحوسبة الموثوقة للتطبيقات الحرجة . 10. مؤرشف من الأصل في 2020-01-05 . تم الاسترجاع في 2019-05-28 .
  4. ↑ أغيليرا، إم كيه (2010). "التعثر في أبحاث الإجماع: سوء الفهم والقضايا". التكرار . سلسلة محاضرات في علوم الحاسوب. المجلد 5959. الصفحات 59-72 . doi : 10.1007/978-3-642-11294-2_4 . ISBN   978-3-642-11293-5.
  5. 1 2 فيشر، إم جيه ؛ لينش، إن إيه ؛ باترسون، إم إس (1985). "استحالة التوافق الموزع مع وجود عملية معيبة واحدة" ( ملف PDF) . مجلة ACM . 32 (2): 374-382 . doi : 10.1145/3149.214121 . S2CID 207660233. مؤرشف (ملف PDF) من الأصل بتاريخ 30 يناير 2023. تم الاطلاع عليه بتاريخ 13 نوفمبر 2017 . 
  6. ↑ أسبنيس، جيمس (مايو 1993). "توافق عشوائي فعال من حيث الوقت والمساحة" . مجلة الخوارزميات . 14 (3): 414-431 . doi : 10.1006/jagm.1993.1022 . مؤرشف من الأصل بتاريخ 16 فبراير 2023. تم الاطلاع عليه بتاريخ 28 أكتوبر 2020 .
  7. ↑ ميلوسيفيتش، زاركو؛ مارتن هوتل؛ أندريه شيبر (2009). "توحيد خوارزميات الإجماع البيزنطية مع الاتساق التفاعلي الضعيف" . مبادئ الأنظمة الموزعة . سلسلة محاضرات في علوم الحاسوب. المجلد 5293. الصفحات 300-314 . CiteSeerX 10.1.1.180.4229 . doi : 10.1007/978-3-642-10877-8_24 . ISBN    978-3-642-10876-1.
  8. 1 2 لامبورت، ل. (1983). "مشكلة الجنرالات البيزنطيين الضعفاء" . مجلة ACM . 30 (3): 668. doi : 10.1145/2402.322398 . S2CID 1574706 . 
  9. ↑ فيشر، مايكل ج. "مشكلة الإجماع في الأنظمة الموزعة غير الموثوقة (دراسة موجزة)" (ملف PDF) . مؤرشف من الأصل (ملف PDF) بتاريخ 22 أبريل 2014. تم الاطلاع عليه بتاريخ 21 أبريل 2014 .
  10. 1 2 3 لامبورت، ل .؛ شوستاك، ر.؛ بيس، م. (1982). "مشكلة الجنرالات البيزنطيين" (ملف PDF) . معاملات ACM في لغات البرمجة والأنظمة . 4 (3): 382-401 . CiteSeerX 10.1.1.64.2312 . doi : 10.1145/357172.357176 . S2CID 55899582. مؤرشف (PDF) من الأصل في 2017-02-07 . تم الاسترجاع في 2015-08-29 .  
  11. ↑ لامبورت، ليزلي؛ مارشال بيس؛ روبرت شوستاك (أبريل 1980). "التوصل إلى اتفاق في ظل وجود أعطال" (ملف PDF) . مجلة ACM . 27 ( 2): 228-234 . CiteSeerX 10.1.1.68.4044 . doi : 10.1145/322186.322188 . S2CID 6429068. مؤرشف (PDF) من الأصل بتاريخ 28 يناير 2007. تم الاطلاع عليه بتاريخ 25 يوليو 2007 .  
  12. ^ عطية، حجيت (2004). الحوسبة الموزعة (الطبعة الثانية ). وايلي. ص 101 – 103. ISBN   978-0-471-45324-6.
  13. ↑ بيسبينغ، بنيامين؛ وآخرون (2016)، "التحقق الآلي من برهان بنائي لـ FLP"، في بلانشيت، ياسمين كريستيان؛ ميرز، ستيفان (محرران)، إثبات النظريات التفاعلي ، سلسلة محاضرات في علوم الحاسوب، المجلد 9807، دار نشر سبرينغر الدولية، الصفحات 107-122 ، doi : 10.1007/978-3-319-43144-4_7 ، ISBN    978-3-319-43144-4
  14. ↑ جلالزاي، محمد؛ جينسر، أ. إركومنت؛ كاتسيبولاكيس، مانوس؛ فوجلز، فيرنر؛ جيسنر، جريجوري. كابريتسوس، مانوس (2023). "سيربيروس: بروتوكول الإجماع الجذري" . سجل سيجمود . 52 (4): 58-65 . دوى : 10.5070/SR33161345 .
  15. ↑ بيرمان، بيوتر؛ غاراي، خوان أ. (1993). "أصوات الإغلاق: توافق موزع مرن بنسبة n/4 في t + 1 جولة". نظرية أنظمة الحوسبة . 2. 26 : 3-19 . doi : 10.1007/BF01187072 . S2CID 6102847 . 
  16. ↑ بوروز، م. (2006). خدمة قفل تشابي للأنظمة الموزعة ذات الترابط الضعيف (ملف PDF) . وقائع الندوة السابعة حول تصميم وتنفيذ أنظمة التشغيل. جمعية USENIX، بيركلي، كاليفورنيا، الولايات المتحدة الأمريكية. الصفحات 335-350 . مؤرشف (ملف PDF) من الأصل بتاريخ 14 ديسمبر 2009. تم الاطلاع عليه بتاريخ 28 أكتوبر 2014 . 
  17. ↑ توشار، سي.؛ غريسمر، ر.؛ ريدستون، ج. (2007). باكسوس ميد لايف - منظور هندسي (ملف PDF) . وقائع الندوة السنوية السادسة والعشرين لجمعية ACM حول مبادئ الحوسبة الموزعة . بورتلاند، أوريغون، الولايات المتحدة الأمريكية: مطبعة ACM، نيويورك، نيويورك، الولايات المتحدة الأمريكية. الصفحات 398-407 . doi : 10.1145/1281100.1281103 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 12 ديسمبر 2014. تم الاطلاع عليه بتاريخ 6 فبراير 2008 . 
  18. ↑ ليبلانك، هيث ج. (أبريل 2013). "التوافق التقاربي المرن في الشبكات القوية". مجلة IEEE للمجالات المختارة في الاتصالات . 31 (4): 766-781 . Bibcode : 2013IJSAC..31..766L . CiteSeerX 10.1.1.310.5354 . doi : 10.1109/JSAC.2013.130413 . S2CID 11287513 .  
  19. ↑ ديباجي، إس إم (مايو 2015). "توافق أنظمة متعددة العوامل من الدرجة الثانية في وجود أعطال محدودة محليًا". رسائل الأنظمة والتحكم . 79 : 23-29 . doi : 10.1016/j.sysconle.2015.02.005 .
  20. ↑ ديباجي، إس إم (يوليو 2017). "التوافق المرن لشبكات الوكلاء من الدرجة الثانية: قواعد التحديث غير المتزامنة مع التأخيرات". أوتوماتيكا . 81 : 123-132 . arXiv : 1701.03430 . Bibcode : 2017arXiv170103430M . doi : 10.1016/j.automatica.2017.03.008 . S2CID 7467466 . 
  21. ↑ بن أور، مايكل (1983). "ميزة أخرى للاختيار الحر (ملخص موسع): بروتوكولات اتفاق غير متزامنة تمامًا". وقائع الندوة السنوية الثانية لجمعية الحوسبة الآلية حول مبادئ الحوسبة الموزعة . الصفحات 27-30 . doi : 10.1145/800221.806707 . S2CID 38215511 .  
  22. ↑ هيلينغز، جيلي؛ سادوغي، محمد (2023). "سيربيروس: معالجة معاملات بسيطة متعددة الأجزاء مقاومة للهجمات البيزنطية" . مجلة أبحاث النظم . 3 (1). doi : 10.5070/SP24360340 (غير نشط في 10 يناير 2026).{{cite journal}}: صيانة CS1: تم تعطيل DOI اعتبارًا من يناير 2026 ( رابط )
  23. ↑ دوليف، داني؛ فيشر، مايكل جيه؛ فاولر، روب؛ لينش، نانسي؛ سترونغ، إتش. ريموند (1982). "خوارزمية فعالة للاتفاق البيزنطي بدون مصادقة" . المعلومات والتحكم . 52 (3): 257-274 . doi : 10.1016/S0019-9958(82)90776-8 .
  24. ↑ فيلدمان، بيسيتش؛ ميكالي، سيلفيو (1997). "بروتوكول احتمالي أمثل للاتفاق البيزنطي المتزامن". مجلة SIAM للحوسبة . 26 (4): 873-933 . doi : 10.1137/S0097539790187084 .
  25. ↑ كاتز، جوناثان؛ كو، تشيو-يوين (2006). "حول بروتوكولات الجولات الثابتة المتوقعة للاتفاق البيزنطي". التطورات في علم التشفير - CRYPTO 2006. سلسلة محاضرات في علوم الحاسوب. المجلد 4117. الصفحات 445-462 . doi : 10.1007/11818175_27 . ISBN   978-3-540-37432-9.
  26. ↑ كاسترو، ميغيل؛ ليسكوف، باربرا (1999). "التسامح العملي مع الأخطاء البيزنطية" (ملف PDF) . وقائع الندوة الثالثة حول تصميم وتنفيذ أنظمة التشغيل، نيو أورليانز، الولايات المتحدة الأمريكية، فبراير 1999. مؤرشف ( ملف PDF) من الأصل بتاريخ 4 مارس 2018. تم الاطلاع عليه بتاريخ 28 مايو 2019 .
  27. ↑ ميلر، أندرو؛ شيا، يو؛ كرومان، كايل؛ شي، إيلين ؛ سونغ، دون (أكتوبر 2016). "غرير العسل في بروتوكولات BFT" (ملف PDF) . وقائع مؤتمر ACM SIGSAC لأمن الحاسوب والاتصالات لعام 2016 (CCS '16) . الصفحات 31-42 . doi : 10.1145/2976749.2978399 . مؤرشف (PDF) من الأصل بتاريخ 3 يونيو 2023. تاريخ الاسترجاع: 4 يوليو 2023 . 
  28. ↑ أبراهام، إيتاي؛ ديفاداس، سرينيفاس؛ دوليف، داني؛ ناياك، كارتيك؛ رين، لينغ (11 سبتمبر 2017). "توافق بيزنطي متزامن فعال" (ملف PDF) . أرشيف الطباعة الإلكترونية لعلم التشفير . ورقة بحثية رقم 2017/307. مؤرشفة (ملف PDF) من الأصل في 4 يوليو 2023. تم الاطلاع عليها في 4 يوليو 2023 .
  29. ↑ ميكالي، سيلفيو (19 مارس 2018). "الاتفاق البيزنطي أصبح تافهاً" (ملف PDF) . كامبريدج، ماساتشوستس: مختبر علوم الحاسوب والذكاء الاصطناعي، معهد ماساتشوستس للتكنولوجيا. مؤرشف (ملف PDF) من الأصل في 7 ديسمبر 2022. تم الاطلاع عليه في 28 مايو 2019 .
  30. ^ تشين ، جينغ. ميكالي، سيلفيو (2016). "الجوراند". أرخايف : 1607.01341v9 [ cs.CR ].
  31. ↑ لوخر، توماس (2020). "اتفاقية بيزنطية سريعة لسجلات موزعة مُرخّصة". وقائع الندوة الثانية والثلاثين لجمعية آلات الحوسبة حول التوازي في الخوارزميات والهياكل . SPAA '20. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 371-382 . doi : 10.1145/3350755.3400219 . 
  32. ↑ عرفان، عمير (18 يونيو 2019). "البيتكوين يستهلك طاقة هائلة. من أين تأتي كل هذه الكهرباء؟" . فوكس . مؤرشف من الأصل في 16 فبراير 2023. تم الاطلاع عليه في 28 أغسطس 2019 .
  33. ↑ "الاندماج - الآثار المترتبة على استهلاك الكهرباء والبصمة الكربونية لشبكة إيثيريوم" . 7 سبتمبر 2022. مؤرشف من الأصل في 5 سبتمبر 2023. تم الاطلاع عليه في 5 سبتمبر 2023 .
  34. ↑ "استهلاك الكهرباء للفرد في جميع أنحاء العالم عام 2022، حسب البلدان المختارة" . ستاتيستا . مؤرشف من الأصل بتاريخ 5 سبتمبر 2023. تم الاطلاع عليه بتاريخ 5 سبتمبر 2023 .
  35. ↑ شوارتز، ديفيد؛ يونغز، نوح؛ بريتو، آرثر (2014). "خوارزمية إجماع بروتوكول ريبل" (ملف PDF) . مختبرات ريبل (مسودة). مؤرشفة (ملف PDF) من الأصل بتاريخ 29 أغسطس 2017. تم الاطلاع عليها بتاريخ 3 يوليو 2023 .
  36. ↑ بورج، ماريا؛ كوكوريس-كوجياس، إليفثيريوس؛ يوفانوفيتش، فيليب؛ جاسر، لينوس؛ جايلي، نيكولاس؛ فورد، برايان (2017). "إثبات الشخصية: إعادة إضفاء الطابع الديمقراطي على العملات المشفرة غير المرخصة". ورش عمل ندوة IEEE الأوروبية للأمن والخصوصية لعام 2017 (EuroS&PW) . الصفحات 23-26 . doi : 10.1109/EuroSPW.2017.46 . ISBN  978-1-5386-2244-5.
  37. ↑ سيدهارث، ديفيا؛ إيفليف، سيرجي؛ سيري، سانتياغو؛ بيرمان، باولا (13 أكتوبر 2020). "من يراقب المراقبين؟ مراجعة للمناهج الذاتية لمقاومة سيبيل في بروتوكولات إثبات الشخصية". arXiv : 2008.05300 [ cs.CR ].
  38. ↑ فورد، برايان؛ شتراوس، جاكوب (أبريل 2008). أساس غير متصل بالإنترنت للأسماء المستعارة المسؤولة على الإنترنت . ورشة العمل الأولى حول أنظمة الشبكات الاجتماعية - SocialNets '08 . الصفحات 31-36 . doi : 10.1145/1435497.1435503 . ISBN  978-1-60558-124-8تم الاطلاع عليه بتاريخ 28-10-2020 .
  39. ↑ شاهف، غال؛ شابيرو، إيهود؛ تالمون، نمرود (أكتوبر 2020). "معرفات شخصية حقيقية وضمانات متبادلة لنمو مجتمعي مقاوم لهجمات سيبيل" . المعلوماتية الاجتماعية . سلسلة محاضرات في علوم الحاسوب. المجلد 12467. الصفحات 320-332 . arXiv : 1904.09630 . doi : 10.1007/978-3-030-60975-7_24 . ISBN   978-3-030-60974-0.
  40. ↑ مارام، ديباك؛ مالفاي، هارجاسلين؛ تشانغ، فان؛ جان لويس، نيرلا؛ فرولوف، ألكسندر؛ كيل، تايلر؛ لوبان، تايرون؛ موي، كريستين؛ جولز، آري؛ ميلر، أندرو (28 سبتمبر 2020). "CanDID: هوية لامركزية فعّالة مع توافق مع الأنظمة القديمة، ومقاومة للهجمات الإلكترونية، ومساءلة" (ملف PDF) . مؤرشف (PDF) من النسخة الأصلية في 9 أكتوبر 2022. تم الاطلاع عليه في 28 أكتوبر 2020 .
  41. ^ حاجي خاني، محمد جواد. جهانارا، محمد مهدي (20 يونيو 2018). “المعرف الفريد: إثبات لامركزي للإنسان الفريد”. أرخايف : 1806.07583 [ cs.CR ].
  42. 1 2 هيرليهي، موريس (يناير 1991). "المزامنة بدون انتظار" ( ملف PDF) . معاملات ACM في لغات البرمجة والأنظمة . 11 (1): 124-149 . doi : 10.1145/114005.102808 . S2CID 2181446. مؤرشف (ملف PDF) من الأصل في 5 يونيو 2011. تم الاسترجاع في 19 ديسمبر 2011 . 
  43. ↑ إمبس، داميان؛ راينال، ميشيل (25 يوليو 2010). "القوة المضاعفة لأعداد الإجماع" (ملف PDF) . وقائع الندوة التاسعة والعشرين لجمعية ACM SIGACT-SIGOPS حول مبادئ الحوسبة الموزعة . جمعية آلات الحوسبة. الصفحات 26-35 . doi : 10.1145/1835698.1835705 . ISBN  978-1-60558-888-9S2CID 3179361. مؤرشف ( PDF) من الأصل بتاريخ 27 يناير 2022. تم الاطلاع عليه بتاريخ 22 أبريل 2021 . 
  44. ↑ فيش، فيث؛ هندلر، داني؛ شافيت، نير (25 يوليو 2004). "حول الضعف المتأصل في بدائيات التزامن الشرطي". وقائع الندوة السنوية الثالثة والعشرين لجمعية آلات الحوسبة حول مبادئ الحوسبة الموزعة . جمعية آلات الحوسبة. الصفحات 80-87 . CiteSeerX 10.1.1.96.9340 . doi : 10.1145/1011767.1011780 . ISBN   1-58113-802-4. S2CID 9313205 . 

للمزيد من القراءة

  • هيرليهي، م.؛ شافيت، ن. (1999). "البنية الطوبولوجية للحوسبة غير المتزامنة". مجلة ACM . 46 (6): 858. CiteSeerX 10.1.1.78.1455 . doi : 10.1145/331524.331529 . S2CID 5797174 .  
  • ساكس، م.؛ زهاروغلو، ف. (2000). "استحالة الاتفاق على مجموعة k بدون انتظار: طوبولوجيا المعرفة العامة". مجلة SIAM للحوسبة . 29 (5): 1449-1483 . doi : 10.1137/S0097539796307698 .
  • بشير، عمران. "إجماع البلوك تشين". إجماع البلوك تشين - مقدمة لبروتوكولات الإجماع الكلاسيكية، وبروتوكولات البلوك تشين، وبروتوكولات الإجماع الكمي . ISBN 978-1-4842-8178-9Apress، بيركلي، كاليفورنيا، 2022. دوى : 10.1007/978-1-4842-8179-6