Параллельное программирование — различия между версиями
(/* 5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство,…) |
м (rollbackEdits.php mass rollback) |
||
(не показано 98 промежуточных версий 11 участников) | |||
Строка 1: | Строка 1: | ||
[[Категория: Параллельное программирование]] | [[Категория: Параллельное программирование]] | ||
=Программирование параллельных и распределенных систем= | =Программирование параллельных и распределенных систем= | ||
+ | *[[Базовые определения и формализм]] | ||
+ | *[[Алгоритмы взаимного исключения]] | ||
+ | *[[Стек Трайбера]] | ||
+ | *[[Формализм распределённых систем]] | ||
+ | |||
==6 семестр== | ==6 семестр== | ||
− | ===Введение | + | ===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью=== |
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]] | *[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]] | ||
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]] | *[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]] | ||
Строка 14: | Строка 19: | ||
===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы=== | ===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы=== | ||
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]] | *[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]] | ||
− | *[[Параллельное программирование: Матричные часы|Матричные часы]] | + | *[[Параллельное программирование: Матричные часы|Матричные часы]] (билет весной 2019 года убран) |
===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы=== | ===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы=== | ||
Строка 28: | Строка 33: | ||
*[[Кворум рушащейся стенки]] | *[[Кворум рушащейся стенки]] | ||
− | === | + | ===11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя=== |
*[[Срез, согласованный срез]] | *[[Срез, согласованный срез]] | ||
*[[Алгоритм Чанди-Лампорта]] | *[[Алгоритм Чанди-Лампорта]] | ||
− | === | + | ===13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы=== |
*[[Глобальные свойства системы]] | *[[Глобальные свойства системы]] | ||
− | *[[Слабый конъюнктивный предикат]] | + | *[[Слабый конъюнктивный предикат (WCP)]] |
+ | *[[Централизованный алгоритм для WCP]] | ||
+ | *[[Распределенный алгоритм для WCP]] | ||
− | === | + | ===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена=== |
+ | * [[Диффундирующие вычисления]] | ||
+ | * [[Алгоритм Дейкстры и Шолтена]] | ||
− | + | ===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки=== | |
− | |||
− | === | ||
*[[Локально стабильный предикат]] | *[[Локально стабильный предикат]] | ||
*[[Согласованный интервал]] | *[[Согласованный интервал]] | ||
*[[Барьерная синхронизация (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 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. === |
+ | * [[Иерархия ошибок в распределённых системах]] | ||
+ | * [[Асинхронные и синхронные распределённые системы]] | ||
+ | * [[Консенсус в распределённой системе]] | ||
+ | * [[Алгоритм Бен-Ора]] | ||
− | + | === 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.=== | |
+ | * [[Консенсус в распределённой системе]] | ||
+ | * [[Replicated State Machine]] | ||
+ | * [[Paxos]] | ||
− | + | === 30 билет. Raft. Алгоритм, его свойства.=== | |
+ | * [[Консенсус в распределённой системе]] | ||
+ | * [[Replicated State Machine]] | ||
+ | * [[Raft]] | ||
− | + | === 31 билет. Транзакции в распределенных системах. 2 Phase Locking=== | |
+ | * [[Транзакции в распределённых системах]] | ||
+ | * [[2 Phase Locking]] | ||
− | + | === 32 билет. Транзакции в распределенных системах. 2 Phase Commit.=== | |
− | * | + | * [[Транзакции в распределённых системах]] |
− | * | + | * [[2 Phase Commit]] |
− | + | === 33 билет. СAP теорема (концепции, подходы, без доказательства)=== | |
+ | * [[CAP теорема]] | ||
− | === | + | === 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)=== |
+ | * [[Gossip-протоколы]] | ||
+ | * [[CRDT]] | ||
− | + | === 35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева === | |
+ | * [[Иерархия ошибок в распределённых системах]] | ||
+ | * [[Самостабилизирующиеся алгоритмы]] | ||
==Ссылки== | ==Ссылки== | ||
<references/> | <references/> |
Текущая версия на 19:33, 4 сентября 2022
Программирование параллельных и распределенных систем
- Базовые определения и формализм
- Алгоритмы взаимного исключения
- Стек Трайбера
- Формализм распределённых систем
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 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора.
- Иерархия ошибок в распределённых системах
- Асинхронные и синхронные распределённые системы
- Консенсус в распределённой системе
- Алгоритм Бен-Ора