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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (→‎14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство))
м (rollbackEdits.php mass rollback)
 
(не показано 106 промежуточных версий 12 участников)
Строка 1: Строка 1:
 
[[Категория: Параллельное программирование]]
 
[[Категория: Параллельное программирование]]
 
=Программирование параллельных и распределенных систем=
 
=Программирование параллельных и распределенных систем=
 +
*[[Базовые определения и формализм]]
 +
*[[Алгоритмы взаимного исключения]]
 +
*[[Стек Трайбера]]
 +
*[[Формализм распределённых систем]]
 +
 
==6 семестр==
 
==6 семестр==
−
===1. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
+
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
 
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
 
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
 
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
 
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
 
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
 
*[[Параллельное программирование: Закон Амдала| Закон Амдала]]
  
−
===2. Логические часы Лампорта и векторные часы, их свойства===
+
===1-2 билеты. Логические часы Лампорта и векторные часы, их свойства===
 
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
 
*[[Параллельное программирование: Частичный порядок| Частичный порядок]]
 
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
 
*[[Параллельное программирование: Логические часы Лампорта| Логические часы Лампорта]]
 
*[[Параллельное программирование: Векторные часы| Векторные часы]]
 
*[[Параллельное программирование: Векторные часы| Векторные часы]]
  
−
===3. Часы с прямой зависимостью (и их свойства) и матричные часы===
+
===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
 
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
 
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
−
*[[Параллельное программирование: Матричные часы|Матричные часы]]
+
*[[Параллельное программирование: Матричные часы|Матричные часы]] (билет весной 2019 года убран)
  
−
===4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
+
===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
 
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
 
*[[Параллельное программирование: Централизованный алгоритм взаимного исключения|Централизованный алгоритм]]
 
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
 
*[[Параллельное программирование: Алгоритм Лампорта взаимного исключения|Алгоритм Лампорта]]
 
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]
 
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]
  
−
===5. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===
+
===8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)===
  
 
*[[Задача обедающих философов]]
 
*[[Задача обедающих философов]]
Строка 28: Строка 33:
 
*[[Кворум рушащейся стенки]]
 
*[[Кворум рушащейся стенки]]
  
−
===6. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя===
+
===11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя===
  
 
*[[Срез, согласованный срез]]
 
*[[Срез, согласованный срез]]
 
*[[Алгоритм Чанди-Лампорта]]
 
*[[Алгоритм Чанди-Лампорта]]
  
−
===7. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
+
===13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы===
  
 
*[[Глобальные свойства системы]]
 
*[[Глобальные свойства системы]]
−
*[[Слабый конъюнктивный предикат]]
+
*[[Слабый конъюнктивный предикат (WCP)]]
 +
*[[Централизованный алгоритм для WCP]]
 +
*[[Распределенный алгоритм для WCP]]
  
−
===8. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
+
===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
 +
* [[Диффундирующие вычисления]]
 +
* [[Алгоритм Дейкстры и Шолтена]]
  
−
Алгоритм Дейкстры и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>.
+
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
−
 
 
−
===9. Локально-стабильные предикаты, согласованные интервала, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
 
  
 
*[[Локально стабильный предикат]]
 
*[[Локально стабильный предикат]]
 
*[[Согласованный интервал]]
 
*[[Согласованный интервал]]
 
*[[Барьерная синхронизация (3 алгоритма)]]
 
*[[Барьерная синхронизация (3 алгоритма)]]
 +
*[[Определение взаимной блокировки]]
  
−
===10. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для причинно-согласованного порядка===
+
===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
−
Порядок сообщений:
+
* [[Иерархия порядков сообщений]]
−
# асинхронный
+
* [[Алгоритм для FIFO порядка]]
−
# FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены)
+
* [[Алгоритм для причинно-согласованного порядка]]
−
# причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком)
+
* [[Алгоритм для синхронного порядка]]
−
# синхронный
 
  
−
===11. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
+
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
−
===12. Общий порядок (total order). Алгоритмы Лампорта и Скина===
+
*[[Общий порядок сообщений]]
−
*[[Total order]]
 
 
*[[Алгоритм Лампорта]]
 
*[[Алгоритм Лампорта]]
 
*[[Алгоритм Скина]]
 
*[[Алгоритм Скина]]
  
−
===13. Выбор лидера. Алгоритм Чанди-Робертса, и алгоритм Хирчберга-Синклера===
+
===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===
−
 
 
−
'''Алгоритм Чанди-Робертса''' (Chang and Roberts) выбора лидера <ref>http://en.wikipedia.org/wiki/Chang_and_Roberts_algorithm</ref>.
 
