Материал из Викиконспекты
Программирование параллельных и распределенных систем
6 семестр
Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью
1-2 билеты. Логические часы Лампорта и векторные часы, их свойства
3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы
5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы
8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)
11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя
13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы
15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена
16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки
17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка
20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина
22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)
23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast
24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов
25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1
26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1
27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора.
28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.
30 билет. Raft. Алгоритм, его свойства.
31 билет. Транзакции в распределенных системах. 2 Phase Locking
32 билет. Транзакции в распределенных системах. 2 Phase Commit.
33 билет. СAP теорема (концепции, подходы, без доказательства)
34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)
35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева
Ссылки
