Параллельное программирование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎2 билет)
м (rollbackEdits.php mass rollback)
 
(не показаны 152 промежуточные версии 18 участников)
Строка 1: Строка 1:
 +
[[Категория: Параллельное программирование]]
 
=Программирование параллельных и распределенных систем=
 
=Программирование параллельных и распределенных систем=
−
===1 билет===
+
*[[Базовые определения и формализм]]
 +
*[[Алгоритмы взаимного исключения]]
 +
*[[Стек Трайбера]]
 +
*[[Формализм распределённых систем]]
 +
 
 +
==6 семестр==
 +
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
 
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
 
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
 
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
 
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
 
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
 
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
−
===2 билет===
+
 
 +
===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/>

Текущая версия на 19:33, 4 сентября 2022

Содержание

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

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

Ссылки

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Параллельное_программирование&oldid=85458»