Taqsimlangan algoritmlar vatizimlar

Taqsimlangan tizimlarni markazlashgan masallarni tezroq yechishga tadbiqi.

Tarqatilgan to'qimalar algoritmi quyidagi bosqichlardan iborat.
1. O2 ob'ekti katta oraliqdagi [0, q - 1] orasidagi raqamni tasodifiy tanlaydi. Y = f (x) ni hisoblab chiqadi.
2. O2 obyekti y ning raqamini O1 ob'ektiga yo'naltiradi. Ob'ektni O1 x sonini tiklay olmaydi.
3. O1 ob'ekti katta intervaldan [0, q - 1] raqamdan tasodifiy tanlanadi. Ob'ektni O1 tasodifiy bit w ni tanlaydi. Bu harakatlar 1-talab bilan bir vaqtda amalga oshirilishi mumkin.
4. O1 ob'ekti s = h (z, y, w) ni hisoblaydi. Bu yerda z zichlik "maskalanishi" uchun va y - "O2" obyekti tomonidan O1 ob'ektining harakatlarining to'g'riligini "tekshirish" uchun kerak.
5. O1 ob'ekti raqamlarni O2 ga yo'naltiradi. W bit O2 obyektiga yuboriladi, lekin u "b" da "yashirin". O2 obyekti bu bitni saqlab qololmaydi. Ob'ekt O2 tiklanolmaydi va z soni.
6. O2 obyekti tasodifiy bitni tanlaydi.
O2 obyekti O1 obyektiga bir oz c yuboradi. Yukni yuboring.
8. O1 ob'ekti z va bitni W ni O2 ob'ektiga yo'naltiradi. Yukni yuboring. Ob'ektni O1 allaqachon lotinlar sonini aniqlaydi: c + w (mod 2).
9. O2 obyekti t = h (z, y, w) ni hisoblab chiqadi. Bu erda z va w faqat O1'den olingan va y, 1-sonli hisoblab chiqilgan.
10. O2 ob'ekti avval O1 ob'ektidan olingan t va s ni taqqoslaydi.
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) va h (z, v, w) = vwgz (mod p).
Bu erda x, w, z ning "yashirin" qiymatlari daraja darajasida bo'lib, uni topish uchun alohida logaritmikatsiya muammosini hal qilish kerak, bular uchun asosan to'liq ro'yxatga olishning eng yaxshi algoritmi noma'lum.
Ikkala ob'ektda ham p, q, g sobit bo'lishi kerak. R soni uzoq boshlang'ich raqam. Q raqami ham uzoq boshlang'ich soni, ya'ni p - 1 sonining bo'linishi. 1 gacha bo'lmagan g g p g g = 1 (mod p) holatiga mos keladi.
Yig'ilgan muammolarni hal qiladigan tarqalgan algoritmlar.
Tarqatilayotgan algoritmlarni rivojlantirishning yo'nalishlaridan biri yuqori samarali kompyuter hisoblanadi. Bunday holatda, tarqalgan kompyuter tizimi bitta muammolarni hal qiladigan kuchli hisob-kitobnoma sifatida ishlatiladi. Mashhur bir misol, DES shifrlash algoritmi tomonidan yaratilgan parolni "buzish" vazifasidir. Shifrlash kaliti ma'lum bo'lsa, matnning parolini hal qilish qiyin emas.
Agar kalit aniq bo'lmasa, unda shovqinni qo'pol kuch ishlatishga urinish mumkin. Biroq, eng tezkor protsessorli kompyuterlar uchun ham qo'pol kuch usuli juda uzoq vaqt talab etadi.
Muammoni yechish juda protsessorli kompyuter yordamida tezlashtirilishi mumkin. Bunday holda, hisoblar parallel holga keltiriladi, ya'ni. Bir vaqtning o'zida bir xil yoki turli guruhlarni bajaradigan barcha protsessorlar ushbu muammoni echishda qatnashadilar. Qanday parallellashish jarayoni juda protsessorli kompyuterning arxitekturasiga bog'liq. Ideal vaziyatda n tarkibida n protsessorlar mavjud bo'lsa, hisob-kitoblarning tezlashishi n vaqtga yaqin qiymatga ega bo'lishi mumkin. Aslida, algoritmlar to'liq parallel holga kelmagan, ayrim protsessorlar ma'lum vaqt ichida bo'sh bo'lishi mumkin va ishlash n vaqtdan kamroq.
Zamonaviy multiprosessor mashinalari o'nlab va yuzlab protsessorlar, minglab shaxsiy protsessorlarga ega. Ammo bunday noyob mashinalar juda qimmatga tushadi, maxsus superkompyuter markazlarida yoki harbiy tashkilotlarda o'rnatiladi va odatdagi foydalanuvchilar uchun doimo mavjud emas.
Shu bilan bir qatorda, global aloqa tarmoqlari bilan bog'langan va shaxslar va turli tashkilotlarga tegishli alohida kompyuterlardan foydalanish. Kompyuterlar nisbatan kam ishlashga ega bo'lishi mumkin, biroq tarmoqdagi o'nlab yoki yuz minglab kompyuterlarni bir muammo hal qilish uchun bir xil superkompyuterning ta'sirini yaratadi, lekin ehtimol yanada kuchli.
Bunday tarqatilgan kompyuter tizimi yuqorida keltirilgan parolni hal qilish vazifasi uchun ishlatilgan. Bu "qattiq" tizim emas edi - kompyuterlar ixtiyoriy ravishda ishlatilgan, har qanday vaqtda har qanday kompyuter o'chirilishi mumkin. Biroq, yangi kompyuterlar ham ishlaydiganlarga qo'shilishlari mumkin edi. Kompleks muammolarni hal qilish uchun global kompyuterlar tarmog'idan foydalanish g'oyasi va tegishli texnologiyaga "Grid" nomi berilgan. Agar veb-global axborot resurslariga kirish imkoni bo'lsa, Grid global hisoblash (resurs) resurslariga kirishni ta'minlashi kerak. Tizimdan foydalanadigan asosiy loyihalar hozirgi vaqtda zarralar fizikasida eksperimental ma'lumotlarning katta soni (terabaytlar, pentabaytlar), astronomiyada kuzatuvlar, biologiyada inson genomining talqini bilan bog'liq.