KNOW INTUIT, Лекция, Разпределени задачи и алгоритми

Целта G е свързана със системата S, в името на която функционира системата. Тази цел се задава от самата система (ако системата е активна) или се задава отвън. За постигане на целта системата трябва да реши проблем - някаква математическа формализация на целта с ясно дефиниран набор от изходни данни и необходими резултати.

Предполага се, че решението на проблема се получава с помощта на алгоритъм, т.е. предписания, посочващи изпълнителя (изпълнителите) и последователността от елементарни стъпки, които трябва да бъдат предприети от изпълнителите.

Разпределената система генерира разпределена задача, тъй като първоначалните данни за задачата възникват в различни точки в пространството. Освен това в различни точки се изискват определени резултати от решаването на проблема. Често задачата може да бъде разделена на набор от подзадачи, някои от тях могат да бъдат концентрирани: всички първоначални данни възникват в една точка в пространството и там се изискват и резултатите от решаването на подзадачата.

Разпределен проблем се решава чрез разпределен алгоритъм, който събира входни данни от различни точки и изпраща резултатите от изчислението до различни точки. Допълнителен фактор при разпределението на алгоритъма може да бъде наличието на няколко изпълнители, разположени в различни точки на пространството (разпределен изпълнител).

Известно е, че алгоритъмът работи освен с изходните данни и с междинни данни, а в големите системи работи и с бази данни. За един разпределен алгоритъм естествено възниква въпросът как ще бъдат организирани тези данни – под формата на концентрирана или разпределена база данни?

Един тип разпределени алгоритми са протоколите. Протоколът се характеризира с това, че има поне две страни, разделени от комуникационен канал. От всяка страна се изпълнявалокален (концентриран) алгоритъм Ak . Локалният алгоритъм A1 се изпълнява до определен момент от време, когато се нуждае от данни от друг локален алгоритъм A2, за да продължи работата си. Той изпраща заявка за данни към локалния алгоритъм A2 чрез комуникационната линия. Алгоритъм A2 отговаря, като препраща съобщението по връзката. След това локалният алгоритъм A1 продължава работата си.

Протоколите обикновено играят техническа роля и служат за установяване на режимите на получаване / предаване на данни между отдалечени обекти. В изчислителна гледна точка локалните алгоритми - части от протокола - не са сложни.

Специален вид разпределени алгоритми са криптографските протоколи. Те имат за цел да докажат на едната или и на двете страни, че са тези, за които се представят, за обмен на поверителна информация и други подобни цели.

Помислете за един от най-простите криптографски протоколи - разпределени алгоритми.

В различни точки на пространството има два обекта, O1 и O2, всеки от които решава своята част (P1 или P2) от общата задача P. В същото време, в допълнение към желанието за решаване на общ проблем, обектите имат свои собствени специфични задачи, Q1 и Q2. Така обект O1 едновременно решава задачи P1 и Q1, а обект O2 решава задачи P2 и Q2. И ако задачите P1 и P2 са съвместими и се допълват, то задачите Q1 и Q2 си противоречат.

Следователно обектите O1 и O2 си сътрудничат, но в същото време се конкурират. И можем също така да кажем, че обектите се конкурират, но са принудени да си сътрудничат. Зависи как да подчертаем коя от задачите, Pi или Qi, е по-важна за обекта Oi.

Описаната ситуация се среща много често. Университетите са заинтересовани от решаването на проблема за подобряване на подготовката на специалисти и в тази задача тесътрудничат. В същото време всяка година университетите се състезават за талантливи кандидати. Научните организации често провеждат съвместни изследвания в пресечната точка на своите интереси (в пресечната точка на науките). Но те също се състезават в разпределението на финансите. Две различни подразделения на фирмата работят за постигане на общите цели на фирмата, но всяко от тях иска да получи повече развитие във фирмата, отколкото другото подразделение. Като цяло приятели-съперници. частична конкуренция.

