خوارزمية موزعة

الخوارزمية الموزعة هي خوارزمية مصممة للعمل على أجهزة حاسوب مكونة من معالجات مترابطة . تُستخدم الخوارزميات الموزعة في مجالات تطبيقية مختلفة للحوسبة الموزعة ، مثل الاتصالات ، والحوسبة العلمية ، ومعالجة المعلومات الموزعة ، والتحكم في العمليات في الوقت الحقيقي . تشمل المشكلات القياسية التي تحلها الخوارزميات الموزعة انتخاب القائد ، والتوافق ، والبحث الموزع ، وتوليد الشجرة الممتدة ، والاستبعاد المتبادل ، وتخصيص الموارد . ^{[ 1 ]}

الخوارزميات الموزعة هي نوع فرعي من الخوارزميات المتوازية ، تُنفذ عادةً بشكل متزامن ، حيث تعمل أجزاء منفصلة من الخوارزمية في وقت واحد على معالجات مستقلة، مع معلومات محدودة حول ما تفعله الأجزاء الأخرى. أحد التحديات الرئيسية في تطوير وتنفيذ الخوارزميات الموزعة هو التنسيق الناجح لسلوك الأجزاء المستقلة من الخوارزمية في مواجهة أعطال المعالجات وعدم موثوقية روابط الاتصال. يعتمد اختيار الخوارزمية الموزعة المناسبة لحل مشكلة معينة على خصائص المشكلة، وخصائص النظام الذي ستُنفذ عليه الخوارزمية، مثل نوع واحتمالية أعطال المعالجات أو الروابط، ونوع الاتصال بين العمليات الممكن إجراؤه، ومستوى تزامن التوقيت بين العمليات المنفصلة. ^{[ 1 ]}

الالتزام الذري

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

تتضمن الخوارزميات لحل مشكلة الالتزام الذري بروتوكول الالتزام ثنائي المرحلة وبروتوكول الالتزام ثلاثي المرحلة .

إجماع

تحاول خوارزميات الإجماع حل مشكلة اتفاق عدد من العمليات على قرار مشترك.

وبشكل أدق، يجب أن يستوفي بروتوكول الإجماع الخصائص الرسمية الأربعة التالية.

• الإنهاء : كل عملية صحيحة تحدد قيمة ما.
• الصلاحية : إذا اقترحت جميع العمليات نفس القيمة${\displaystyle v}$ثم تقرر كل عملية صحيحة${\displaystyle v}$.
• النزاهة : كل عملية صحيحة تحدد قيمة واحدة على الأكثر، وإذا حددت قيمة ما${\displaystyle v}$، ثم${\displaystyle v}$لا بد أن ذلك قد تم اقتراحه من خلال عملية ما.
• الاتفاق : إذا تم اتخاذ قرار بناءً على عملية صحيحة${\displaystyle v}$ثم تقرر كل عملية صحيحة${\displaystyle v}$.

من الخوارزميات الشائعة لحل مشكلة التوافق خوارزمية باكسوس وخوارزمية رافت .

البحث الموزع

انتخابات الزعيم

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

الاستبعاد المتبادل

هياكل البيانات غير المحظورة

بث موثوق

يُعدّ البث الموثوق أحد أساسيات الاتصال في الأنظمة الموزعة. ويُعرَّف البث الموثوق بالخصائص التالية:

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

يمكن أن يكون للبث الموثوق ترتيب تسلسلي أو سببي أو كلي.

النسخ

تخصيص الموارد

توليد الأشجار الممتدة

كسر التناظر، على سبيل المثال تلوين الرؤوس

• كريستيان كاشين؛ رشيد الكراوي؛ لويس رودريغز (2011)، مقدمة إلى البرمجة الموزعة الموثوقة والآمنة (2.  الطبعة)، سبرينغر، بيب كود : 2011itra.book .....C ، ISBN 978-3-642-15259-7
• C. Rodríguez, M. Villagra and B. Barán, Asynchronous team algorithms for Boolean Satisfiability , Bionetics2007, pp.  66–69, 2007.

• الوسائط المتعلقة بالخوارزميات الموزعة على ويكيميديا ​​كومنز
• برنامج معهد ماساتشوستس للتكنولوجيا التعليمي المفتوح - الخوارزميات الموزعة