−
 
 
−
Пусть процессы находятся в кольце.
 
−
Посылаем свой номер налево по кольцу.
 
−
При получении номера справа посылаем налево максимум из своего номера и полученного справа.
 
−
Если полученный справа номер является нашим номером, то заканчиваем работу.
 
−
 
 
−
'''Алгоритм Хирчберга-Синклера''' <ref>http://en.wikipedia.org/wiki/HS_algorithm</ref> <ref>http://web.cs.gc.cuny.edu/~vmitsou/presentation.pdf слайды 16-18</ref>.
 
−
 
 
−
===14. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство)===
 
−
 
 
−
#Отказ узла
 
−
#Отказ связи
 
−
#Неустойчивая связь / пропуск пакетов
 
−
#Византийская ошибка (сломавшийся процесс может слать любой мусор)
 
−
 
 
−
Отказ одного узла в распределенной системе ведет к невозможности консенсуса. Решением является уход от асинхронизации, накладывание ограничений на время ответа.
 
−
 
 
−
Также решение - уйти от требования детерминированности алгоритма.
 
−
 
 
−
===15. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
 
  
−
Пусть в системе имеется ''n'' узлов.
+
* [[Иерархия ошибок в распределённых системах]]
−
Пусть из них максимум ''f'' не работают.
+
* [[Асинхронные и синхронные распределённые системы]]
−
Тогда можно решить задачу консенсуса:
+
* [[Консенсус в распределённой системе]]
 +
* [[Теорема Фишера-Линча-Патерсона (FLP)]]
  
−
*Каждый узел посылает каждому свое число;
+
===23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast===
−
*Процессы запоминают пришедшие числа;
+
* [[Иерархия ошибок в распределённых системах]]
−
*Новые для себя числа процессы рассылают дальше;
+
* [[Асинхронные и синхронные распределённые системы]]
−
*Каждый процесс выбирает минимально известное ему число.
+
* [[Консенсус в распределённой системе]]
 +
* [[Переформулировки консенсуса в распределённой системе]]
  
−
(возможно, стоит дописать)
+
===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
  
−
===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===
+
* [[Иерархия ошибок в распределённых системах]]
 +
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Консенсус в распределённой системе]]
 +
* [[Консенсус в синхронных системах]]
  
−
'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. (Википедия)
+
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
 +
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Проблема византийских генералов]]
 +
* [[Алгоритм Лампорта-Шостака-Пиза]] для решения проблемы
  
−
Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].
+
===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===
 +
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Проблема византийских генералов]]
 +
* [[Невозможность византийского консенсуса]] при N=3, f=1.
  
−
===17. Синхронные системы. Проблема византийских генералов. Невозможность решения при N=3, f=1. Формулировка общей теоремы===
+
=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
 +
* [[Иерархия ошибок в распределённых системах]]
 +
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Консенсус в распределённой системе]]
 +
* [[Алгоритм Бен-Ора]]
  
−
'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)
+
=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===
 +
* [[Консенсус в распределённой системе]]
 +
* [[Replicated State Machine]]
 +
* [[Paxos]]
  
−
Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?
+
=== 30 билет. Raft. Алгоритм, его свойства.===
 +
* [[Консенсус в распределённой системе]]
 +
* [[Replicated State Machine]]
 +
* [[Raft]]
  
−
Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.
+
=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
 +
* [[Транзакции в распределённых системах]]
 +
* [[2 Phase Locking]]
  
−
*Каждый рассылает каждому свое число;
+
=== 32 билет. Транзакции в распределенных системах. 2 Phase Commit.===
−
*Каждый рассылает каждому собранные значения;
+
* [[Транзакции в распределённых системах]]
−
*В полученных векторах каждый проводит голосование.
+
* [[2 Phase Commit]]
  
−
Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.
+
=== 33 билет. СAP теорема (концепции, подходы, без доказательства)===
 +
* [[CAP теорема]]
  
−
===18. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить обобщение для f > 1===
+
=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
 +
* [[Gossip-протоколы]]
 +
* [[CRDT]]
  
−
Данный вопрос достаточно хорошо описан в английской версии.
+
=== 35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева ===
 +
* [[Иерархия ошибок в распределённых системах]]
 +
* [[Самостабилизирующиеся алгоритмы]]
  
 
==Ссылки==
 
==Ссылки==
 
<references/>
 
<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»