В нашия проблем обектите O1 и O2 трябва да стигнат до общо компромисно решение в интерес на решаването на проблем P. Да предположим, че има две еквивалентни (от гледна точка на задача P) решения. Едното от тях подхожда и на обекта O1, а другото на обекта O2. Тогава обектите O1 и O2 решават да теглят жребий. Това може да се направи: напишете всяко решение на вашия лист хартия, навийте парчетата хартия в тръба, превъртете в машината за лотария и издърпайте едно от парчетата хартия. Това ще бъде компромисно решение.

Трудността се състои в това, че обектите O1 и O2 са на голямо разстояние един от друг и не могат да извършат процедурата с лото барабана. Процедурата с лотарията се извършва на едно място, възможно е и по концентрирана система. Нашата система е разпределена.

Процедурата на лотарийния барабан може да бъде изпълнена от обект O1 и да докладва резултата на обект O2. Въпреки това, обект O2 не се доверява напълно на обект O1. Дори телевизионно предаване на процедурата не е категорично доказателство - може да е умело монтиран запис.

Резултатът е следният. Нека означим едно от решенията с числото 0, другото с числото 1. Всеки от обектите, независимо един от друг, трябва да назове някакво цяло число ni в диапазона, например от 0 до 99. След това обектите си разменят числата ni и изчисляват резултата n1 + n2 (mod 2) . Това ще е решението, т.е.номер 0 или 1.

Обектите не могат да изпращат числата ni един на друг абсолютно едновременно. Някой първи ще изпрати номера си и ще бъде в неизгодна позиция. Например, O1 препрати своя номер n1 към O2, който се интересува решението "1" да спечели. Тогава O2, знаейки n1, решава уравнението n1 + n2 (mod 2) = 1 по отношение на променливата n2 и изпраща на O1 намерената стойност на n2. Решаването на уравнението не отнема почти никакво време: след като получи четно число от O1, O2 трябва да отговори нечетно и обратно.

Тази несправедливост трябва да се поправи. В същото време е ясно, че така или иначе една от страните в обмена на съобщения първа ще изпрати номера си. Необходимо е да се уверите, че втората страна няма достатъчно време да "избере отговор".

Обектите O1 и O2 могат да се съгласят, че цялата процедура на "хвърляне на жребий" от разстояние трябва да бъде завършена за няколко минути. Ако едновременно и двата обекта знаят, че изборът на отговор изисква няколко часа суперкомпютърна работа, тогава те могат да бъдат спокойни, че решението не е "настроено" от другата страна.

За осигуряване на такива времеви параметри при изчисленията трябва да се използва функцията f(x), чиято стойност y = f(x) с известен аргумент x може да бъде изчислена относително бързо. Но за да решим уравнението f(x) = y , т.е. намирането на неизвестно x с известна стойност на y не е лесно. Освен това е желателно да не са известни никакви математически методи за решаване на това уравнение, освен изчерпателно изброяване или подобни по сложност.

Разбира се, областта на дефиниране на функцията f(x) трябва да бъде много голяма, за да направи изчерпателното изброяване практически невъзможно. Площта на два елемента, 0 и 1, е малка, площта от 0 до 99 също е недостатъчна. Целите числа, с които трябва да работите, трябва да са в десетичен знакзаписи от най-малко 150-200 цифри или най-малко 512 бита в двоична нотация. Такива числа се наричат "дълги".

Нека f(x) и h(z, v, w) са две такива трудни за връщане функции. Във функцията h(z, v, w) първите два аргумента са дълги числа, а третият е побитов. Функциите f и h са известни на обектите O1 и O2 и те имат алгоритми за бързо изчисляване на стойностите на тези функции за дадени стойности на аргументите, но не могат бързо да обърнат тези функции, т.е. решаване на уравнения.

Алгоритъмът за разпределено хвърляне на партиди се състои от следните стъпки.

