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

Материал из Викиконспекты
Перейти к: навигация, поиск
(25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1)
(30 билет. Raft. Алгоритм, его свойства.)
 
(не показано 16 промежуточных версий этого же участника)
Строка 50: Строка 50:
  
 
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
 
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
TODO
 
  
 
*[[Локально стабильный предикат]]
 
*[[Локально стабильный предикат]]
 
*[[Согласованный интервал]]
 
*[[Согласованный интервал]]
 
*[[Барьерная синхронизация (3 алгоритма)]]
 
*[[Барьерная синхронизация (3 алгоритма)]]
* Применение для определения дедлока.
+
*[[Определение взаимной блокировки]]
Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания (ребра, которые из него исходят), а также флажок changed, который равен true, если его часть графа поменялась с последнего  сообщения координатору. Координатор периодически опрашивает процессы, получая их графы. Процесс отвечает новым графом, если есть изменение, а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если в нем есть цикл, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, дедлок найден.
 
 
 
Рассмотрим два среза:
 
* когда взаимно блокирующие процессы прислали координатору свои графы;
 
* когда они прислали ему notChanged.
 
Эти срезы не обязательно согласованны, но они барьерно-синхронизированы (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез <tex>G</tex>, а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для <tex>G</tex> он также выполнен.
 
  
 
===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
 
===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
Строка 70: Строка 63:
  
 
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
 
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
TODO? (CHECK)
 
 
 
*[[Общий порядок сообщений]]
 
*[[Общий порядок сообщений]]
 
*[[Алгоритм Лампорта]]
 
*[[Алгоритм Лампорта]]
Строка 91: Строка 82:
 
===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
 
===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
  
Как известно из FLP, при всех требованиях консенсус невозможен. Уберем требование асинхронности (любое сообщение доходит за некоторое конечное время).
+
* [[Иерархия ошибок в распределённых системах]]
 
+
* [[Асинхронные и синхронные распределённые системы]]
Пусть в системе имеется ''n'' узлов, каждому задано начальное число.
+
* [[Консенсус в распределённой системе]]
Пусть из них максимум ''f'' могут в любой момент упасть навсегда (crash), "воскрешения" не разрешены.
+
* [[Консенсус в синхронных системах]]
Тогда [[Консенсус в распределённой системе#Решение при отсутствии отказов|базовый алгоритм]] всё ещё не работает, хотя мы и можем "дождаться всех сообщений":
 
узел может отказать в процессе рассылки предложений: кому-то послал, а кому-то не успел.
 
 
 
Но можно решить задачу консенсуса за ''f+1'' фазу (секция 15.4.1 на странице 240 в Garg):
 
 
 
*Делаем в каждом узле множество из ''n'' значений (своё записываем, остальные пока неизвестны)
 
*В каждом раунде каждый узел посылает каждому все свои числа (или только те, которые не посылал ранее - без разницы)
 
*Процессы записывают пришедшие числа в свой вектор
 
*После ''f+1'' - го раунда выбираем минимум из известных чисел.
 
 
 
Докажем, что в конце у всех неотказавших процессов будут одинаковые множества значений.
 
Если мы на каждом шаге рассылаем вообще всё множество, то это просто: у нас по принципу Дирихле есть раунд без ошибок, в нём все друг другу всё рассказали, а дальше множества уже не меняются.
 
 
 
А если рассылаем только новые данные, то интереснее (см. Garg; на лекции вроде не было).
 
Пусть у неотказавшего процесса $P_i$ после раунда $f+1$ есть значение $x$.
 
Тогда если он его получил в раунде $f$ или меньшем, то в раунде $f+1$ он разошлёт его всем остальным и все неотказавшие его успешно получат.
 
Более интересный случай: процесс $P_i$ получил значение $x$ только в раунде $f+1$, а в предыдущих $f$ не получал.
 
Предположим, что есть процесс $P_j$, который так и не получил значение $x$ к раунду $f+1$.
 
Тогда у нас имеется $f+1$ процесс, которые по очереди отказывали на предыдущих шагах, успевая передать друг другу $x$, но не успевая передать их $P_i$ или $P_j$.
 
И только $(f+1)$-й отказавший процессор смог передать $P_i$, но не $P_j$.
 
Но у нас всего максимум $f$ отказов, противоречие.
 
 
 
Итого нам требуется $O((f + 1)N^2)$ сообщений на консенсус.
 
  
 
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
 
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
Строка 125: Строка 93:
  
 
===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===
 
===26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1===
 
+
* [[Асинхронные и синхронные распределённые системы]]
'''Задача византийских генералов''' — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)
+
* [[Проблема византийских генералов]]
 
+
* [[Невозможность византийского консенсуса]] при N=3, f=1.
Проблема византийских генералов формулируется так: имеется ''n'' генералов из которых ''f'' являются предателями. Как прийти к консенсусу честным генералам?
 
 
 
Известно, что при ''n'' > 3''f'' задача решаема, а иначе нет.
 
 
 
*Каждый рассылает каждому свое число;
 
*Каждый рассылает каждому собранные значения;
 
*В полученных векторах каждый проводит голосование.
 
 
 
Можно доказать, например, что при ''n'' = 3, ''f'' = 1 консенсус невозможен.
 
 
 
Доказательство от Елизарова:
 
 
 
Пусть каждому процессу подаётся число 0 или 1 на вход(могут быть разными на разных процессах). Задача - прийти к нетривиальному консенсусу всем работающим процессам на одном значении, которое было дано на вход хотя бы одному работающему процессу. (Сильный консенсус)
 
 
 
[[Файл:byzantine.png|frame|right]] Предположим обратное. Пусть существует алгоритм консенсуса. Тогда расставим 4 ноды с этим алгоритмом, подадим верхним на вход 0, и нижним = 1.
 
 
 
Тогда если считать 2 верхних процесса рабочими, а 2 нижних - одним сбойным, верхние обязаны прийти к консенсусу на 0. Аналогично, если считать 2 нижних процесса рабочими, а 2 верхних - одним сбойным - нижние приходят к консенсусу на 1.
 
 
 
И если мы считаем рабочими 2 правых, а 2 левых - одним сбойным(ведущим себя как пара из верхнего рабочего и нижнего рабочего) - то верхний правый придет к консенсусу на 0 вместе с воображаемым верхним соседом, а нижний правый - к консенсусу на 1 с воображаемым нижним соседом. Fail.
 
 
 
Поэтому такого алгоритма нет, и консенсус при N=3 и f=1 невозможен.
 
  
 
=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
 
=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
=== 28 билет. Paxos. Алгоритм, его свойства.===
+
* [[Иерархия ошибок в распределённых системах]]
=== 29 билет. Paxos. Общие принципы. Основные модификации.===
+
* [[Асинхронные и синхронные распределённые системы]]
=== 30 билет. Транзакции в распределенных системах. 2 Phase Locking===
+
* [[Консенсус в распределённой системе]]
=== 31 билет. Транзакции в распределенных системах. 2 Phase Commit.===
+
* [[Алгоритм Бен-Ора]]
=== 32 билет. СAP теорема (концепции, подходы, без доказательства)===
 
=== 33 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
 
CRDT (Conflict-Free Replicated Data Type) &mdash; объект, который можно реплицировать на много узлов и обновлять параллельно без координации между узлами.
 
  
'''Репликация на основе состояния'''
+
=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===
 +
* [[Консенсус в распределённой системе]]
 +
* [[Replicated State Machine]]
 +
* [[Paxos]]
  
Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике. Та применяет функцию merge, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д..  
+
=== 30 билет. Raft. Алгоритм, его свойства.===
 +
* [[Консенсус в распределённой системе]]
 +
* [[Replicated State Machine]]
 +
* [[Raft]]
  
Достаточные условия согласованности:
+
=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
 +
* [[Транзакции в распределённых системах]]
 +
* [[2 Phase Locking]]
  
1. Множество возможных состояний образует полурешетку, т.е. частично упорядоченное множество с операцией наименьшей верхней грани, причем merge реализует эту операцию;
+
=== 32 билет. Транзакции в распределенных системах. 2 Phase Commit.===
 +
* [[Транзакции в распределённых системах]]
 +
* [[2 Phase Commit]]
  
2. Обновления возрастают.
+
=== 33 билет. СAP теорема (концепции, подходы, без доказательства)===
 +
* [[CAP теорема]]
  
'''Репликация на основе операций'''
+
=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
 +
* [[Gossip-протоколы]]
 +
* [[CRDT]]
  
Реплика посылает не все состояние, а только обновление всем репликам. Согласованность можно гарантировать, если обновления коммутативны. Кроме того, требуется чтобы каждая операция была доставлена ровно один раз.
+
=== 35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева ===
 
+
* [[Иерархия ошибок в распределённых системах]]
todo дельта-CRDT
+
* [[Самостабилизирующиеся алгоритмы]]
  
 
==Ссылки==
 
==Ссылки==
 
<references/>
 
<references/>

Текущая версия на 09:06, 4 июня 2019

Содержание

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

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

Ссылки[править]