1-ma’ruza. Taqsimlangan masalalar, tizimlar va algoritmlar. Reja

1-ma’ruza. Taqsimlangan masalalar, tizimlar va algoritmlar.


Reja:

1. 
   Masalalar va algoritmlarning o’zaro bog’liqligi.
   
2. 
   Taqsimlangan boshqarish tizimlari va ma’lumotlar bazasi.
   
3. 
   Markazlashgan va taqsimlangan tizimlar.
   
4. 
   Taqsimlangan tizimlar tandemlari.
   

Tayanch iboralar. Tizim, element, tizimda munosabat, predikat, taqsimlangan tizim, uzluksiz tizim,diskret tizim, mashrutlash, to’plam elementi, prosessor buyrug’i, tanlov, tandem, taqsimlangan boshqarish tizimlari, korporativ tizimlar, korporativ tarmoq, ofis kompyuterlari,aloqa tizimi, tarmoq operatstion tizimlar, MBBT,parallel ma’lumotlar, tizimli servislar, tarmoq texnologiyalari, aloqa, algoritm, kriptografik protokol, tizim, yechim, masala, maqsad, matematik formalizasiya, boshlang’ich ma’lumotlar, bajaruvchi, qadam, taqsimlangan masala, masala osti, taqsimlangan algoritm, ma’lumotlar bazasi, protokol, lokal, konkurensiya, kompromis, prosedura, super EHM, ko’p prosessorli mashina.

1. 
   Masalalar va algoritmlarning o’zaro bog’liqligi
   

S tizim bilan, shu tizimning ishlash maqsadi G o’zaro bog'langan. Ushbu maqsad tizimning o'zi (agar tizim faol bo'lsa) yoki tashqi tomondan yetkaziladi. tizimining maqsadi muammoni hal qilinishi kerak erishish uchun - maqsad ba'zi matematik formalizasiyalashni kiritish ma'lumotlar aniq belgilangan majmui va kerakli natijalar bilan muammoni hal etish algoritm yordamida, ya'ni ijrochining (ijrochilarning) ko'rsatuvlari va ijrochilar tomonidan bajarilishi kerak bo'lgan elementar qadamlar ketma-ketligi.
Taqsimlangan tizim tarqatilgan muammolarni keltirib chiqaradi, chunki muammo uchun dastlabki ma'lumotlar fazodagi turli nuqtalarda paydo bo'ladi. Bundan tashqari, turli nuqtalarda muammoni hal qilishning ayrim natijalari talab qilinadi. Ko'pincha vazifa subtaskalarga bo'linishi mumkin, ularning ba'zilari bo'shashishi mumkin: barcha dastlabki ma'lumotlar fazodagi bir nuqtada paydo bo'ladi va u yerda subtaskalarni hal qilish natijalari ham talab qilinadi.
Taqsimlangan muammo muayyan nuqtalardan dastlabki ma'lumotlarni yig'adigan va hisoblarning natijalarini turli nuqtalarga yuboradigan taqsimlangan algoritm bilan hal etiladi. Algoritmni taqsimlashda qo'shimcha omil fazodagi turli nuqtalarda joylashgan bir necha ijrochilarning mavjudligi (taqsimlangan ijrochi) bo'lishi mumkin.
Algoritm asl ma'lumotlarga, shuningdek, oraliq ma'lumotlarga qo'shimcha ravishda ishlaydi va ma'lumotlar bazalari bilan yirik tizimlarda ishlaydi. Taqsimlangan algoritm uchun tabiiy ravishda savol tug'iladi: bu ma'lumotlar konsentrlangan yoki taqsimlangan ma'lumotlar bazasida qanday tashkil etiladi?
Taqsimlangan algoritmlardan biri protokol. Protokoli kamida ikkita tomon mavjudligi bilan ajralib turadi va aloqa kanali orqali ajratiladi. Har tomondan, Ak (mahalliy) (joyga jamlanganda) algoritmi bajariladi. u boshqa mahalliy algoritm A2 ma'lumotlarni muhtoj davom qachon Mahalliy algoritm A1 vaqtida ma'lum bir nuqtaga qadar amalga oshiriladi. Mahalliy algoritm A2 ga ulanish orqali ma'lumot so'rovini yuboradi. Algoritm A2 aloqa liniyasi orqali xabar yuborish orqali javob beradi. Shundan so'ng mahalliy algoritm A1 ishini davom ettiradi.
Protokollar odatda texnik rol o'ynaydi va masofadan ob'ektlar o'rtasida ma'lumotlarni uzatish / uzatish rejimlarini o'rnatish uchun xizmat qiladi. Hisob-kitoblarga ko'ra, mahalliy algoritmlar - protokol qismlari murakkab emas.
Maxsus tarqatiladigan algoritmlar kriptografik protokollardir. Ular bir yoki ikkala tomonning o'zlari bergan, aniq ma'lumot almashish va boshqa shunga o'xshash maqsadlar uchun ular tomonidan aniqlanganligini isbotlash uchun mo'ljallangan.
Eng oddiy kriptografik protokollardan biri - taqsimlangan algoritmlarni ko'rib chiqaylik. fazodagi turli ball umumiy muammoni hal qilish istagi boshqa Biroq umumiy muammo P. bir qismini (P₁ yoki P₂) qaror har biri ikki ob'ekt, O₁ va O₂, bor paytda, ob'ektlar o'z Xususan muammolari, 1-savol va Q₂ bor. vazifa P₂ va 2-choragida - Shunday qilib, bir vaqtning o'zida ob'ekt O₁ P₁ va Q₁, va ob'ekt O₂ muammosini hal. P₁ va P₂ maqsadlari mos va o'zaro mustahkamlash bo'lsa, 1-savol va muammoni Q₂ - qarama-qarshi bo'ladi.
Shuning uchun, O₁ va O₂ ob'ektlari hamkorlik qiladilar, biroq ayni paytda ular raqobat qiladilar. Va siz moslamalarni raqobatlashtirasiz deb aytishingiz mumkin, ammo hamkorlik qilish kerak. Vazifalarni qanday joylashtirishni ko'rib chiqaylik, Piy yoki Q_i vazifalaridan qaysi biri O_i obyekti uchun muhimroq.
Bu holat juda keng taqsimlangan. Universitetlar mutaxassislarni tayyorlashni takomillashtirish vazifasini hal qilishdan manfaatdordir va bu vazifada ular hamkorlik qilmoqdalar. Shu bilan birga, universitetlar qobiliyatli abiturientlar uchun har yili raqobatlashadi. Ilmiy tashkilotlar tez-tez o'z manfaatlarini kesib o'tishda (fanlarning kesishmasida) birgalikda tadqiqot olib boradilar. Ammo ular moliya taqsimotida ham raqobatlashadilar. Ikki xil ish birliklari kompaniya umumiy maqsadlarga erishish uchun mehnat, lekin ularning har biri kompaniya boshqa bo'linmasi ko'proq rivojlangan ostida olishni istaydi. Umuman olganda, do'stlar raqibdir. Qisman raqobat.
Bizning muammo, ob'ektlar O₁ va O₂ muammoni P. hal manfaatlari bir umumiy murosaga kelgan teng ikki yechimlari (vazifa R jihatidan) bor deylik. Ulardan biri O₁ ob'ektiga, ikkinchisi esa O₂ ob'ektiga mos keladi. Keyin O₁ va O₂ ob'ektlari lotlarni tashlashga qaror qiladi. Bu amalga oshirilishi mumkin: a kolba ichiga qog'oz yo'l, qog'oz o'z parcha har qaror yozish bingo va amalga olish uchun qog'oz parcha biriga o'ting. Bu murosaga erishish murakkablik darajasi ob'ektlar O₁ va O₂ bir-biridan juda katta masofada ekanligi, va bingo bilan amaliyotlaridan amalga oshirish uchun mumkin emas. Lototronli protsedura bir joyda amalga oshiriladi, bu erda konsentratsiyalangan tizim bo'lishi mumkin. Bizning tizimimiz taqsimlangan.
Lototron tartibi ob'ekt O1 amalga mumkin va O₂ juda ob'ektni O₁ 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 N₁ + N₂ (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, O₁ o'z raqamini n1ni "1" qozongan g'olib bo'lgan O₂ obyektiga yuborgan. So'ngra, O₂, N₁ bilib, tenglama N₁ +, n₂ (mod 2) = 1, o'zgaruvchan, n₂ hal va olingan qiymati O₁, n₂ yuboradi. Tenglama hal deyarli hech vaqt talab qiladi: O₁ bir, hatto sonining olish, O₂ 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.
O₁ va O₂ 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 erda 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.