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

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

وصف المشكلة

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

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

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

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

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

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

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

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

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

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

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

الإجماع

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

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

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

المصدر	التزامن	المصادقة	البداية	الدورات	ملاحظات
Pease-Shostak-Lamport	متزامن	شفهي	${\displaystyle n>3f$	${\displaystyle f+1$	total communication ${\displaystyle O(n^{f )$
Pease-Shostak-Lamport	متزامن	مكتوب	${\displaystyle n>f+1$	${\displaystyle f+1$	total communication ${\displaystyle O(n^{f )$
Ben-Or	غير متزامن	شفهي	${\displaystyle n>5f$	${\displaystyle O(2^{n )$ (expected)	expected ${\displaystyle O(1)$ rounds when ${\displaystyle f<{\sqrt {n$
Dolev et al.	متزامن	شفهي	${\displaystyle n>3f$	${\displaystyle 2f+3$	total communication ${\displaystyle O(f^{3 \log f)$
Dolev-Strong	متزامن	مكتوب	${\displaystyle n>f+1$	${\displaystyle f+1$	total communication ${\displaystyle O(n^{2 )$
Dolev-Strong	متزامن	مكتوب	${\displaystyle n>f+1$	${\displaystyle f+2$	total communication ${\displaystyle O(nf)$
Feldman-Micali	متزامن	شفهي	${\displaystyle n>3f$	${\displaystyle O(1)$ (expected)
Katz-Koo	متزامن	مكتوب	${\displaystyle n>2f$	${\displaystyle O(1)$ (expected)	Requires PKI
PBFT	غير متزامن (safety)-- Synchronous (liveness)	شفهي	${\displaystyle n>3f$
HoneyBadger	غير متزامن	شفهي	${\displaystyle n>3f$	${\displaystyle O(1)$	total communication ${\displaystyle O(n)$ - requires public-key encryption
Abraham et al.	متزامن	مكتوب	${\displaystyle n>2f$	${\displaystyle 8$
Byzantine Agreement Made Trivial	متزامن	Signatures	${\displaystyle n>3f$	${\displaystyle 9$ (expected)	Requires digital signatures

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

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

انظر أيضاً

إجماع موحد
الاتفاق البيزنطي الكمومي
مسألة الجنرال البيزنطي

المصادر

^ Coulouris, George; Jean Dollimore; Tim Kindberg (2001), Distributed Systems: Concepts and Design (3rd Edition), Addison-Wesley, p. 452, ISBN 978-0201-61918-8
^ خطأ استشهاد: وسم <ref> غير سليم؛ لا نص تم توفيره للمراجع المسماة PSL82
^ Ben-Or, Michael (1983). "Another advantage of free choice (extended abstract): Completely asynchronous agreement protocols". pp. 27–30. doi:10.1145/800221.806707.
^ 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.
^ خطأ استشهاد: وسم <ref> غير سليم؛ لا نص تم توفيره للمراجع المسماة dolev strong
^ نطقب:Cite techreport
^ (2006) "On Expected Constant-Round Protocols for Byzantine Agreement" in CRYPTO.. doi:10.1007/11818175_27.
^ (1999) "Practical Byzantine Fault Tolerance" in OSDI..
^ (2016) "The honey badger of BFT protocols" in CCS.. doi:10.1145/2976749.2978399.
^ نطقب:Cite techreport
^ Micali, Sylvio (2018). "Byzantine agreement made trivial" (PDF).

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

Herlihy, M.; Shavit, N. (1999). "The topological structure of asynchronous computability". Journal of the ACM. 46 (6): 858. CiteSeerX 10.1.1.78.1455. doi:10.1145/331524.331529.
Saks, M.; Zaharoglou, F. (2000). "Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge". SIAM Journal on Computing. 29 (5): 1449–1483. doi:10.1137/S0097539796307698.