Паралельне програмування

Зміст

6 семестр [ред.]

Вступ. Масштабованість розподілених та паралельних систем, закон Амдала. Відмінності розподілених систем від систем з пам'яттю, що розділяється [ред.]

1-2 квитки. Логічний годинник Лампорту та векторний годинник, їх властивості [ред.]

3-4 квитки. Годинник з прямою залежністю (і їх властивості) і матричний годинник [ред.]

5-7 квитки. Взаємний виняток у розподіленій системі. Централізований, алгоритм Лампорта, алгоритм Рікарта та Агравали [ред.

8-10 квитки. Взаємний виняток у розподіленій системі. Алгоритм філософів, що обідають, на основі токена, на основі кворуму (проста більшість, стіни, що руйнуються) [ред.

11-12 квитки. Узгоджений глобальний стан (узгоджений зріз). Алгоритм Чанді-Лампорт. Запам'ятовування повідомлень на стороні відправника та одержувача [ред.]

13-14 квитки. Глобальні характеристики. Стабільні та нестабільні предикати. Слабкий кон'юнктивний предикат. Централізований та розподілений алгоритми [ред.]

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

Алгоритм Дейкстри та Шолтена в англійській вікіпедії [1] .

16 квиток. Локально-стабільні предикати, узгоджені інтервали, бар'єрна синхронізація (3 алгоритми). Застосування для визначення взаємного блокування [ред.]

Кожен процес [math]P_i[/math] підтримує свою частину графа очікування (ребра, що з нього виходять), а також прапорець changed, який дорівнює true, якщо його частина графа змінилася з останнього повідомлення координатору. Координатор періодично опитує процеси, отримуючи їхні графи. Процес відповідає новим графом, якщо є зміна,а інакше шле не змінюється. Координатор збирає весь граф очікування. Якщо в ньому є цикл, він надсилає процесам запит на зміну. Якщо всі процеси в циклі відповіли незмінені, дідлок знайдений.

Розглянемо два зрізи:

  • коли взаємно блокуючі процеси надіслали координатору свої графи;
  • коли вони прислали йому незмінили.

Ці зрізи не обов'язково узгоджені, але вони бар'єрно-синхронізовані (через повідомлення координатору і назад), а отже утворюють узгоджений інтервал. Тому з-поміж них є узгоджений зріз [math]G[/math] , оскільки стан процесів у циклі не змінювалося усім інтервалі, й у першому зрізі предикат виконаний, для [math]G[/math] він також виконаний.

17-18 квитки. Впорядкування повідомлень. Визначення, ієрархія порядків. Алгоритм для FIFO. Алгоритм для причинно-узгодженого порядку [ред.]

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

Алгоритм FIFO ґрунтується на нумерації повідомлень. Псевдокод алгоритму для причинно-узгодженого порядку. Разом із повідомленням відправляємо матрицю M: M[i, j] — кількість повідомлень, надісланих процесом i процесу j.

19 квиток. Впорядкування повідомлень. Визначення, ієрархія порядків. Алгоритм для синхронного порядку [ред.]

Алгоритм для синхронного порядку ґрунтується на ієрархії процесів. Упорядкуємо процеси за номером, назвемо повідомленнявеликим, якщо номер відправника більший за номер одержувача, імалимінакше. Процес може бути вактивномуабопасивному стані. Спочатку всі активні. Процес може надіслати велике повідомлення лише якщо він активний. Після відправки він стає пасивним і не може ні надсилати, ні приймати повідомлення, доки не отримає від одержувача ack.

Щоб надіслати повідомлення більшому процесу [math]P_j[/math] , процес [math]P_i[/math] спочатку посилає службове повідомлення,запит. У відповідь [math]P_j[/math] відправляєдозвіл; він може зробити це лише в активному стані. Дозволивши, він стає пасивним і залишається в цьому стані, доки не отримує повідомлення, яке дозволив.

20-21 квитки. Загальний порядок (total order). Алгоритми Лампорта та Скіна [ ред .

22 квиток. Ієрархія помилок у розподілених системах. Відмова вузла в асинхронній системі - неможливість консенсусу (доказ Фішера-Лінча-Патерсона) [ред.

  1. Відмова одного або кількох вузлів (crash)
  2. Відмова одного або кількох каналів (link failure)
  3. Ненадійна доставка повідомлень (omission)
  4. Візантійська помилка (byzantine failure) (зламаний процес може слати будь-яке сміття)

Ієрархія помилок будується з того, що сильніші помилки можуть імітувати менш сильні - візантійська помилка імітує поведінку при ненадійній доставці повідомлень, ненадійна доставка може імітувати повну відмову каналу, а відмова всіх каналів до вузла - відмова вузла.

Неможливість консенсусу в асинхронній системі з відмовою вузла (FLP) (Фішер-Лінч-Патерсон)

  • Система асинхронна (немає часу доставки повідомлення)
  • (Один) вузол може відмовити (crash)
  • Консенсус треба досягти закінцевий час
  • Детермінований алгоритм консенсусу

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

Відповідно, можна дійти консенсусу, якщо:

  • зробити мережу синхронною (обмежити час доставки повідомлень)
  • зробити алгоритм недетермінованим (випадковим)
  • послабити вимоги у яких алгоритмі може бути прогрес (тобто. він повинен завершуватися)

TODO: доказ із презентації Єлізарова. Інфо: http://bailonga.es/tpmtp/lecture09.pdf + презентація Р.Єлізарова

23 квиток. Консенсус у розподілених системах. Застосування консенсусу: вибір лідера, terminating reliable broadcast [ред.]

Результат FLP про неможливість консенсусу вірний навіть якщо процесу дозволено робити операцію «атомарної передачі» повідомлення відразу кілька процесів, бо немає гарантії що всі процеси опрацюють його. Якщо є гарантія отримання повідомлення всіма процесами (чи жодним), така операція називається Terminating Reliable Broadcast (TRB). Маючи TRB можна тривіально з його основі написати алгоритм консенсусу (процес [math]P_0[/math] розсилає всім свій біт, вони погоджуються цей біт, якщо отримали повідомлення, інакше на 0).

  • Кожен процес пропонує себе. Консенсус визначає лідера для подальшого розподіленого алгоритму

2) Terminating Reliable Broadcast

  • Потрібно дійти консенсусу про те, чи треба обробляти отримане повідомлення
  • Таким чином, задача TRB еквівалентна задачі консенсусу

24 квиток. Синхронні системи. Алгоритм для консенсусу у разі відмови заданої кількості вузлів [ред.]

Як відомо з FLP, за всіх вимогконсенсус неможливий. Приберемо вимогу асинхронності (будь-яке повідомлення доходить за деякий кінцевий час).

Нехай у системі єnвузлів, кожному задано початкове число. Нехай їх максимумfможуть у будь-який момент впасти(crash). Тоді можна вирішити завдання консенсусу заf+1раундів:

  • Робимо у кожному вузлі вектор ізnзначень (своє записуємо, інші поки невідомі)
  • У кожному раунді кожен вузол посилає кожному всі свої числа (або тільки ті, які не посилав раніше - не має значення)
  • Процеси записують числа, що прийшли, у свій вектор
  • Післяf+1- го раунду вибираємо мінімум із відомих чисел.

Чому це працює? Припустимо, що процеси a та b вибрали різні мінімуми. Значить, є значення v, яке є в одного з процесів і немає в іншого (нехай у b). Але якщо у нас був раунд без збоїв, то всі процеси дізнаються всі числа, що є в даний момент - тому що всі повідомлення дійшли. А збоїв було не більше f – протиріччя.

25 квиток. Синхронні системи. Проблема візантійських генералів. Алгоритм для N>=4, f=1. Пояснити ідею узагальнення для f> 1 [ = 4, f = 1. Пояснити ідею узагальнення для f > 1»">редагувати ]

Проблема візантійських генералів - дійти нетривіального консенсусу N процесів, якщо серед них є f збійних (можуть поводитися як завгодно/контролюються зловмисниками).

Алгоритм Лампорта (і ще 2 чоловік): Вважаємо, що процеси мають номери. Процес 1 - "генерал" - розсилає всім речення - 0 або 1. І після цього мовчить (приймає свою пропозицію).

При f=0 решта ( " лейтенанти " ) просто приймають пропозицію.

При f=1 всі "лейтенанти" розсилають всім "лейтенантам" повідомлення "генерал сказав X".Тепер у кожного процесу є N-1 повідомлення виду "A сказав, що генерал сказав X", включаючи своє (Я сказав, що генерал сказав X). Вибираємо варіант, який зустрічається більше разів, або 0 якщо однаково. Якщо збійний процес - генерал, то решта процесів отримають однакову кількість 0 і 1 у повідомленнях і виберуть однаковий варіант. Якщо збійний процес - лейтенант, решта процесів отримають більше вірних повідомлень, ніж невірних і виберуть варіант, посланий генералом.

При f=2+ робимо всього f раундів розсилки повідомлень між лейтенантами (при f=2 посилаються повідомлення "B сказав, що A сказав, що генерал сказав X"), і f раундів вибору більшості всередині кожного процесу (тобто f =2 процес має N-1 повідомлення "B сказав, що А сказав . " і вирішує, що саме сказав A вибором варіанта, який більше зустрічається).

Якщо всі процеси рівноправні, то 0 раунді розсилки все вважають себе " генералами " , та був робимо консенсус на вихідних значеннях кожного.

Вибір варіанта зрештою дасть правильний варіант саме тому, що N > 3f.

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

Завдання візантійських генералів— уявний експеримент, покликаний проілюструвати проблему синхронізації стану систем у разі, коли комунікації вважаються надійними, а процесори — ні. (Вікі)

Проблема візантійських генералів формулюється так: єnгенералів з якихfє зрадниками. Як дійти консенсусу чесним генералам?

Відомо, що заn> 3fзавдання вирішуване, а інакше ні.

  • Кожен розсилає кожному своє число;
  • Кожен розсилає кожному зібрані значення;
  • Уотримані вектори кожен проводить голосування.

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

Доказ від Єлізарова:

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

програмування

Тоді якщо вважати 2 верхніх процесу робітниками, а 2 нижніх - одним збійним, верхні повинні дійти консенсусу на 0. Аналогічно, якщо вважати 2 нижніх процесу робітниками, а 2 верхніх - одним збійним - нижні приходять до консенсусу на 1.

І якщо ми вважаємо робітниками 2 правих, а 2 лівих - одним збійним (що ведуть себе як пара з верхнього робітника і нижнього робітника) - то верхній правий прийде до консенсусу на 0 разом з уявним верхнім сусідом, а нижній правий - до консенсусу на 1 с уявним нижнім сусідом. Fail.

Тому такого алгоритму немає і консенсус при N=3 і f=1 неможливий.

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

28 квиток. Paxos. Алгоритм, його властивості. [ред.]

29 квиток. Paxos. Загальні принципи. Основні зміни. [ред.]

30 квиток. Транзакції у розподілених системах. 2 Phase Locking [ред.]

31 квиток. Транзакції у розподілених системах. 2 Phase Commit. [ред.]

32 квиток. СAP теорема (концепції, підходи, без доказів) [ред.]

33 квиток. Gossip. СRDT і дельта-CRDT (концепції, приклади алгоритмів, див. роботу з семінару) [ред.

CRDT (Conflict-Free Replicated Data Type) — об'єкт, який можна реплікувати на багато вузлів та оновлюватипаралельно без координації між вузлами.

Реплікація на основі стану

Отримавши оновлення від клієнта, репліка спочатку оновлює локальний стан, потім надсилає цей стан іншій репліці. Та застосовує функцію merge, щоб поєднати свій стан з отриманим і відправляє його ще одній репліці, і т.д.

Достатні умови узгодженості:

1. Безліч можливих станів утворює напіврешітку, тобто. частково впорядковане безліч з операцією найменшої верхньої грані, причому merge реалізує цю операцію;

2. Оновлення зростають.

Реплікація на основі операцій

Репліка посилає не весь стан, лише оновлення всім реплікам. Узгодженість можна гарантувати, якщо оновлення є комутативними. Крім того, потрібно, щоб кожна операція була доставлена ​​рівно один раз.