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

(تم التحويل من Consensus (computer science))

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


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

وصف المشكلة

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

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





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

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


قنوات الاتصال المعتمدة

الإجماع الثنائي

فشل التحطم والفشل البيزني

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

النتيجة المستجيلة

معادلة مشكلات الاتفاق

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


الإجماع

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

النتائج القابلة للحل لبعض مشكلات الاتفاق

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

المصدر التزامن المصادقة البداية الدورات ملاحظات
Pease-Shostak-Lamport [2] متزامن شفهي total communication
Pease-Shostak-Lamport [2] متزامن مكتوب total communication
Ben-Or [3] غير متزامن شفهي (expected) expected rounds when
Dolev et al. [4] متزامن شفهي total communication
Dolev-Strong [5] متزامن مكتوب total communication
Dolev-Strong [5] متزامن مكتوب total communication
Feldman-Micali [6] متزامن شفهي (expected)
Katz-Koo [7] متزامن مكتوب (expected) Requires PKI
PBFT [8] غير متزامن (safety)-- Synchronous (liveness) شفهي
HoneyBadger [9] غير متزامن شفهي total communication - requires public-key encryption
Abraham et al. [10] متزامن مكتوب
Byzantine Agreement Made Trivial [11] متزامن Signatures (expected) Requires digital signatures

في أنظمة الذاكرة المشتركة

رقم الإجماع Objects
Read/write registers
test&set, swap, fetch&add, queue, stack
... ...
n-register assignment
... ...
Memory-to-memory move and swap, augmented queue, compare&swap, fetch&cons, sticky byte


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

انظر أيضاً

المصادر

  1. ^ أ ب ت Coulouris, George; Jean Dollimore; Tim Kindberg (2001), Distributed Systems: Concepts and Design (3rd Edition), Addison-Wesley, p. 452, ISBN 978-0201-61918-8 
  2. ^ أ ب خطأ استشهاد: وسم <ref> غير صحيح؛ لا نص تم توفيره للمراجع المسماة PSL82
  3. ^ Ben-Or, Michael (1983). "Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols". pp. 27–30. doi:10.1145/800221.806707. {{cite news}}: Unknown parameter |booktitle= ignored (help)
  4. ^ Dolev, Danny; Fisher, Michael J.; Fowler, Rob; Lynch, Nancy; Strong, H. Raymond (1982). "An Efficient Algorithm for Byzantine Agreement without Authentication". Information and Control. doi:10.1016/S0019-9958(82)90776-8.
  5. ^ أ ب خطأ استشهاد: وسم <ref> غير صحيح؛ لا نص تم توفيره للمراجع المسماة dolev strong
  6. ^ قالب:Cite techreport
  7. ^ (2006) "On Expected Constant-Round Protocols for Byzantine Agreement" in CRYPTO.. doi:10.1007/11818175_27. 
  8. ^ (1999) "Practical Byzantine Fault Tolerance" in OSDI.. 
  9. ^ (2016) "The honey badger of BFT protocols" in CCS.. doi:10.1145/2976749.2978399. 
  10. ^ قالب:Cite techreport
  11. ^ Micali, Sylvio (2018). "Byzantine agreement made trivial" (PDF).

قراءات إضافية

الكلمات الدالة: