Паралелно програмиране

Съдържание

6-ти семестър[редактиране]

Въведение. Мащабируемост на разпределени и паралелни системи, закон на Амдал. Разлики между разпределени системи и системи със споделена памет[редактиране]

1-2 билета. Логически часовник и векторен часовник на Lamport, техните свойства[редактиране]

3-4 билета. Часовници с пряка зависимост (и техните свойства) и матрични часовници[редактиране]

5-7 билета. Взаимно изключване в разпределена система. Централизиран, алгоритъм на Lamport, алгоритъм на Rikart и Agrawala[редактиране]

8-10 билета. Взаимно изключване в разпределена система. Алгоритъм за хранене на философи, базиран на токени, базиран на кворум (обикновено мнозинство, рушащи се стени) [редактиране]

11-12 билета. Съгласувано глобално състояние (последователен срез). Алгоритъм на Чанди-Лампорт. Съхраняване на съобщения от страна на подателя и получателя[редактиране]

13-14 билета. глобални свойства. Устойчиви и нестабилни предикати. Слаб съчинителен подлог. Централизирани и разпределени алгоритми[редактиране]

15 билет. Дифузно изчисление. Спри се. Алгоритъмът на Дейкстра и Шолтен[редактиране]

Алгоритъм на Дейкстра и Шолтен в английската wikipedia [1].

16 билет. Локално стабилни предикати, последователни интервали, бариерна синхронизация (3 алгоритъма). Приложение за откриване на блокиране[редактиране]

Всеки [math]P_i[/math] процес поддържа своята част от чакащата графика (ръбовете, които идват от нея), както и променения флаг, който е верен, ако неговата част от графиката се е променила след последното съобщение до координатора. Координаторът периодично анкетира процесите, получавайки техните графики. Процесът отговаря с нова графика, ако има промяна,в противен случай изпраща notChanged. Координаторът събира цялата графика на чакащите. Ако има цикъл, той изпраща заявка за промяна на процесите. Ако всички процеси в цикъла са отговорили с notChanged, блокирането е намерено.

Помислете за две части:

• когато взаимно блокиращите процеси изпращат своите графики на координатора;
• когато го изпратиха notChanged.

Тези срезове не са непременно последователни, но те са синхронизирани с бариера (поради съобщения до и от координатора) и по този начин образуват последователен интервал. Следователно между тях има последователен срез [math]G[/math] и тъй като състоянието на процесите в цикъла не се е променило през целия интервал и в първия срез предикатът е изпълнен, за [math]G[/math] той също е удовлетворен.

17-18 билета. Съобщения за поръчка. Дефиниции, йерархия на поръчките. Алгоритъм за FIFO. Алгоритъм за причинно-последователен ред[редактиране]

