1632
правки
Изменения
м
rollbackEdits.php mass rollback
[[Категория: Параллельное программирование]]
=Программирование параллельных и распределенных систем=
*[[Базовые определения и формализм]]
*[[Алгоритмы взаимного исключения]]
*[[Стек Трайбера]]
*[[Формализм распределённых систем]]
==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 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
* [[Иерархия ошибок в распределённых системах]]
* [[Асинхронные и синхронные распределённые системы]]
* [[Консенсус в распределённой системе]]
* [[Алгоритм Бен-Ора]]
=== 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/>
