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

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

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

 وصف المشكلة

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

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

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

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

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

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

المقالة الرئيسية: إنهاء البث الموثوق

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

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

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

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

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

 انظر أيضاً

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

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

• 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.