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

5. Tanlash algoritmini aniqlash. Siljitish algoritimi va uni ishlashini misolda ko’rsatish

Ko'pgina taqsimlangan tizimlarda saytlarning biri taqsimlanlgan algoritmni bajarishda koordinator rolini bajaradi. Ba'zan koordinator algoritmning bajarilishini boshlagan sayt. Lekin har doim ham bir xil sayt hisoblash davomida koordinator bo'lib qolishi mumkin emas. Koordinatorni o'zgartirish uchun quyidagi sabablar mavjud.

1. Saytning muvofiqlashtiruvchisida uskunaning yo'qligi, buning natijasida ushbu sayt taqsimlangan tizimdagi jarayonlarni boshqarishni davom ettira olmaydi.
2. Saytda amalga oshiriladigan tashkillashtirish usuli samarasiz deb topildi.
3. Tizimning turli joylaridan foydalanish intensivligidagi o'zgarishlar, avvalgi joydan muvofiqlashtirish boshqa saytlar bilan muvofiqlashtirishdan ko'ra samarasiz bo'lishiga olib keladi.
Bunday hollarda yangi koordinator talab qilinadi. Saytlar orasida tanlov markazlashtirilgan algoritmni amalga oshirish kerak va algoritm tashabbuskori rolini biladigan nomzod bo'lmasa ham amalga oshirilishi kerak. Misol uchun, tizimni ishga tushirish yoki boshlash paytida bajarilishi kerak bo'lgan tizimni ishga tushirish protsedurasi. Ko'pgina faol saytlar oldindan ma'lum bo'lmasligi mumkinligi sababli, bitta saytni bir martagina rahbar sifatida ko'rsatish mumkin emas.
Faol (hozirgi kunda faoliyat yuritadigan) saytlar o'z-o'zini tashkil qilish va muvofiqlashtiruvchi saylovini o'tkazishi kerak. Tanlovda nomzodlar haqida ba'zi ma'lumotlarga ehtiyoj bor. Oddiylik uchun biz har bir sayt bilan bog'liq bo'lgan ma'lum sonni - est qiymatini taxmin qilamiz. Baholashning maksimal (yoki alohida vazifalari - minimal) qiymati bo'lgan sayt tanlanishi kerak.
Barcha mahalliy qiymatlar bir joyda to'plangan bo'lsa, maksimal qiymatni topish qiyin emas. Biroq, bu qiyinchilik, axborot to'plashda kimlar to'planishi mumkinligi, shuningdek, yig'ish tartibining tizimning arxitekturasiga bog'liqligi aniq emas. Ko'chirma algoritmi
Algoritm saytlarning mahalliy hisob-kitoblari asosida muvofiqlashtiruvchining dinamik tanlovi uchun mo'ljallangan. Aloqa kanallari ishonchli hisoblanadi va saytlar ba'zan ularning faoliyatini to'xtatishi mumkin (masalan, muvaffaqiyatsizlik tufayli).
Saytlar uchta mumkin bo'lgan qiymatlar bilan almashishadi: "saylov", "javob", "muvofiqlashtiruvchi". Saylov haqida "saylov" xabarlari yuboriladi. "Javob" xabari saylov e'lon qilingani munosabati bilan yuboriladi. Yangi koordinator identifikatorini e'lon qilish uchun "koordinator" xabar yuboriladi.
Tanlovning algoritmi har qanday Si saytidan boshlanishi mumkin, chunki mavjud SC muvofiqlashtiruvchisi ishlamayapti (masalan, koordinatordan xabarlarni kutish juda uzoq davom etsa).
Algoritm quyidagi bosqichlardan iborat.
1. S_i sayti saytga "saylov" xabarini yuboradi, bu esa boshqa saytlarga nisbatan ancha katta (S_j) reytingga ega. U "javob" xabarini yuborishni kutmoqda.
sayt S_i javob
2. Kutish hech javob, bu vaqt ichida qabul qilingan bo'lsa vaqt T. ko'p bo'lmagan davom etadi, Si sayt o'zini e'lon va koordinatori ularga, "koordinatori" xabar yuborib EST (Si) dan kam ball saytlarni xabardor qiladi. javob olingan bo'lsa, keyin Si sayt ba'zi cheklangan vaqt Xabar "koordinatori" qabul (ehtimol "katta" hamkasblari kimdir koordinatori sifatida orqali o'tadi) kutadi. Agar u "koordinator" xabarini kutmasa, Si saytida yangi saylovlar boshlanadi.
3. Agar Si sayti "muvofiqlashtiruvchi" xabarini olgan bo'lsa, u ushbu xabar olingan sayt identifikatorini qayd qiladi va keyin bu sayt bilan muvofiqlashtiruvchi sifatida bog'laydi.
bir sayt Sj xabar "Saylov" qabul qiladi va saylovlarda ishtirok etish niyatida bo'lsa
4. xabar "javob" qaytadi, so'ngra (uning baholash EST (Sj eslang) hozir olib smeta EST (Si) sayt kattaroqdir yangi saylovlarni boshlanadi saylovlar).
5. Agar SC sayti qayta boshlangan bo'lsa, u saylovni boshlaydi. Esh (SC) reytingi eng yuqori bo'lsa, u o'zini koordinator deb e'lon qiladi va bu haqida boshqa saytlarga ma'lum qiladi. Bunday holatlarga qaramasdan, ba'zi bir sayt sayg'oqlarning noto'g'ri ishlashi vaqtida saylovni qo'lga kiritdi va hozirda koordinator vazifasini bajaradi. "Vaqtinchalik" o'zgarish mavjud. Shuning uchun, tanlash algoritm deb atash mumkin olish algoritm (Ingliz tili nomi - urmoq algoritm; bezori so'z, jabbor, hashamatli, ajoyib ishqalanish qadriyatlarni, scrapper, bouncer bor).
Shakl. 9.4-rasmda algoritmning to'rtta bosqichi ko'rsatilgan. Algoritm, S1 saytining SC saytining muvofiqlashtiruvchi funktsiyalarini bajarmasligini aniqlaganligi bilan boshlanadi. Keyin S₂ va S₃ saytlariga tegishli xabarlarni yuborib, saylovlarni e'lon qiladi. Sayt S₁ "javob" (1-qadam) va o'z tanlovlarini boshlaydi (2-qadam). Rasmda, saytlarning estalik baholari chapdan o'ngga ko'tariladi.
S₃ sayti S₂ saytiga "javob" yuboradi, lekin u javob bermaydi, chunki u ishlamaydi. Shuning uchun S3 koordinator vazifalarini bajarishga qaror qiladi. Ammo u omadli emas: u ham muvaffaqiyatsiz (3-qadam), "koordinator" xabarini jo'natish uchun vaqti yo'q.
Shu bilan birga, S₁ saytining kutish muddati saylovlarni tugatadi. U "javob" xabarlarini oldi, ammo "koordinator" xabarlari yo'q. Keyin u yangi saylovlar boshlanadi, undan keyin koordinator (S) S2 saytiga aylanadi.
Quyida keltirilgan barcha algoritmlarda p-saytidagi jarayonlar mumkin bo'lgan qiymatlarni muvofiqlashtiruvchi va yo'qotilgan davlat o'zgaruvchiga ega. Ba'zan biz davlat p hisoblash kiritilgan bo'lsa, uyqu, bir qiymati p algoritm bir qadam, va jongina (nomzod) qiymatini bajarmadi (uyqu), bor, biroq u yutib chiqiladi yoki yutqaziladi bo'ldi bilmaydi, deb taxmin. Ba'zi algoritmlar algoritm ko'rsatilgan bo'ladi va hokazo, faol passiv kabi qo'shimcha davlatlar, foydalaning. Tanlash muammosi noyob identifikatorlari ahamiyati ular xabarlarini hal qilish uchun emas, balki faqat foydalanish mumkin, balki saytlarni baholash uchun, deb. bo'lishi mumkin tanlash algoritmi ishlab chiqish, masalan, baholash (eng past bilan yoki aksincha) eng yuqori bo'lgan sayt g'olib kerak, deb talab qiladi. Keyinchalik vazifa - markazlashmagan algoritmdan foydalanib, identifikatorni eng yuqori baho bilan topish. Bunday holda, tanlash muammosi ekstremumni topish muammosi deb ataladi.
Daraxtlar uchun algoritmdan foydalanib tanlash bir tarqatish tizimi topologiyasi bo'lsa - bir daraxt yoki mavjud spanning Tree tizimi, tanlash, bu algoritm yilda berilgan algoritm bilan amalga oshirilishi mumkin, barcha end vertices algoritm tashabbuskorlari deb talab qiladi. Algoritmni ba'zi saytlar ham tashabbuskor bo'lgan holga aylantirish uchun uyg'otish davri qo'shiladi. Saylovni boshlashni istagan saytlar barcha boshqa saytlarga xabar yuboradi.

9.4-rasm. «ofsetni» tanlash uchun algoritmning bajarilishiga misol.

Bir sayt har bir kanal orqali xabar olganda, u eng yuqori baholash bilan sayt ID hisoblash uchun, shuningdek, uzaytiriladi bob 12 dan algoritm ijro boshlanadi, va har bir sayt Qaytish (OK) amaliyotlaridan amalga oshiradi, deb. Sayt ushbu amaliyotni amalga oshirganda, u koordinator identifikatorini biladi; agar ushbu identifikator identifikatorning identifikatoriga to'g'ri keladigan bo'lsa, u muvofiqlashuvchi bo'lib, agar bo'lmasa, yo'qotilgan hisoblanadi.

Yuborilgan algoritm Boolean ( «yuborilgan») matnida har bir sayt bir marta ortiq bir xabar yuborish uchun ishlatiladi, va o'zgaruvchan hisoblagich (counter) xabarlar sonini , «veb-sayt hisob uchun ishlatiladi.