خوارزمية هوانغ

خوارزمية هوانغ هي خوارزمية للكشف عن الإنهاء في نظام موزع . وقد اقترحها شينغ-تسان هوانغ في عام 1989 في مجلة Information Processing Letters . ^{[ 1 ]}

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

يحدث الإنهاء عندما تصبح جميع العمليات في النظام الموزع خاملة ولا توجد رسائل حسابية قيد النقل.

يمكن وصف خوارزمية هوانغ على النحو التالي:

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

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

• خوارزمية ديكسترا-شولتن