Обектът O2 произволно избира число x от голям интервал [0, q – 1] . Изчислява y = f(x) .
Обект O2 изпраща числото y към обект O1. Обект O1 няма да може да възстанови числото x.
Обектът O1 произволно избира число z от голям интервал [0, q – 1] . Обект O1 избира произволен бит w. Тези действия могат да се извършват едновременно с т.1.
Обектът O1 оценява s = h(z, y, w). Числото z тук е необходимо, за да "маскира" бита w, а числото y е необходимо, за да "провери" от обекта O2 правилността на действията на обекта O1.
Обект O1 изпраща числото s към обект O2. Бит w се изпраща към обект O2, но е "скрит" в числото s. Обектът O2 няма да може да възстанови този бит. Обектът O2 също няма да може да възстанови числото z.
Обект O2 избира случаен бит c .
Обект O2 изпраща бит c към обект O1. Отворено препращане.
Обект O1 изпраща числото z и бит w към обект O2. Отворено препращане. Обектът O1 вече може да определи резултата от хвърлянето: c + w (mod 2) .
Обектът O2 изчислява t = h(z, y, w). Тук z и w току-що са получени от O1 и y е изчислено в стъпка 1.
Обект O2 сравнява t и s, получени преди това от обект O1.
Ако t = s, тогава обект O2 оценява резултата от хвърлянетопартиди: c + w (mod 2) .

Функциите f и h могат да бъдат различни. По-специално се използват следните функции:

f(x) = g x (mod p) и h(z, v, w) = v w g z (mod p) .

Тук „тайните“ стойности на x, w, z са в експоненти и за да се намерят, е необходимо да се реши проблема с дискретния логаритъм, за който не е известен ефективен алгоритъм, който е по същество по-добър от изчерпателното търсене.

Константите p , q , g трябва да са известни и на двата обекта. Числото p е дълго просто число. Числото q също е дълго просто число, което е делител на числото p - 1. Число g, което не е равно на 1, удовлетворява условието g q = 1 (mod p) .

Разпределени алгоритми, които решават групирани проблеми.

Едно от направленията в развитието на разпределените алгоритми са високопроизводителните изчисления. В този случай разпределената компютърна система се използва като един мощен компютър, който решава един проблем. Добре известен пример е проблемът с "разбиването" на шифър, създаден от алгоритъма за криптиране DES. Дешифрирането на текста не е трудно, ако ключът за криптиране е известен. Ако ключът не е известен, тогава може да се направи опит за дешифриране чрез изчерпателно търсене. Но методът на груба сила отнема много време дори за най-бързите еднопроцесорни компютри.

Решението на проблема може да бъде ускорено с помощта на многопроцесорен компютър. В този случай изчисленията са паралелни, т.е. всички процесори едновременно, изпълнявайки еднакви или различни инструкции, участват в решаването на проблема. Как точно се осъществява паралелизирането зависи от архитектурата на многопроцесорния компютър. Ако в състава му има n процесора, в идеална ситуация ускорението на изчисленията може да достигне стойност, близка до n пъти. Реално погледнато, алгоритмите не са напълно паралелизирани, частпроцесорите могат да бъдат неактивни в отделни периоди от време и производителността се увеличава с по-малко от n пъти.

Съвременните многопроцесорни машини имат десетки и стотици процесори, отделните машини имат хиляди процесори. Но такива уникални машини са много скъпи, те се инсталират в специални суперкомпютърни центрове или във военни организации и не винаги са достъпни за обикновените потребители.

Алтернатива е използването на отделни компютри, свързани с глобални комуникационни мрежи и притежавани от физически лица и различни организации. Компютрите може да имат относително ниска производителност, но използването на няколко десетки или стотици хиляди компютъра в мрежата наведнъж за решаване на един проблем създава ефекта на същия суперкомпютър, но може би дори по-мощен.

Точно такава разпределена компютърна система е използвана за споменатата задача за дешифриране. Това не беше "твърда" система - компютрите се използваха на доброволна основа, по всяко време всеки компютър можеше да излезе от системата. Но по същия начин нови компютри могат да се присъединят към вече работещите.

Идеята и свързаната с нея технология за използване на глобална мрежа от компютри за решаване на сложен проблем се нарича Grid. Ако Мрежата предоставя достъп до глобални информационни ресурси, тогава Гридът трябва да предоставя достъп до глобални изчислителни (обработващи) ресурси. Основните проекти, използващи Grid, в момента са свързани с обработката на голямо количество (терабайти, пентабайти) експериментални данни във физиката на елементарните частици, наблюденията в астрономията и декодирането на човешкия геном в биологията.