1. асинхронен (без ред)
2. FIFO (съобщенията достигат до получателя в реда, в който са му изпратени в смисъл на един поток)
3. причинно-следствен (ако едно съобщение е изпратено преди друго, то ще бъде доставено преди другото (в цялата система, а не в смисъл на една нишка, както е във FIFO)
4. синхронен (можете да създавате ръбове за предаване на съобщения без пресичане)

Алгоритъмът FIFO се основава на номерирането на съобщенията. Псевдокод на алгоритъм за причинно-последователен ред. Заедно със съобщението изпращаме матрица M: M[i, j] е броят съобщения, изпратени от процес i до процес j.

19 билет. Съобщения за поръчка. Дефиниции, йерархия на поръчките. Алгоритъм за синхронен ред[редактиране]

Алгоритъмът за синхронен ред се основава на йерархията на процесите. Подредете процесите по номера, обадете се на съобщениетоlarge, ако номерът на изпращача е по-голям от номера на получателя, иsmallв противен случай. Един процес може да бъдеактивенилипасивен. Първоначално всички са активни. Процесът може да изпрати голямо съобщение само ако е активен. След изпращане той става пасивен и не може да изпраща или получава съобщения, докато не получи потвърждение от получателя.

За да изпрати съобщение до по-големия процес [math]P_j[/math], процесът [math]P_i[/math] първо изпраща служебно съобщение,request. В отговор [math]P_j[/math] изпращаразрешение; може да направи това само в активно състояние. След като разреши, той става пасивен и остава в това състояние, докато не получи съобщението, че е разрешил.

20-21 билета. Обща поръчка (обща поръчка). Алгоритми на Lamport и Skene[редактиране]

22 билет. Йерархия на грешките в разпределени системи. Повреда на възел в асинхронна система - невъзможност за консенсус (доказателство на Фишер-Линч-Патерсън)[редактиране]

1. Повреда на един или повече възли (срив)
2. Неизправност на една или повече връзки (отказ на връзката)
3. Ненадеждна доставка на съобщение (пропускане)
4. Византийски провал (повреден процес може да изпрати всякакъв боклук)

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

Неуспешно постигане на консенсус в система за повреда на асинхронен възел (FLP) (Fisher-Lynch-Paterson)

• Системата е асинхронна (няма ограничение във времето за доставка на съобщения)
• (Един) възел може да се повреди (срив)
• Трябва да се постигне консенсускрайно време
• Алгоритъм за детерминиран консенсус

ТЕОРЕМА: Невъзможно е за N процеса да постигнат консенсус, дори за набор от стойности на два елемента 0 и 1

Съответно може да се постигне консенсус, ако:

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

TODO: доказателство от презентацията на Елизаров. Информация: http://bailonga.es/tpmtp/lecture09.pdf + презентация на Р. Елизаров

23 билет. Консенсус в разпределени системи. Прилагане на консенсус: избор на лидер, прекратяване на надеждно излъчване [редактиране]

Резултатът от FLP за липса на консенсус е верен, дори ако на даден процес е разрешено да "атомично изпрати" съобщение до множество процеси наведнъж, тъй като няма гаранция, че всички процеси ще го обработят. Ако има гаранция, че всички процеси (или нито един) ще получат съобщението, тогава такава операция се нарича Прекратяване на надеждно излъчване (TRB). Имайки TRB, можете тривиално да напишете алгоритъм за консенсус, базиран на него (процесът [math]P_0[/math] изпраща своя бит до всички, те се съгласяват с този бит, ако са получили съобщение, в противен случай до 0).

• Всеки процес предлага себе си. Консенсусът определя лидера за последващия разпределен алгоритъм

2) Прекратяване на надеждно излъчване

• Трябва да постигнем консенсус дали да обработим полученото съобщение
• По този начин проблемът TRB е еквивалентен на проблема с консенсуса

24 билет. Синхронни системи. Алгоритъм за консенсус в случай на повреда на даден брой възли[редактиране]

Както е известно от ФЛП, за всички изискванияконсенсус не е възможен. Нека премахнем изискването за асинхронност (всяко съобщение пристига за определено време).

Нека системата имаnвъзли, всеки с начален номер. Нека най-многоfот тях могат да се сринат във всеки момент. Тогава можем да решим проблема с консенсуса вf+1кръгове:

• Ние правим вектор отnстойности във всеки възел (записваме нашите собствени, останалите все още са неизвестни)
• Във всеки кръг всеки възел изпраща всички свои номера на всички (или само тези, които не е изпращал преди - няма значение)
• Процесите записват входящите числа в своя вектор
• Следf+1-тия кръг избираме минималното от известните числа.

Защо работи? Да приемем, че процесите a и b са избрали различни минимуми. Това означава, че има стойност v, която единият от процесите има, а другият не (нека b има). Но ако сме имали кръг без неуспехи, тогава всички процеси ще открият всички налични номера в момента - защото всички съобщения са достигнали. И имаше не повече от f неуспехи - противоречие.

25 билета. Синхронни системи. Проблемът на византийските пълководци. Алгоритъм за N >= 4, f = 1. Обяснете идеята за генерализация за f > 1 [ = 4, f = 1. Обяснете идеята за обобщение за f>gt; 1"">редактиране]

Проблемът на византийските пълководци е да стигнат до нетривиален консенсус от N процеса, ако сред тях има f лоши (те могат да се държат както си искат / контролират се от злосторници).

Алгоритъмът на Lamport (и още 2 души): Предполагаме, че процесите имат числа. Процес 1 - "общ" - изпраща оферта до всички - 0 или 1. След това мълчи (приема офертата си).

При f=0 всички останали ("лейтенанти") просто приемат предложението.

