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

Программирование параллельных и распределенных систем

6 семестр

Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью

• Распределенные системы
• Масштабируемость параллельных и распределенных систем
• Закон Амдала

1-2 билеты. Логические часы Лампорта и векторные часы, их свойства

• Частичный порядок
• Логические часы Лампорта
• Векторные часы

3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы

• Часы с прямой зависимостью
• Матричные часы

5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы

• Централизованный алгоритм
• Алгоритм Лампорта
• Алгоритм Рикарта-Агравалы

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

• Задача обедающих философов
• Кворум
• Кворум простого большинства
• Кворум рушащейся стенки

11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя

• Срез, согласованный срез
• Алгоритм Чанди-Лампорта

13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы

• Глобальные свойства системы
• Слабый конъюнктивный предикат (WCP)
• Централизованный алгоритм для WCP
• Распределенный алгоритм для WCP

15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена

TODO

Алгоритм Дейкстры и Шолтена в английской википедии.

16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки

TODO

• Локально стабильный предикат
• Согласованный интервал
• Барьерная синхронизация (3 алгоритма)

17-18 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка

TODO

Порядок сообщений:

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

Алгоритм FIFO основан на нумерации сообщений. Алгоритм для причинно-согласованного порядка основан на матричных часах.

19 билет. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка

TODO

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

20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина

TODO? (CHECK)

• Total order
• Алгоритм Лампорта
• Алгоритм Скина

?? билет. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера

Алгоритм Чанди-Робертса (Chang and Roberts) выбора лидера .

Пусть процессы находятся в кольце. Посылаем свой номер налево по кольцу. При получении номера справа посылаем налево максимум из своего номера и полученного справа. Если полученный справа номер является нашим номером, то заканчиваем работу.

Алгоритм Хирчберга-Синклера .

22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)

TODO

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

Теорема FLP (Фишер-Линч-Патерсон): Для асинхронной системы N потоков с хотя бы одним сбойным потоком нельзя построить решение задачи консенсуса.

Решением является уход от асинхронизации, накладывание ограничений на время ответа. Также решение - уйти от требования детерминированности алгоритма.

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

23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast

TODO

Результат FLP о невозможности консенсуса верен даже если, процессу разрешено делать операцию «атомарной передачи» сообщения сразу несколько процессам, ибо нет гарантии что все процессы обработают его. Если есть гарантия получения сообщения всеми процессами (или ни одним), то такая операция называется Terminating Reliable Broadcast (TRB). Имея TRB можно тривиально на его основе написать алгоритм консенсуса.

Применение консенсуса: 1) Выбор лидера

• Каждый процесс предлагает себя. Консенсус определяет лидера для последующего распределенного алгоритма

2) Terminating Reliable Broadcast

• Надо прийти к консенсусу о том, надо ли обрабатывать

полученное сообщение

• Таким образом, задача TRB эквивалентна задаче консенсуса

24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов

Пусть в системе имеется n узлов. Пусть из них максимум f не работают. Тогда можно решить задачу консенсуса:

• Каждый узел посылает каждому свое число;
• Процессы запоминают пришедшие числа;
• Новые для себя числа процессы рассылают дальше;
• Каждый процесс выбирает минимально известное ему число.

(возможно, стоит дописать)

25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1

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

Два процесса в случае ненадежного канала не могут достичь консенсуса.

Consider the last such message that was successfully delivered. If that last message had not been successfully delivered, then one general at least (presumably the receiver) would decide not to attack. From the viewpoint of the sender of that last message, however, the sequence of messages sent and delivered is exactly the same as it would have been, had that message been delivered.

Для недетерминнированного - аналогично. Посмотрим на "успешную" последовательность. И отменим успешность последнего сообщения. Для 1-ого все ок, для 2-ого все испортилось.

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

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

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

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

• Каждый рассылает каждому свое число;
• Каждый рассылает каждому собранные значения;
• В полученных векторах каждый проводит голосование.

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

Данный вопрос достаточно хорошо описан в английской версии.