توافق (علوم الحاسوب)
لمعانٍ أخرى، طالع توافق (توضيح).
تتمثل المشكلة الأساسية في الحوسبة الموزعة والأنظمة متعددة الوكلاء في تحقيق موثوقية النظام الشاملة رغم وجود عدد من العمليات الخاطئة. يتطلب ذلك غالبًا عمليات تنسيق لتحقيق توافق، أو اتفاق على بعض قيم البيانات المطلوبة في أثناء الحساب. تتضمن الأمثلة على تطبيقات التوافق الاتفاق على المعاملات التي يجب الالتزام بها في قاعدة بيانات بترتيب، وتكرار آلة الحالة، وبث ذري معين. تشمل تطبيقات العالم الحقيقي التي تتطلب توافقًا غالبًا الحوسبة السحابية، ومزامنة الساعة، ونظام بيج رانك، وتكوين الآراء، وشبكات الطاقة الذكية، وملاحظ الحالة، والتحكم في الطائرات بدون طيار (والعديد من الروبوتات/الوكلاء عمومًا)، وموازنة الحمل، وسلسلة الكتل وغيرها.
وصف المشكلة[عدل]
تتطلب مشكلة التوافق الاتفاق بين عدد من العمليات (أو الوكلاء) على قيمة بيانات واحدة. قد تفشل بعض العمليات (الوكلاء) أو تكون غير موثوقة في طرق أخرى، لذلك يجب أن تتحمل بروتوكولات التوافق الأخطاء أو تتصف بالمرونة. يجب أن تقدم العمليات بطريقة ما قيمها المرشحة، وتتواصل مع بعضها البعض، وتتفق على قيمة توافق واحدة.
تعد مشكلة التوافق مشكلة أساسية في السيطرة على الأنظمة متعددة الوكلاء. تتمثل إحدى طرق توليد التوافق في اتفاق جميع العمليات (الوكلاء) على القيمة الغالبة. في هذا السياق، تتطلب الغالبية ما لا يقل عن نصف الأصوات المتاحة (إذ تمنح كل عملية صوت). ولكن، قد تؤدي عملية خاطئة واحدة أو أكثر إلى تحريف النتيجة الناتجة بحيث لا يحقق توافق أو يحقق بشكل غير صحيح.
تصمم البروتوكولات التي تحل مشاكل التوافق للتعامل مع عدد محدود من العمليات الخاطئة. يجب أن تفي هذه البروتوكولات بعدد من المتطلبات لتكون مفيدة. مثلًا، يمكن أن تكون قيمة الإخراج الثنائية لبروتوكول بسيط تساوي 1 لجميع العمليات. وهذا ليس مفيدًا وبالتالي يعدل المطلب بحيث يعتمد الإخراج بطريقة ما على المدخلات. بمعنى، يجب أن تساوي قيمة مخرجات بروتوكول التوافق قيمة الإدخال في بعض العمليات. ويوجد مطلب آخر ينص على أن العملية قد تقرر قيمة المخرجات مرة واحدة فقط ويعد هذا القرار قطعي. تسمى العملية صحيحة في التنفيذ إذا لم تواجه أي فشل. ويجب أن يفي بروتوكول التوافق الذي يتحمل حالات الفشل بالخصائص التالية.[1]
الإنهاء
بالنهاية، تقرر كل عملية صحيحة بعض القيم.
التكامل
إذا اقترحت جميع العمليات الصحيحة نفس القيمة v، فيجب أن تقرر أي عملية صحيحة القيمة v.
الاتفاق
يجب أن تتفق جميع العمليات الصحيحة على نفس القيمة.
قد تكون الاختلافات في تعريف التكامل واجبة، وفقًا للتطبيق. فمثلًا، قد يشترط النوع الضعيف من التكامل أن تساوي قيمة القرار قيمة تقترحها بعض العمليات الصحيحة- وليس بالضرورة جميعها. يُعرف شرط التكامل أيضًا بالصلاحية في المنشورات.
يقال إن البروتوكول الذي يمكن أن يضمن التوافق بشكل صحيح بين n عملية يفشل منها t عملية على الأكثر، مرن بالنسبة لـt.
يوجد عاملان مهمان عند تقييم أداء بروتوكولات التوافق هما وقت التشغيل وتعقيد الرسالة. يعطى وقت التشغيل في تمثيل O الكبير في عدد دورات تبادل رسائل كدالة لبعض معلمات الإدخال (عادةً عدد العمليات و/أو حجم مجال الإدخال). يشير تعقيد الرسائل إلى مقدار حركة الرسائل التي ينشئها البروتوكول. قد تشمل العوامل الأخرى استخدام الذاكرة وحجم الرسائل.
نماذج الحساب[عدل]
قد تحدد نماذج الحساب المختلفة «مشكلة التوافق». قد تتعامل بعض النماذج مع رسوم بيانية متصلة تمامًا، بينما قد يتعامل البعض الآخر مع الحلقات والأشجار. يُسمح بمصادقة الرسائل في بعض النماذج، بينما تكون العمليات مجهولة تمامًا في نماذج أخرى. تعد نماذج الذاكرة المشتركة التي تتواصل فيها العمليات عن طريق الوصول إلى الكائنات في الذاكرة المشتركة أيضًا مجالًا مهمًا للبحث.
قنوات الاتصال ذات المصادقة المباشرة أو القابلة للتحويل[عدل]
يتواصل المشاركون في معظم نماذج بروتوكولات الاتصال عن طريق قنوات مصدقة. يعني هذا أن الرسائل غير مجهولة الهوية، وأن المستلمين يعرفون مصدر كل رسالة يتلقونها. تنفذ بعض النماذج شكلًا أقوى وقابل للتحويل من المصادقة، إذ يوقع المرسل كل رسالة، بحيث لا يعرف المستلم المصدر المباشر لكل رسالة فحسب، بل يعرف المشارك الذي أنشأ الرسالة في البداية. يحقق هذا النوع القوي من المصادقة عن طريق التوقيعات الرقمية، وعندما يتوفر هذا الشكل القوي من المصادقة، يمكن للبروتوكولات أن تتحمل عدد أكبر من الأخطاء.[2]
يدعا نموذجا المصادقة المختلفان نموذجي الاتصال الشفوي والاتصال الكتابي. في نموذج الاتصال الشفوي، يُعرف المصدر المباشر للمعلومات، بينما في نماذج الاتصال المكتوبة القوية، لا يعلم المتلقي المصدر المباشر للرسالة في كل خطوة فحسب، بل وتاريخ الاتصال للرسالة.[3]
مدخلات ومخرجات التوافق[عدل]
في معظم بروتوكولات التوافق التقليدية أحادية القيمة مثل باكسوس، تتفق العقد المتعاونة على قيمة واحدة كعدد صحيح، والتي قد تكون ذات حجم متغير لترميز البيانات الوصفية المفيدة مثل المعاملات المرتبطة بقاعدة البيانات.
تقيد حالة خاصة من مشكلة التوافق أحادية القيمة، تسمى التوافق الثنائي، الإدخال وبالتالي مجال الإخراج إلى رقم ثنائي واحد {0،1}. رغم أنها ليست مفيدة للغاية بحد ذاتها، لكن بروتوكولات التوافق الثنائية تكون غالبًا مفيدة كوحدات بناء في بروتوكولات التوافق الأكثر عمومية، خاصةً بالنسبة للتوافق غير المتزامن.
يعد الهدف في بروتوكولات التوافق متعدد القيم مثل باكسوس-المتعدد ورافت، هو الاتفاق على سلسلة من القيم بمرور الوقت ليس فقط على قيمة واحدة، وتشكيل سجل مزايد تدريجيًا. رغم أنه يمكن تحقيق توافق متعدد القيم ببساطة عن طريق تشغيل عدة تكرارات من بروتوكولات التوافق أحادية القيمة على التوالي، فإن العديد من التحسينات والاعتبارات الأخرى مثل دعم إعادة التهيئة يمكن أن تجعل بروتوكولات التوافق متعددة القيم أكثر كفاءة في الممارسة.
الأعطال والفشل البيزنطي[عدل]
يوجد نوعان من الفشل الذي قد تتعرض له العملية، فشل التعطل أو الفشل البيزنطي. يحدث فشل التعطل عندما تتوقف العملية فجأة ولا تستأنف. أما الفشل البيزنطي فهو فشل لا ينطبق عليه أي شرط مطلقًا. قد يحدث مثلًا نتيجة إجراءات الخصم الضارة. قد ترسل العملية التي تواجه فشلًا بيزنطيًا بيانات متناقضة أو متضاربة إلى عمليات أخرى، أو قد تستريح ثم تستأنف النشاط بعد تأخير طويل. يعتبر الفشل البيزنطي أكثر تخريبًا بكثير.
بالتالي، يجب أن يكون بروتوكول التوافق الذي يتحمل الإخفاقات البيزنطية متكيفًا مع كل خطأ محتمل يمكن أن يحدث.
تعطى نسخة أقوى من التوافق الذي يتحمل الفشل البيزنطي عن طريق تعزيز قيود التكامل:
التكامل
إذا قررت عملية صحيحة القيمة v، فلا بد أن v قد اقتُرحت عن طريقي عملية صحيحة.
الأنظمة غير المتزامنة والمتزامنة[عدل]
يمكن دراسة مشكلة التوافق في حالة الأنظمة غير المتزامنة أو المتزامنة. رغم أن اتصالات العالم الحقيقي تكون غالبًا غير متزامنة بطبيعتها، ولكن من العملي والأسهل غالبًا تصميم أنظمة متزامنة، لأن الأنظمة غير المتزامنة تتضمن بطبيعة الحال مشكلات أكثر من المتزامنة.[4]
في الأنظمة المتزامنة، يفترض أن تستمر جميع الاتصالات في دورات. قد ترسل العملية في دورة واحدة جميع الرسائل التي تتطلبها، بينما تتلقى جميع الرسائل من العمليات الأخرى. وبهذه الطريقة، لا يمكن لأي رسالة من دورة واحدة أن تؤثر على أي رسائل مرسلة في نفس الدورة.
المراجع[عدل]
- ^ Coulouris، George؛ Jean Dollimore؛ Tim Kindberg (2001)، Distributed Systems: Concepts and Design (3rd Edition)، Addison-Wesley، ص. 452، ISBN:978-0201-61918-8
- ^ Dolev، D.؛ Strong، H.R. (1983). "Authenticated algorithms for Byzantine agreement". SIAM Journal on Computing. ج. 12 ع. 4: 656–666. DOI:10.1137/0212045.
- ^ Gong، Li؛ Lincoln، Patrick؛ Rushby، John (1995). "Byzantine Agreement with authentication". Dependable Computing for Critical Applications. ج. 10. مؤرشف من الأصل في 2020-01-05.
- ^ Aguilera، M. K. (2010). "Stumbling over Consensus Research: Misunderstandings and Issues". Replication. Lecture Notes in Computer Science. ج. 5959. ص. 59–72. DOI:10.1007/978-3-642-11294-2_4. ISBN:978-3-642-11293-5.