С f=1, всички "лейтенанти" изпращат на всички "лейтенанти" съобщението "генерал каза X".Сега всеки процес има N-1 съобщения като „A каза, че генералът каза X“, включително неговото собствено (аз казах, че генералът каза X). Избираме опцията, която се среща повече пъти или 0, ако е същата. Ако неуспешният процес е общ, тогава всички други процеси ще получат същия брой нули и 1 в съобщения и ще изберат същата опция. Ако неуспешният процес е лейтенантът, всички други процеси ще получат повече правилни съобщения от неправилните и ще изберат опцията, изпратена от генерала.

За f=2+ правим f кръга съобщения между лейтенантите (за f=2 се изпращат съобщения „B каза, че A каза, че генералът каза X“) и f кръга на избор на мнозинство в рамките на всеки процес (т.е. за f=2 процесът има N-1 съобщения „B каза, че A каза . “ и решава какво точно е казал A, като избира опцията, която се появява по-често).

Ако всички процеси са равни, тогава в 0-ия кръг на изпращане всеки се смята за "генерали" и след това постигаме консенсус относно първоначалните стойности на всеки.

Избирането на опция в крайна сметка ще ви даде правилната опция точно защото N > 3f.

26 билет. Синхронни системи. Проблемът на византийските пълководци. Невъзможност за решение за N = 3, f = 1 [редактиране]

Предизвикателството на византийските генералие мисловен експеримент, предназначен да илюстрира проблема със синхронизирането на състоянието на системите, когато се предполага, че комуникациите са надеждни, но процесорите не са. (Уики)

Проблемът за византийските генерали се формулира по следния начин: имаnгенерали, от коитоfса предатели. Как могат честните генерали да стигнат до консенсус?

Известно е, че заn> 3fзадачата е разрешима, иначе не.

• Всеки изпраща своя номер на всеки;
• Всеки изпраща на всеки събраните стойности;
• INполучени вектори, всеки има право на глас.

Може да се докаже, например, че заn= 3,f= 1, консенсусът е невъзможен.

Доказателство от Елизаров:

Нека на всеки процес се даде числото 0 или 1 като вход (те могат да бъдат различни за различните процеси). Задачата е да се стигне до нетривиален консенсус за всички работещи процеси относно една и съща стойност, която е била дадена като вход на поне един работещ процес. (Силен консенсус)

След това, ако считаме 2-та горни процеса за работещи, а 2-те най-долни процеса като един неуспешен, горните трябва да стигнат до консенсус относно 0. По същия начин, ако считаме, че 2-та най-долни процеса работят, а 2-та най-горни като един неуспешен, най-долните стигат до консенсус относно 1.

И ако считаме, че 2 десни работници работят, а 2 леви са един провал (държат се като двойка горен работник и долен работник) - тогава горният десен ще стигне до консенсус за 0 заедно с въображаем горен съсед, а долният десен ще стигне до консенсус за 1 с въображаем долен съсед. провалят се.

Следователно няма такъв алгоритъм и консенсусът с N=3 и f=1 е невъзможен.

27 билет. Недетерминирани консенсусни алгоритми. Алгоритъмът на Бен Ор. [редактиране]

28 билет. Паксос. Алгоритъм, неговите свойства. [редактиране]

29 билет. Паксос. Основни принципи. Основни модификации. [редактиране]

30 билета. Транзакции в разпределени системи. 2 фазово заключване[редактиране]

31 билета. Транзакции в разпределени системи. 2 Фаза Комит. [редактиране]

32 билет. CAP теорема (концепции, подходи, без доказателство) [редактиране]

33 билет. клюка. CRDT и делта-CRDT (концепции, примери за алгоритми, вижте документ за семинар) [редактиране]

CRDT (репликиран тип данни без конфликти) - обект, който може да бъде репликиран на много възли и актуализиранпаралелно без координация между възлите.

Репликация, базирана на състояние

При получаване на актуализация от клиента, репликата първо актуализира локалното състояние, след което изпраща това състояние на другата реплика. Той използва функцията за сливане, за да обедини своето състояние с полученото състояние и да го изпрати на друга реплика и т.н.

Достатъчни условия за последователност:

1. Наборът от възможни състояния образува полурешетка, т.е. частично подредено множество с операцията на най-малката горна граница и сливането изпълнява тази операция;

2. Актуализациите се увеличават.

Репликация, базирана на операции

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

---