Taqsimlangan algoritmlar vatizimlar

5 – Amaliy mashg’ulot. TAQSIMLANGAN MASALALAR VA ALGORITMLAR.
Ishning maqsadi: Ushbu amaliyotda ob'ektning hayot aylanish jarayonining boshqaruvini ko'rib chiqamiz.
Nazariy qism:
S tizim bilan, shu tizimning ishlash maqsadi G o’zaro bog'langan. Ushbu maqsadni tizimning o'zi (agar tizim faol bo'lsa) yoki tashqaridan tizimga qo’yiiladi. Maqsadga erishish uchun tizimda maqsadning qandaydir matematik formalizatsiyasi bo’lgan aniq kirish ma'lumotlar va talab qilingan natijalar majmuidan iborat masala hal etilishi lozim.
Masalaning yechimini olish algoritm yordamida, ya'ni ijrochisi (ijrochilari) ko'rsatilgan buyruqlar va ijrochilar tomonidan bajarilishi kerak bo'lgan elementar qadamlar ketma-ketligi yordamida olish nazarda tutiladi.
Taqsimlangan tizim taqsimlangan masalalarni keltirib chiqaradi, chunki masala uchun dastlabki ma'lumotlar fazoning turli nuqtalarda paydo bo'ladi. Bundan tashqari, turli nuqtalarda masalani hal qilishning ayrim natijalari talab qilinadi. Ko'pincha masala qism masalalarga bo'linishi mumkin, ularning ba'zilari markazlashgan bo'lishi mumkin: barcha dastlabki ma'lumotlar fazodagi bir nuqtada paydo bo'ladi va u shu nuqtada qism masalalarning yechish natijalari talab qilinadi.
Taqsimlangan masala muayyan nuqtalardan dastlabki ma'lumotlarni yig'adigan va hisoblarning natijalarini turli nuqtalarga yuboradigan taqsimlangan algoritm bilan hal etiladi. Algoritmni taqsimlanganlik ko’rsatkichligiga qo'shimcha omil fazodagi turli nuqtalarda joylashgan bir necha ijrochilarning mavjudligi (taqsimlangan ijrochi) bo'lishi mumkin.
Algoritm boshlang’ich ma’lumotlardan tashqari oraliq ma'lumotlar bilan ham ishlaydi katta tizimlarda esa ma'lumotlar bazalari bilan ishlaydi. Taqsimlangan algoritm uchun tabiiy ravishda savol tug'iladi: bu ma'lumotlar markazlashgan ma'lumotlar bazasi sifatida tashkil etiladimi yoki taqsimlangan ma’lumotlar bazasi sifatidami?
Taqsimlangan algoritmlar ko’rinishlaridan biri - bu protokollardir. Protokol kamida ikkita tomon mavjudligi bilan xarakterlanadi va bu tomonlar aloqa kanali orqali ajratiladi. Har bir tomonda lokal Ak (markazlashgan) algoritm bajariladi. Lokal A1 algoritmning bajarilishi unga boshqa lokal A2 algoritmdan ma'lumotlar kerak bo’lgunga qadar cheklangan vaqtgacha amalga oshiriladi. U aloqa kanali orqali lokal A2 algoritmga ma'lumotlar so'rovini yuboradi. A2 algoritm aloqa liniyasi orqali ma’lumotlarni yuborish orqali javob beradi. Shundan so'ng A1 lokal algoritm ishini davom ettiradi.
Protokollar odatda texnik rol o'ynaydi va masofadagi ob'ektlar o'rtasida ma'lumotlarni qabul qilish/uzatish rejimlarini o'rnatish uchun xizmat qiladi. Hisoblashlar nuqtai nazaridan protokol qismi bo’lgan lokal algoritmlar - murakkab emas.
Taqsimlangan algoritmlarlarning maxsus turi bu - kriptografik protokollardir. Ular har bir yoki ikkala tomonning aniq ma'lumot almashish va boshqa shunga o'xshash maqsadlar uchun o'zlari bergan ma’lumotlarga mos tushushini isbotlash uchun mo'ljallangan.
Eng oddiy kriptografik protokollardan biri bo’lgan - taqsimlangan algoritmlarni ko'rib chiqaylik. Fazodagi turli nuqtalarida joylashgan O1 va O2 ob'ektlar umumiy P masalaning bir qismini (P1 yoki P2) hal qiladi. Ular umumiy masalani yechish bilan birga ularning har biri o'z xususiy masalalari Q1 va Q2 bor. Shunday qilib, O1 ob'ekt bir vaqtning o'zida P1 va Q1 hamda O2 ob'ekt P2 va Q2 masalalarni hal qilishadi. Agar P1 va P2 masalalar bir-biriga mos keladigan va bir-birini to’ldiradigan bo’lsa u holda Q1 va Q2 masalalar bir-biriga qarama-qarshi bo'ladi.
Shuning uchun, O1 va O2 ob'ektlari hamkorlik qiladilar, biroq ayni paytda ular raqobat qiladilar. Ob’yektlar o’zaro raqobatlashshishadi ammo hamkorlik qilishga majbur deb aytishimiz mumkin. Bu Pi yoki Qi masalalaridan qaysi biri Oi obyekti uchun muhimroqligiga bog’liqdir.
Bu holat juda keng tarqalgan. Universitetlar mutaxassislarni tayyorlashni takomillashtirish masalasini hal qilishdan manfaatdordir va bu masalada ular hamkorlik qilishadi. Shu bilan birga, universitetlar qobiliyatli abiturientlar uchun har yili raqobatlashishadi. Ilmiy tashkilotlar tez-tez o'z manfatlari kesishish doirasida (fanlarning kesishmasida) birgalikda tadqiqot olib boradilar. Ammo ular moliya taqsimotida ham raqobatlashadilar. Firmaning ikki xil ish bo’limlari firmaning umumiy maqsadlariga erishish uchun ishlashadi, lekin ularning har biri firmaningboshqa bo'linmasiga qaragandq ko'proq rivojlanishni istaydi. Umuman olganda, do'stlar raqibdir. Qisman raqobat.
Bizning masalada, O1 va O2 ob'ektlar P masalani hal qilish yo’lida bir umumiy murosaga kelishlari kerak. Faraz qilaylik ikkita teng qiymatli (P masalaga nisbatdan) yechimlar bor deylik. Ulardan biri O1 ob'ektiga, ikkinchisi esa O2 ob'ektiga mos keladi. U holda O1 va O2 ob'ektlari qur’a tashlashga qaror qilishadi. Buni quyidagicha amalga oshirilish mumkin: har biri o’zining qog’ozida qarorini yozib, qog’ozlar trubka shaklida o’raladi va lototronda aylantirib ixtiyoriy bittasi olinadi. Bu murosaga erishish yechimidir. Bu yechimnng murakkabligi O1 va O2 ob'ektlarning bir-biridan juda katta masofada ekanligida va lototron bilan amalga oshirish mumkin emasligida. Lototronli protsedura bir joyda amalga oshiriladi, bu markazlashgan tizimda amalga oshirilishi mumkin. Bizning tizimimiz esa taqsimlangan.
Lototron prosedurasini O1 ob'ekt amalga oshirishi mumkin va O2 juda ob'ektni O1 ishonmasa ob'ekt . Ammo O2 ob'ekt natija e'lon. Hatto televizion eshittirishlar ham bu dalilni tasdiqlamaydi - bu mohirlik bilan yozilgan yozuv bo'lishi mumkin.
Chiqish yo'li quyidagicha. 0 echimlar biri, belgilaymiz boshqa - mustaqil ravishda boshqa ob'ektlarini har 0 ob'ektlar keyin ni va hisoblash natijasi N1 + N2 (mod raqamlarini almashildi qilingan 99 uchun, masalan, ichidagi har qanday integer ni chaqirish kerak soni 1. 2 ). Bu yechim, ya'ni. son, 0 yoki 1.
Birgalikda bir vaqtning o'zida raqamlar ob'ektlarini qabul qila olmaydi. Kimdir birinchi raqamini yuboradi va u g'olib bo'lmagan holatda bo'ladi. Misol uchun, O1 o'z raqamini n1ni "1" qozongan g'olib bo'lgan O2 obyektiga yuborgan. So'ngra, O2, N1 bilib, tenglama N1 +, n2 (mod 2) = 1, o'zgaruvchan, n2 hal va olingan qiymati O1, n2 yuboradi. Tenglama hal deyarli hech vaqt talab qiladi: O1 bir, hatto sonining olish, O2 aksincha tasodifiy javob, va kerak.
Bu adolatsizlikni yo'q qilish kerak. Shunga qaramasdan, xabar almashish taraflarining biri birinchi navbatda o'z raqamini yuboradi. Ikkinchi tarafning "javobni tanlash" uchun etarli vaqti yo'qligiga ishonch hosil qilish kerak.
O1 va O2 ob'ektlari masofadan turib "lotereya" larning butun amaliyoti bir necha daqiqada tugashi kerakligini qabul qilishi mumkin. Bir vaqtning o'zida ikkala ob'ekt ham javobni tanlab olish superkompyuterning bir necha soat ishlashini talab qilsa, u holda bu echim boshqa taraf tomonidan "sozlanmagan" bo'lishiga ishonch hosil qilishi mumkin.
Kalkulyatorda bunday vaqt parametrlarini ta'minlash uchun f (x) funktsiyasini ishlatish kerak, ma'lum argument x uchun y = f (x) qiymati nisbatan tez hisoblanishi mumkin. Ammo bu yerda f (x) = y tenglamasini yeching. Yning nominal qiymatini noma'lum x ni topish uchun tezkorlik qila olmaysiz. Bundan tashqari, bu tenglamani yechish uchun matematik usullar ma'lum emas, aniq qidiruv yoki murakkablik bilan bir xil bo'lmasligi kerak.
Albatta, f (x) funktsiyasini ta'riflash maydoni to'liq qidiruvni amalga oshirishni imkonsiz qilish uchun juda katta bo'lishi kerak. 0 va 1 elementlarining hududi kichik bo'lib, 0 dan 99 gacha bo'lgan hudud ham etarli emas. Ishlatiladigan tamsayılar kasr ko'rsatkichida eng kamida 150-200 ta raqam yoki ikki tomonlama belgilarda kamida 512 bit bo'lishi kerak. Bunday raqamlar "uzoq" deb nomlanadi.
F (x) va h (z, v, w) funksiyalari ikkita funktsiyaga aylanishi mumkin. H (z, v, w) funktsiyasida dastlabki ikki argument uzun raqamlar, uchinchisi esa bitwise. F va h funktsiyalari O1 va O2 ob'ektlariga ma'lum va ular ushbu funktsiyalarning qadriyatlarini argumentlarning berilgan qiymatlari uchun tez hisoblash uchun algoritmlarni bilishadi, lekin ular bu masalalarni tezda qanday qilib tezda o'zgartirishni bilishmaydi; tenglamalarni echish.
Quyidagilar quyida keltirilgan bosqichlardan iborat.
O2 ob'ekti tasodifiy ravishda katta intervaldan [0, q-1] x sonini tanlaydi.
Y = f (x) funksiyasini qaytaradi.
2. O2 obyekti y ning raqamini O1 ob'ektiga yo'naltiradi. O1 obyekti x sonini tiklay olmaydi.
3. O1 ob'ekti katta oraliqdagi [0, q-1] orasidagi raqamni tasodifiy tanlaydi. O1 obyekti tasodifiy bitni w ni tanlaydi. Bu harakatlar 1-band bilan bir vaqtning o'zida amalga oshirilishi mumkin.
4. O1 ob'ekti s = h (z, y, w) ni hisoblaydi. Bu yerda z zonasi "niqob" va "y" - ob'ekt O1 ob'ektlarining xatti-harakatlarining to'g'riligiga O2 ob'ektini "tekshirish" uchun kerak.
5. O1 ob'ekti s ni O2 ob'ektiga yuboradi. Bit w, O2 obyektiga yuboriladi, lekin u sonlar ichida "yashirin". O2 ob’yekti bu bitni saqlab qo'lolmaydi. O2 obyekti z raqamini tiklay olmaydi.
6. O2 obyekti tasodifiy bitni tanlaydi.
7. O2 obyekti O1 ob'ektiga bir oz yuboradi. Yuk tashish uchun ochiq.
8. O1 ob'ekti z va bit w ni O2 ob'ektiga yuboradi. Yuk tashish uchun ochiq. O1 obyekti allaqachon lotereya lotereyalari natijalarini aniqlab berishi mumkin: c + w (mod 2).
9. O2 ob'ekti t = h (z, y, w) ni hisoblaydi. Bu yerda z va w faqat O1 dan olinadi va y 1-bandda hisoblab chiqilgan.
10. O2 ob’yekti avval O1 ob'ektidan olingan t va s ni solishtiradi.
11. Agar t = s bo'lsa, u holda O2 obyekti lotereya lotlarining natijasini hisoblaydi:
c + w (mod 2).
F va h funktsiyalari har xil bo'lishi mumkin. Xususan, quyidagi funktsiyalar qo'llaniladi:
f(x) = gx (mod p) и h(z, v, w) = vwgz (mod p).
Bu yerda x, w, z ning "yashirin" qiymatlari vakolat doirasiga kiradi va ularni topish uchun aniq qidiruv tizimidan ancha yaxshi bo'lgan algoritm aniq bo'lgan logaritma masalasini hal qilish talab qilinadi.
P, q, g o’zgarmas ikkala ob'ektga ma'lum bo'lishi kerak. P soni uzoq boshlang'ich raqam. Q raqami ham p-1 sonining bo'lagi bo'lgan uzoq boshlang'ich raqamdir. 1 gacha bo'lmagan g < p gq = 1 (mod p) holatiga mos keladi.
Yig'ilgan masalalarni hal qiladigan taqsimlangan algoritmlar. Taqsimlangan algoritmlarni rivojlantirishning yo'nalishlaridan biri yuqori samarali hisoblash hisoblanadi. Bu holda taqsimlangan kompyuter tizimi bir masalani hal qilishda kuchli hisob-kitob qilish vositasi sifatida ishlatiladi. Mashhur bir misol, DES shifrlash algoritmi tomonidan yaratilgan shifrlarni "buzish" masalasi. Agar shifrlash tugmasi ma'lum bo'lsa, matnning parolini o'zgartirish qiyinlashtirilmaydi. Agar kalit ma'lum bo'lmasa, unda parol hal qilishni to'liq qidirish orqali sinab ko'rish mumkin. Biroq, to'liq qidirish usuli juda tez, hatto eng tezkor protsessorli kompyuterlar uchun ham talab qiladi.
Masalani echish juda protsessorli kompyuter yordamida tezlashtirilishi mumkin. Bunday holda, hisoblar parallel holga keltiriladi, ya'ni. barcha protsessorlar bir vaqtning o'zida bir xil yoki turli xil buyruqlar bajarib, masalani hal qilishda ishtirok etishadi. Qanday parallellashtirish amalga oshirilishi juda protsessorli kompyuterning arxitekturasiga bog'liq. Ideal vaziyatda n tarkibida n protsessorlar mavjud bo'lsa, hisoblashlarning tezlashishi n vaqtga yaqin qiymatga ega bo'lishi mumkin. Aslida, algoritmlar to'liq parallel holga kelmagan, ayrim protsessorlar muayyan vaqt oralig'ida bo'sh bo'lishi mumkin va ishlash n vaqtdan kamroq vaqt bilan ortadi.