Параллельное программирование — различия между версиями
Yeputons (обсуждение | вклад) (→34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)) |
м (rollbackEdits.php mass rollback) |
||
| (не показано 8 промежуточных версий 2 участников) | |||
| Строка 50: | Строка 50: | ||
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки=== | ===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки=== | ||
| − | |||
*[[Локально стабильный предикат]] | *[[Локально стабильный предикат]] | ||
*[[Согласованный интервал]] | *[[Согласованный интервал]] | ||
*[[Барьерная синхронизация (3 алгоритма)]] | *[[Барьерная синхронизация (3 алгоритма)]] | ||
| − | * | + | *[[Определение взаимной блокировки]] |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка === | ===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка === | ||
| Строка 70: | Строка 63: | ||
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина=== | ===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина=== | ||
| − | |||
| − | |||
*[[Общий порядок сообщений]] | *[[Общий порядок сообщений]] | ||
*[[Алгоритм Лампорта]] | *[[Алгоритм Лампорта]] | ||
| Строка 112: | Строка 103: | ||
* [[Алгоритм Бен-Ора]] | * [[Алгоритм Бен-Ора]] | ||
| − | === 28 | + | === 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.=== |
| − | + | * [[Консенсус в распределённой системе]] | |
| + | * [[Replicated State Machine]] | ||
| + | * [[Paxos]] | ||
| + | |||
=== 30 билет. Raft. Алгоритм, его свойства.=== | === 30 билет. Raft. Алгоритм, его свойства.=== | ||
| + | * [[Консенсус в распределённой системе]] | ||
| + | * [[Replicated State Machine]] | ||
| + | * [[Raft]] | ||
| + | |||
=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking=== | === 31 билет. Транзакции в распределенных системах. 2 Phase Locking=== | ||
* [[Транзакции в распределённых системах]] | * [[Транзакции в распределённых системах]] | ||
Текущая версия на 19:33, 4 сентября 2022
Содержание
- 1 Программирование параллельных и распределенных систем
- 1.1 6 семестр
- 1.1.1 Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью
- 1.1.2 1-2 билеты. Логические часы Лампорта и векторные часы, их свойства
- 1.1.3 3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы
- 1.1.4 5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы
- 1.1.5 8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)
- 1.1.6 11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя
- 1.1.7 13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы
- 1.1.8 15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена
- 1.1.9 16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки
- 1.1.10 17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка
- 1.1.11 20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина
- 1.1.12 22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)
- 1.1.13 23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast
- 1.1.14 24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов
- 1.1.15 25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1
- 1.1.16 26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1
- 1.1.17 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора.
- 1.1.18 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.
- 1.1.19 30 билет. Raft. Алгоритм, его свойства.
- 1.1.20 31 билет. Транзакции в распределенных системах. 2 Phase Locking
- 1.1.21 32 билет. Транзакции в распределенных системах. 2 Phase Commit.
- 1.1.22 33 билет. СAP теорема (концепции, подходы, без доказательства)
- 1.1.23 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)
- 1.1.24 35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева
- 1.2 Ссылки
- 1.1 6 семестр
Программирование параллельных и распределенных систем
- Базовые определения и формализм
- Алгоритмы взаимного исключения
- Стек Трайбера
- Формализм распределённых систем
6 семестр
Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью
1-2 билеты. Логические часы Лампорта и векторные часы, их свойства
3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы
- Часы с прямой зависимостью
- Матричные часы (билет весной 2019 года убран)
5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы
8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)
11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя
13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы
- Глобальные свойства системы
- Слабый конъюнктивный предикат (WCP)
- Централизованный алгоритм для WCP
- Распределенный алгоритм для WCP
15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена
16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки
- Локально стабильный предикат
- Согласованный интервал
- Барьерная синхронизация (3 алгоритма)
- Определение взаимной блокировки
17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка
- Иерархия порядков сообщений
- Алгоритм для FIFO порядка
- Алгоритм для причинно-согласованного порядка
- Алгоритм для синхронного порядка
20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина
22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)
- Иерархия ошибок в распределённых системах
- Асинхронные и синхронные распределённые системы
- Консенсус в распределённой системе
- Теорема Фишера-Линча-Патерсона (FLP)
23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast
- Иерархия ошибок в распределённых системах
- Асинхронные и синхронные распределённые системы
- Консенсус в распределённой системе
- Переформулировки консенсуса в распределённой системе
24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов
- Иерархия ошибок в распределённых системах
- Асинхронные и синхронные распределённые системы
- Консенсус в распределённой системе
- Консенсус в синхронных системах
25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1
- Асинхронные и синхронные распределённые системы
- Проблема византийских генералов
- Алгоритм Лампорта-Шостака-Пиза для решения проблемы
26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1
- Асинхронные и синхронные распределённые системы
- Проблема византийских генералов
- Невозможность византийского консенсуса при N=3, f=1.
27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора.
- Иерархия ошибок в распределённых системах
- Асинхронные и синхронные распределённые системы
- Консенсус в распределённой системе
- Алгоритм Бен-Ора
