1632
правки
Изменения
м
#Отказ узла=== 35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева ===#Отказ связи* [[Иерархия ошибок в распределённых системах]]#Неустойчивая связь / пропуск пакетов#Византийская ошибка (сломавшийся процесс может слать любой мусор)* [[Самостабилизирующиеся алгоритмы]]
rollbackEdits.php mass rollback
[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
*[[Базовые определения и формализм]]*[[Алгоритмы взаимного исключения]]*[[Стек Трайбера]]*[[Формализм распределённых систем]] ==6 семестр=1 билет====Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
===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 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===* [[Иерархия ошибок в распределённых системах]]* [[Асинхронные и синхронные распределённые системы]]* [[Консенсус в распределённой системе]]* [[Алгоритм Бен-Ора]] === 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 теорема]]
===434 билет. Взаимное исключение в распределенной системеGossip. Централизованный, алгоритм Лампорта, алгоритм Рикарта СRDT и Агравалы======5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)======6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя======7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы======8. Диффундирующие вычисления. Останов. Алгоритм Дейксты и Шолтена======9. Локальнодельта-стабильные предикаты, согласованные интервала, барьерная синхронизация CRDT (3 алгоритма). Применение для определения взаимной блокировки======10. Упорядочивание сообщений. Определенияконцепции, иерархия порядков. Алгоритм для причинно-согласованного порядка======11. Упорядочивание сообщений. Определенияпримеры алгоритмов, иерархия порядковсм. Алгоритм для синхронного порядка======12. Общий порядок (total orderработу с семинара). Алгоритмы Лампорта и Скина======13. Выбор лидера. Алгоритм Чанди* [[Gossip-Робертса, и алгоритм Хирчберга-Синклера===протоколы]]===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===* [[CRDT]]
===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов======16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации=Ссылки=====17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы======18. Синхронные системы. Проблема византийских генералов. Алгоритм для N <references/>= 4, f = 1. Объяснить обобщение для f > 1===
