Чанг және Робертс алгоритмі - Chang and Roberts algorithm

The Чанг және Робертс алгоритмі[1] Бұл сақинаға негізделген сайлау алгоритмі үйлестірушісі, жұмыспен қамтылған таратылған есептеу.

Алгоритм

Алгоритм әр процестің бірегей идентификацияға (UID) ие екендігін және процестердің өзін біржақты сақина әр процесстен сағат тілімен көршіге өтетін байланыс каналымен. Екі бөлімнен тұратын алгоритмді келесідей сипаттауға болады:

  1. Бастапқыда сақинадағы әрбір процесс ретінде белгіленеді қатысушы емес.
  2. Көшбасшының жоқтығын байқайтын процесс сайлауды бастайды. Бұл жасайды сайлау туралы хабарлама оның UID кодын қамтиды. Содан кейін бұл хабарламаны сағат тілімен көршісіне жібереді.
  3. Процесс сайын жібереді немесе жібереді сайлау туралы хабарлама, процесс сонымен қатар өзін қатысушы ретінде белгілейді.
  4. Процесс қабылдаған кезде сайлау туралы хабарлама ол хабарламадағы UID-ді өзінің UID-мен салыстырады.
    1. Егер сайлау хабарламасындағы UID үлкенірек болса, процесс сөзсіз алға жібереді сайлау туралы хабарлама сағат тілімен.
    2. Егер сайлау хабарламасындағы UID кішірек болса және процесс әлі қатысушы болмаса, процесс хабарламадағы UID-ді өзінің UID-мен алмастырады, жаңартылған хабарламаны жібереді сайлау туралы хабарлама сағат тілімен.
    3. Егер сайлау туралы хабарламадағы UID кішірек болса және бұл процесс қазірдің өзінде қатысушы (яғни, үдеріс UID-мен, ең болмағанда, өзінің UID-мен бірдей көлемінде) сайлау хабарламасын жіберді), процесс сайлау туралы хабарламаны алып тастайды.
    4. Егер кіріс сайлау хабарламасындағы UID процестің UID-мен бірдей болса, онда бұл процесс көшбасшы рөлін атқара бастайды.

Процесс көшбасшы рөлін атқара бастаған кезде, алгоритмнің екінші кезеңі басталады.

  1. Көшбасшы процесі өзін ретінде белгілейді қатысушы емес және жібереді сайланған хабарлама көршісіне өзінің сайлануы және UID туралы жариялайды.
  2. Процесс қабылдаған кезде сайланған хабарлама, ол өзін ретінде белгілейді қатысушы емес, таңдалған UID жазбасын жазып, жібереді сайланған хабарлама өзгеріссіз.
  3. Қашан сайланған хабарлама жаңадан сайланған көшбасшыға жетеді, көшбасшы бұл хабарламаны тастайды, ал сайлау аяқталады.

Бұл алгоритм ешқандай ақаулар болмаса, алгоритм N процестерінің кез-келген саны үшін жұмыс істейді және сақинада қанша процестің бар екендігін білу үшін ешқандай процесс қажет емес.

Қасиеттері

Алгоритм құрметтейді қауіпсіздік: процедура өзінің UID идентификаторы басқаларға қарағанда үлкен болған жағдайда ғана, және барлық процестер бір UID-ге келіскенде ғана өзінің жеке интерфейсі бар хабарлама алады. Алгоритм де құрметке ие тіршілік. «Қатысушы» және «қатысушы емес» күйлері бірнеше процестер бір уақытта сайлауды бастаған кезде тек бір ғана жеңімпаз жарияланатындай етіп қолданылады.

Сайлауды бастайтын жалғыз процесс болған кезде, алгоритмге ең нашар жағдайда 3N-1 дәйекті хабарламалар қажет. Ең жаман жағдай - бұл сайлауды бастау процесі UID ең үлкені болып табылады: сайлау хабарламасы оған жету үшін N-1 хабарламаларын, содан кейін өзінің UID-ін қайтару үшін N хабарламаларын, содан кейін басқа N хабарламаларын қажет етеді рингтегі барлық адамдарға сайланған хабарлама жіберу.

Бұл алгоритм ақаулыққа төзімді емес. Ақаулыққа төзімділікті арттыруға болады, егер әрбір процесс барлық топологияны білсе, ACK хабарламаларын енгізу және хабарламаларды жіберу кезінде ақаулы түйіндерді өткізіп жіберу.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ Эрнест Чанг; Розмари Робертс (1979), «Процестердің дөңгелек конфигурацияларында экстремаларды табудың орталықтандырылмаған алгоритмі», ACM байланысы, ACM, 22 (5): 281–283, дои:10.1145/359104.359108CS1 maint: бірнеше есімдер: авторлар тізімі (сілтеме)