Содержание

1 Программирование параллельных и распределенных систем
- 1.1 6 семестр
- 1.2 Ссылки

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

6 семестр

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

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

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

Часы с прямой зависимостью
Матричные часы (билет весной 2019 года убран)

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

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

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

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

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

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

TODO

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

Рассмотрим два среза:

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

Эти срезы не обязательно согласованны, но они барьерно-синхронизированы (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез [math]G[/math], а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для [math]G[/math] он также выполнен.

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

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

TODO? (CHECK)

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

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

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

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

Асинхронные и синхронные распределённые системы
Проблема византийских генералов
Алгоритм Лампорта-Шостака-Пиза для решения проблемы

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

27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора.

28 билет. Paxos. Алгоритм, его свойства.

29 билет. Paxos. Общие принципы. Основные модификации.

30 билет. Raft. Алгоритм, его свойства.

31 билет. Транзакции в распределенных системах. 2 Phase Locking

32 билет. Транзакции в распределенных системах. 2 Phase Commit.

33 билет. СAP теорема (концепции, подходы, без доказательства)

CAP теорема

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

35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева

Ссылки

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