خوارزمية التنمر

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

في الحوسبة الموزعة ، تُعدّ خوارزمية "المتنمر" طريقةً لاختيار منسق أو قائد بشكل ديناميكي من بين مجموعة من عمليات الحاسوب الموزعة. ويتم اختيار العملية التي تحمل أعلى رقم تعريف من بين العمليات غير الفاشلة لتكون المنسق.

الافتراضات

تفترض الخوارزمية ما يلي: [ 1 ]

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

الخوارزمية

تستخدم الخوارزمية أنواع الرسائل التالية:

  • رسالة انتخابية: تم إرسالها للإعلان عن الانتخابات.
  • رسالة الرد (على قيد الحياة): يرد على رسالة الانتخابات.
  • رسالة المنسق (النصر): تُرسل من قبل الفائز في الانتخابات لإعلان النصر.

عندما تتعافى عملية P من الفشل، أو عندما يشير كاشف الفشل إلى فشل المنسق الحالي، فإن P تقوم بالإجراءات التالية:

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

تحليل

أمان

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

حيوية

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

استخدام عرض النطاق الترددي للشبكة

بافتراض أن رسائل خوارزمية التنمر ذات أحجام ثابتة (معروفة، غير متغيرة)، يتم تبادل أكبر عدد من الرسائل في المجموعة عندما تبدأ العملية ذات المعرف الأدنى عملية انتخاب. ترسل هذه العملية (N-1) رسالة انتخاب، وترسل العملية ذات المعرف الأعلى التالي (N-2) رسالة، وهكذا، مما ينتج عنهΘ(شمال2){\displaystyle \Theta \left(N^{2}\right)}رسائل انتخابية. وهناك أيضاًΘ(شمال2){\displaystyle \Theta \left(N^{2}\right)}الرسائل الحية، وΘ(شمال){\displaystyle \Theta \left(N\right)}رسائل المنسق، مما يجعل العدد الإجمالي للرسائل المتبادلة في أسوأ الحالاتΘ(شمال2){\displaystyle \Theta \left(N^{2}\right)}.

انظر أيضاً

مراجع

  1. ↑ كولوريس، جورج؛ دوليمور، جين؛ كيندبيرغ، تيم (2000). الأنظمة الموزعة: المفاهيم والتصميم (  الطبعة الثالثة). أديسون ويسلي. ISBN 978-0201619188.
  • ويتشل، إيميت (2005). "التنسيق الموزع" . تم الاطلاع عليه في 4 مايو 2005.
  • هيكتور غارسيا مولينا، الانتخابات في نظام الحوسبة الموزعة، معاملات IEEE للحواسيب، المجلد C-31، العدد 1، يناير (1982) 48-59
  • L. Lamport, R. Shostak, and M. Pease, “The Byzantine Generals Problem” ACM Transactions on Programming Languages ​​and Systems, Vol. 4, No 3, July 1982.
  • شعار ويكيميديا ​​كومنزالوسائط المتعلقة بخوارزمية Bully على ويكيميديا ​​كومنز