Параллельное программирование — различия между версиями
Yeputons (обсуждение | вклад) (/* 16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаи…) |
Yeputons (обсуждение | вклад) (→20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина) |
||
| Строка 63: | Строка 63: | ||
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина=== | ===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина=== | ||
| − | |||
| − | |||
*[[Общий порядок сообщений]] | *[[Общий порядок сообщений]] | ||
*[[Алгоритм Лампорта]] | *[[Алгоритм Лампорта]] | ||
Версия 20:04, 3 июня 2019
Содержание
- 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 билет. Paxos. Алгоритм, его свойства.
- 1.1.19 29 билет. Paxos. Общие принципы. Основные модификации.
- 1.1.20 30 билет. Raft. Алгоритм, его свойства.
- 1.1.21 31 билет. Транзакции в распределенных системах. 2 Phase Locking
- 1.1.22 32 билет. Транзакции в распределенных системах. 2 Phase Commit.
- 1.1.23 33 билет. СAP теорема (концепции, подходы, без доказательства)
- 1.1.24 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)
- 1.1.25 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 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора.
- Иерархия ошибок в распределённых системах
- Асинхронные и синхронные распределённые системы
- Консенсус в распределённой системе
- Алгоритм Бен-Ора
