Chang va Roberts algoritmi - Chang and Roberts algorithm

The Chang va Roberts algoritmi[1] a halqaga asoslangan koordinator saylov algoritmi yilda ishlagan tarqatilgan hisoblash.

Algoritm

Algoritm har bir jarayonning yagona identifikatsiyalash (UID) ga ega ekanligini va jarayonlar o'zlarini bir yo'nalishli uzuk har bir jarayondan soat yo'nalishi bo'yicha qo'shniga o'tadigan aloqa kanali bilan. Ikki qism algoritmini quyidagicha ta'riflash mumkin:

  1. Dastlab ringdagi har bir jarayon quyidagicha belgilanadi ishtirok etmaydigan.
  2. Rahbar etishmasligini sezgan jarayon saylovni boshlaydi. Bu yaratadi saylov to'g'risidagi xabar uning UID-ni o'z ichiga oladi. Keyin ushbu xabarni soat yo'nalishi bo'yicha qo'shnisiga yuboradi.
  3. Har safar jarayon yuboradi yoki yuboradi saylov to'g'risidagi xabar, jarayon o'zini ishtirokchi sifatida belgilaydi.
  4. Jarayon an qabul qilganda saylov to'g'risidagi xabar u xabardagi UIDni o'zining UID bilan taqqoslaydi.
    1. Agar saylov to'g'risidagi xabarda UID kattaroq bo'lsa, jarayon so'zsiz yuboradi saylov to'g'risidagi xabar soat yo'nalishi bo'yicha.
    2. Agar saylov xabaridagi UID kichikroq bo'lsa va jarayon hali ishtirokchi bo'lmasa, jarayon xabardagi UID-ni o'zining UID-ga almashtiradi, yangilangan xabarni yuboradi saylov to'g'risidagi xabar soat yo'nalishi bo'yicha.
    3. Agar saylov xabaridagi UID kichikroq bo'lsa va jarayon allaqachon bo'lsa ishtirokchi (ya'ni, jarayon allaqachon UID bilan o'z saylov kodidan kam bo'lmagan miqdorda saylov xabarini yuborgan), jarayon saylov haqidagi xabarni bekor qiladi.
    4. Agar kelayotgan saylov xabaridagi UID jarayonning UID bilan bir xil bo'lsa, bu jarayon etakchi sifatida ishlay boshlaydi.

Jarayon etakchi sifatida ishlay boshlagach, algoritmning ikkinchi bosqichi boshlanadi.

  1. Etakchi jarayon o'zini o'zi sifatida belgilaydi ishtirok etmaydigan va yuboradi tanlangan xabar qo'shniga o'z saylovi va UIDni e'lon qilgani haqida.
  2. Jarayon an qabul qilganda tanlangan xabar, o'zini o'zi sifatida belgilaydi ishtirok etmaydigan, tanlangan UIDni qayd etadi va yuboradi tanlangan xabar o'zgarishsiz.
  3. Qachon tanlangan xabar yangi saylangan rahbarga etib boradi, rahbar bu xabarni tashlaydi va saylov tugaydi.

Hech qanday nosozlik bo'lmasa, bu algoritm tugaydi, algoritm har qanday N protsess uchun ishlaydi va halqada qancha jarayon borligini bilish uchun biron bir jarayon talab qilinmaydi.

Xususiyatlari

Algoritm hurmat qiladi xavfsizlik: jarayon o'z UID-i bilan tanlangan xabarni oladi, agar uning UID-si boshqalarnikidan kattaroq bo'lsa va barcha jarayonlar bir xil UID-da kelishsa. Algoritm ham hurmat qiladi tiriklik. "Ishtirokchi" va "qatnashuvchi emas" holatlaridan foydalaniladi, shunday qilib bir nechta jarayonlar bir vaqtning o'zida saylovni boshlaganda, faqat bitta g'olib e'lon qilinadi.

Saylovni boshlashning yagona jarayoni bo'lganida, algoritm eng yomon holatda 3N-1 ketma-ket xabarlarni talab qiladi. Eng dahshatlisi shundaki, saylovni boshlash jarayoni eng katta UIDga ega bo'lganga to'g'ri keladi: saylov xabarining etib borishi uchun N-1 xabarlari, keyin o'z UID-ni qaytarib olish uchun N xabarlari, keyin boshqa N xabarlari kerak ringdagi barchani saylangan xabarni yuborish.

Ushbu algoritm xatolarga juda chidamli emas. Xatolarga bardoshliligini oshirish mumkin, agar har bir jarayon ACK xabarlarini kiritish va xabarlarni yuborishda noto'g'ri tugunlarni o'tkazib yuborish orqali butun topologiyani bilsa.

Shuningdek qarang

Adabiyotlar

  1. ^ Ernest Chang; Rozmari Roberts (1979), "Jarayonlarning dumaloq konfiguratsiyasida markazlashtirilmagan ekstremma topish uchun takomillashtirilgan algoritm", ACM aloqalari, ACM, 22 (5): 281–283, doi:10.1145/359104.359108CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)