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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎4. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы)
м (rollbackEdits.php mass rollback)
 
(не показано 99 промежуточных версий 11 участников)
Строка 1: Строка 1:
 
[[Категория: Параллельное программирование]]
 
[[Категория: Параллельное программирование]]
 
=Программирование параллельных и распределенных систем=
 
=Программирование параллельных и распределенных систем=
 +
*[[Базовые определения и формализм]]
 +
*[[Алгоритмы взаимного исключения]]
 +
*[[Стек Трайбера]]
 +
*[[Формализм распределённых систем]]
 +
 
==6 семестр==
 
==6 семестр==
−
===Введение (вне билетов). Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
+
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
 
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
 
*[[Параллельное программирование: Распределенные вычислительные системы|Распределенные системы]]
 
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
 
*[[Параллельное программирование: Масштабируемость параллельных и распределенных систем|Масштабируемость параллельных и распределенных систем]]
Строка 14: Строка 19:
 
===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
 
===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
 
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
 
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
−
*[[Параллельное программирование: Матричные часы|Матричные часы]]
+
*[[Параллельное программирование: Матричные часы|Матричные часы]] (билет весной 2019 года убран)
  
 
===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
 
===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
Строка 21: Строка 26:
 
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]
 
*[[Параллельное программирование: Алгоритм Рикарта-Агравалы|Алгоритм Рикарта-Агравалы]]
  
−
===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)]]
  
−
===16. Синхронные системы. Проблема двух генералов. Невозможность получения общей информации===
+
===23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast===
 +
* [[Иерархия ошибок в распределённых системах]]
 +
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Консенсус в распределённой системе]]
 +
* [[Переформулировки консенсуса в распределённой системе]]
  
−
'''Задача двух генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния двух систем по ненадежному каналу связи. ([https://ru.wikipedia.org/wiki/%D0%97%D0%B0%D0%B4%D0%B0%D1%87%D0%B0_%D0%B4%D0%B2%D1%83%D1%85_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D0%BB%D0%BE%D0%B2 Википедия])
+
===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
  
−
Два процесса в случае ненадежного канала не могут достичь [[консенсус|консенсуса]].
+
* [[Иерархия ошибок в распределённых системах]]
 +
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Консенсус в распределённой системе]]
 +
* [[Консенсус в синхронных системах]]
  
−
Consider the last such message that was successfully delivered. If that last message had not been successfully delivered, then one general at least (presumably the receiver) would decide not to attack. From the viewpoint of the sender of that last message, however, the sequence of messages sent and delivered is exactly the same as it would have been, had that message been delivered.
+
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
 +
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Проблема византийских генералов]]
 +
* [[Алгоритм Лампорта-Шостака-Пиза]] для решения проблемы
  
−
Для недетерминнированного - аналогично. Посмотрим на "успешную" последовательность.
+
===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===
−
И отменим успешность последнего сообщения. Для 1-ого все ок, для 2-ого все испортилось.
+
* [[Асинхронные и синхронные распределённые системы]]
 +
* [[Проблема византийских генералов]]
 +
* [[Невозможность византийского консенсуса]] при 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»