9-ma’ruza. Saytlarni aylanish va tanlash algoritmlari. Reja

var is_sent: boolean init false ;
counter: integer init 0 ;
rec_p[q]: boolean hamma q  Out(this) init false ;
m: integer init this ;
state : (sleep, koordinator, lost) init sleep ;
begin if this – coordinator then
begin is_sent := true ;
forall in Out(this) do send <wakeup> to q
end ;
while counter< card(Out(this)) do
begin receive<wakeup> ; counter := counter + 1 ;
if notis_sent then
begin is_sent := true ;
forall q Out(this) do send <wakeup> to q
end
end ;
(* Algoritmning boshlanishi *)
while card{q : rec_p[q]} > 1 do
begin receive (token, r) from q ; rec_p[q] := true ;
ifest(r) >est(m) then m := r
end;
send (token, m) to q₀ with rec_p[q₀] ;
receive (token, r) from q₀ ;
if est(r) >est(m) then m := r; (* return(OK) m javob bilan *)
ifm = this then state := coordinator else state := lost ;
forall q Out(this), q  q₀do send (token, m) to q
end

Eng kamida bitta sayt algoritmni ishga tushirganda, barcha saytlar xabarlarini qo'shnilariga yuboradi va har bir sayt har bir qo'shnidan xabarini olgandan keyin daraxt uchun algoritmni ishga tushiradi. Barcha jarayonlar bir xil qiymatga ega bo'lgan daraxt uchun algoritmni to'ldiradi, ya'ni saytning eng yuqori bahosi bilan. Bunday baho beradigan yagona sayt muvofiqlashtiruvchining maqomini bajarishni tugatadi va boshqa barcha saytlar yo'qolib qolishi mumkin.

Har bir kanal orqali xabarlarning murakkabligi 4N-4 bo'lgan ikkita xabar va ikkita xabarlari yuboriladi. Dastlabki jarayondan so'ng D vaqt birliklari algoritmni boshlaganida, har bir operatsiya xabarlarini yuborgan, shuning uchun D + 1 vaqt birliklari uchun har bir jarayon to'lqin boshlagan. Birinchi qaror to'lqin boshlanishidan keyin D vaqtidan kechiktirilmayapti va so'nggi qaror birinchi marta keyin D vaqtidan kechiktirildi, jami vaqt 3D + ga teng bo'lganini ko'rish oson.
Agar kanaldagi xabarlar tartibi o'zgartirilishi mumkin bo'lsa (ya'ni, kanal FIFO bo'lmasa), jarayon qo'shnisidan xabarini olishdan oldin xabarni (token, r) qabul qilishi mumkin. Bunday holda xabar (token, r) vaqtinchalik saqlanishi yoki undan keyin keladigan xabarlar (token, r) sifatida qayta ishlanishi mumkin. Ring me'morchiligi uchun tanlangan algoritmlarbir tarqatish tizimi Arxitektura uzuk uchun LELA algoritmida (yo'naltirilgan asr) har bir tashabbuskori buyuk baholash EST tanlangan tashabbuskori () keyin, barcha tashabbuskorlaridan identifikatorlari ro'yxatini aniqlaydi. Har bir tashabbuskor identifikatorni ringning ustida ko'rsatuvchi belgini yuboradi va ushbu belgi barcha saytlar tomonidan qabul qilinadi. Bu kanal FIFO intizom tobe bo'lgan taxmin qilinadi va u boshqa tashabbuskori belgini (sayt alomatini olganda, u keyin algoritmini boshlashi emas) oladi oldin tashabbuskori markerni ishlab kerakligini.
Tashabbuskori o'z belgini qabul P, barcha tashabbuskorlaridan markerlar p orqali bo'lgan, va p tashabbuskor orasida eng yuqori ball bor faqat p tanlanadi. Sizga saytlarning tashqi va ichki belgilarini ajratishingiz kerakligini eslatib o'tamiz. Bu erda p va q tashqi belgilar. Ular boshqa joylarda ishlaydigan jarayonlar yordamida kerak bo'lganda foydalaniladi. uning jarayon ID P o'z veb-sayti, bu ko'rsatilgan. Bu holda, albatta, p, va bu bir xil qiymati (masalan, soni yoki kodi) mavjud. Quyidagi algoritmda davlat o'zgaruvchisi saytning holatini aniqlaydi.
LELA algoritm: