Параллельное программирование

Программирование параллельных и распределенных систем

• Базовые определения и формализм
• Алгоритмы взаимного исключения
• Стек Трайбера
• Формализм распределённых систем

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 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева

• Иерархия ошибок в распределённых системах
• Самостабилизирующиеся алгоритмы