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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1)
(Метки: правка с мобильного устройства, правка из мобильной версии)
м (rollbackEdits.php mass rollback)
 
(не показаны 34 промежуточные версии 6 участников)
Строка 1: Строка 1:
 
[[Категория: Параллельное программирование]]
 
[[Категория: Параллельное программирование]]
 
=Программирование параллельных и распределенных систем=
 
=Программирование параллельных и распределенных систем=
 +
*[[Базовые определения и формализм]]
 +
*[[Алгоритмы взаимного исключения]]
 +
*[[Стек Трайбера]]
 +
*[[Формализм распределённых систем]]
 +
 
==6 семестр==
 
==6 семестр==
 
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
 
===Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью===
Строка 14: Строка 19:
 
===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
 
===3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы===
 
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
 
*[[Параллельное программирование: Часы с прямой зависимостью|Часы с прямой зависимостью]]
−
*[[Параллельное программирование: Матричные часы|Матричные часы]]
+
*[[Параллельное программирование: Матричные часы|Матричные часы]] (билет весной 2019 года убран)
  
 
===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
 
===5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы===
Строка 41: Строка 46:
  
 
===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
 
===15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена===
−
TODO
+
* [[Диффундирующие вычисления]]
−
 
+
* [[Алгоритм Дейкстры и Шолтена]]
−
Алгоритм Дейкстры и Шолтена в английской википедии<ref>http://en.wikipedia.org/wiki/Dijkstra-Scholten_algorithm</ref>.
 
  
 
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
 
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
−
TODO
 
  
 
*[[Локально стабильный предикат]]
 
*[[Локально стабильный предикат]]
 
*[[Согласованный интервал]]
 
*[[Согласованный интервал]]
 
*[[Барьерная синхронизация (3 алгоритма)]]
 
*[[Барьерная синхронизация (3 алгоритма)]]
−
* Применение для определения дедлока.
+
*[[Определение взаимной блокировки]]
−
Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания (ребра, которые из него исходят), а также флажок changed, который равен true, если его часть графа поменялась с последнего  сообщения координатору. Координатор периодически опрашивает процессы, получая их графы. Процесс отвечает новым графом, если есть изменение, а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если в нем есть цикл, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, дедлок найден.
 
−
 
 
−
Рассмотрим два среза:
 
−
* когда взаимно блокирующие процессы прислали координатору свои графы;
 
−
* когда они прислали ему notChanged.
 
−
Эти срезы не обязательно согласованны, но они барьерно-синхронизированы (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез <tex>G</tex>, а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для <tex>G</tex> он также выполнен.
 
−
 
 
−
===17-18 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка ===
 
−
TODO
 
  
−
Порядок сообщений:
+
===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
−
# асинхронный (нет порядка)
+
* [[Иерархия порядков сообщений]]
−
# FIFO (сообщения доходят получателю в том порядке, в котором они были ему отправлены в смысле одного потока)
+
* [[Алгоритм для FIFO порядка]]
−
# причинно-следственный (если одно сообщение было отправлено раньше другого, то оно будет доставлено раньше другого (в системе целиком, а не в смысле одного потока, как в FIFO)
+
* [[Алгоритм для причинно-согласованного порядка]]
−
# синхронный (можно выстроить ребра передачи сообщений без пересечений)
+
* [[Алгоритм для синхронного порядка]]
−
 
 
−
Алгоритм FIFO основан на нумерации сообщений.<br>
 
−
Псевдокод алгоритма для причинно-согласованного порядка. Вместе с сообщением отправляем матрицу M: M[i, j] &mdash; количество сообщений, отправленных процессом i процессу j.
 
−
  '''var'''
 
−
      M:array[l..N, 1..N] of integer initially 0;
 
−
  To send a message to <tex>P_j</tex>:
 
−
      M [i,j] := M[i,j] + 1;
 
−
      send M as part of the message;
 
−
  To receive a message with matrix W from Pj:
 
−
      '''enabled if''' W[j,i] = M [j,i] + 1 <tex>\land</tex> <tex> \forall k \neq j</tex> <tex>M[k, i] \geqslant W[k, i]</tex>
 
−
      M := max(M, W)
 
−
 
 
−
===19 билет. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для синхронного порядка===
 
−
 
 
−
Алгоритм для синхронного порядка основан на иерархии процессов.
 
−
Упорядочим процессы по номеру, назовем сообщение ''большим'', если номер отправителя больше номера получателя, и ''малым'' иначе.
 
−
Процесс может быть в ''активном'' или ''пассивном состоянии''. Изначально все активны.
 
−
Процесс может отправить большое сообщение, только если он активен. После отправки он становится пассивным и не может ни отправлять, ни принимать сообщения, пока не получит от получателя ack.
 
−
 
 
−
Чтобы отправить сообщение большему процессу <tex>P_j</tex>, процесс <tex>P_i</tex> сначала посылает служебное сообщение, ''запрос''. В ответ <tex>P_j</tex> отправляет ''разрешение''; он может сделать это только в активном состоянии. Разрешив, он становится пассивным и остается в этом состоянии, пока не получает сообщение, которое разрешил.
 
  
 
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
 
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
−
TODO? (CHECK)
+
*[[Общий порядок сообщений]]
−
 
 
−
*[[Total order]]
 
 
*[[Алгоритм Лампорта]]
 
*[[Алгоритм Лампорта]]
 
*[[Алгоритм Скина]]
 
*[[Алгоритм Скина]]
Строка 97: Строка 69:
 
===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===
 
===22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)===
  
−
#Отказ одного или нескольких узлов (crash)
+
* [[Иерархия ошибок в распределённых системах]]
−
#Отказ одного или нескольких каналов (link failure)
+
* [[Асинхронные и синхронные распределённые системы]]
−
#Ненадежная доставка сообщений (omission)
+
* [[Консенсус в распределённой системе]]
−
#Византийская ошибка (byzantine failure) (сломавшийся процесс может слать любой мусор)
+
* [[Теорема Фишера-Линча-Патерсона (FLP)]]
−
 
 
−
Иерархия ошибок строится по тому, что более сильные ошибки могут имитировать менее сильные - византийская ошибка имитирует поведение при ненадежной доставке сообщений, ненадежная доставка может имитировать полный отказ канала, а отказ всех каналов к узлу - отказ узла.
 
−
 
 
−
Невозможность консенсуса в асинхронной системе с отказом узла (FLP)(Фишер-Линч-Патерсон)
 
−
 
 
−
4 требования/предпосылки:
 
−
* Система асинхронна (нет предела времени доставки сообщения)
 
−
* (Один) узел может отказать (crash)
 
−
* Консенсус надо достичь за конечное время
 
−
* Детерминированный алгоритм консенсуса
 
−
 
 
−
'''ТЕОРЕМА''': Невозможно достичь консенсуса N процессам, даже на множестве значений из двух элементов 0 и 1
 
−
 
 
−
Соответственно, можно придти к консенсусу, если:
 
−
* сделать сеть синхронной (ограничить время доставки сообщений)
 
−
* сделать алгоритм недетерминированным (случайным)
 
−
* ослабить требования при которых в алгоритме обязан быть прогресс (т.е. он обязан завершаться)
 
−
 
 
−
TODO: доказательство из презентации Елизарова.
 
−
Инфо: http://bailonga.es/tpmtp/lecture09.pdf + презентация Р.Елизарова
 
  
 
===23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast===
 
===23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast===
−
TODO
+
* [[Иерархия ошибок в распределённых системах]]
−
 
+
* [[Асинхронные и синхронные распределённые системы]]
−
Результат FLP о невозможности консенсуса верен даже если, процессу разрешено делать операцию «атомарной передачи» сообщения сразу несколько процессам, ибо нет гарантии что все процессы обработают его. Если есть гарантия получения сообщения всеми процессами (или ни одним), то такая операция называется Terminating Reliable Broadcast (TRB). Имея TRB можно тривиально на его основе написать алгоритм консенсуса (процесс <tex>P_0</tex> рассылает всем свой бит, они соглашаются на этот бит, если получили сообщение, иначе на 0).
+
* [[Консенсус в распределённой системе]]
−
 
+
* [[Переформулировки консенсуса в распределённой системе]]
−
Применение консенсуса:
 
−
 
 
−
1) Выбор лидера
 
−
 
 
−
* Каждый процесс предлагает себя. Консенсус определяет лидера для последующего распределенного алгоритма
 
−
 
 
−
2) Terminating Reliable Broadcast
 
−
 
 
−
* Надо прийти к консенсусу о том, надо ли обрабатывать полученное сообщение
 
−
* Таким образом, задача TRB эквивалентна задаче консенсуса
 
  
 
===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
 
===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
  
−
Как известно из FLP, при всех требованиях консенсус невозможен. Уберем требование асинхронности (любое сообщение доходит за некоторое конечное время).
+
* [[Иерархия ошибок в распределённых системах]]
−
 
+
* [[Асинхронные и синхронные распределённые системы]]
−
Пусть в системе имеется ''n'' узлов, каждому задано начальное число.
+
* [[Консенсус в распределённой системе]]
−
Пусть из них максимум ''f'' могут в любой момент упасть(crash).
+
* [[Консенсус в синхронных системах]]
−
Тогда можно решить задачу консенсуса за ''f+1'' раундов:
 
−
 
 
−
*Делаем в каждом узле вектор из ''n'' значений (своё записываем, остальные пока неизвестны)
 
−
*В каждом раунде каждый узел посылает каждому все свои числа (или только те, которые не посылал ранее - без разницы)
 
−
*Процессы записывают пришедшие числа в свой вектор
 
−
*После ''f+1'' - го раунда выбираем минимум из известных чисел.
 
−
 
 
−
Почему это работает?
 
−
Допустим, что процессы a и b выбрали разные минимумы. Значит, есть значение v, которое есть у одного из процессов и нет у другого(пусть есть у b). Но если у нас был раунд без сбоев, то все процессы узнают все имеющиеся в данный момент числа - потому что все сообщения дошли. А сбоев было не больше f - противоречие.
 
  
 
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
 
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
−
 
+
* [[Асинхронные и синхронные распределённые системы]]
−
Проблема византийских генералов - прийти к нетривиальному консенсусу N процессам, если среди них есть f сбойных(могут вести себя как угодно/контролируются злоумышленниками).
+
* [[Проблема византийских генералов]]
−
 
+
* [[Алгоритм Лампорта-Шостака-Пиза]] для решения проблемы
−
Алгоритм Лампорта(и еще 2 человек):
 
−
Считаем, что у процессов есть номера. Процесс 1 - "генерал" - рассылает всем предложение - 0 или 1. И после этого молчит(принимает своё предложение).
 
−
 
 
−
При f=0 все остальные ("лейтенанты") просто принимают предложение.
 
−
 
 
−
При f=1 все "лейтенанты" рассылают всем "лейтенантам" сообщение "генерал сказал X". Теперь у каждого процесса есть N-1 сообщение вида "A сказал, что генерал сказал X", включая своё(Я сказал, что генерал сказал X). Выбираем вариант, который встречается больше раз, или 0 если одинаково. Если сбойный процесс - генерал, то все остальные процессы получат одинаковое количество 0 и 1 в сообщениях и выберут одинаковый вариант. Если сбойный процесс - лейтенант, все остальные процессы получат больше верных сообщений, чем неверных и выберут вариант, посланный генералом.
 
−
 
 
−
При f=2+ делаем всего f раундов рассылки сообщений между лейтенантами (при f=2 посылаются сообщения "B сказал, что A сказал, что генерал сказал X"), и f раундов выбора большинства внутри каждого процесса (т.е. для f=2 процесс имеет N-1 сообщение "B сказал, что А сказал ..." и решает, что именно сказал A выбором варианта, который больше встречается).
 
−
 
 
−
Если же все процессы равноправные, то в 0 раунде рассылки все считают себя "генералами", а потом делаем консенсус на исходных значениях каждого.
 
−
 
 
−
Выбор варианта в конечном итоге даст правильный вариант именно потому, что N > 3f.
 
  
 
===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; объект, который можно реплицировать на много узлов и обновлять параллельно без координации между узлами.
 
−
 
 
−
'''Репликация на основе состояния'''
 
  
−
Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике. Та применяет функцию merge, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д..  
+
=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===
 +
* [[Консенсус в распределённой системе]]
 +
* [[Replicated State Machine]]
 +
* [[Paxos]]
  
−
Достаточные условия согласованности:
+
=== 30 билет. Raft. Алгоритм, его свойства.===
 +
* [[Консенсус в распределённой системе]]
 +
* [[Replicated State Machine]]
 +
* [[Raft]]
  
−
1. Множество возможных состояний образует полурешетку, т.е. частично упорядоченное множество с операцией наименьшей верхней грани, причем merge реализует эту операцию;
+
=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
 +
* [[Транзакции в распределённых системах]]
 +
* [[2 Phase Locking]]
  
−
2. Обновления возрастают.
+
=== 32 билет. Транзакции в распределенных системах. 2 Phase Commit.===
 +
* [[Транзакции в распределённых системах]]
 +
* [[2 Phase Commit]]
  
−
'''Репликация на основе операций'''
+
=== 33 билет. СAP теорема (концепции, подходы, без доказательства)===
 +
* [[CAP теорема]]
  
−
Реплика посылает не все состояние, а только обновление всем репликам. Согласованность можно гарантировать, если обновления коммутативны. Кроме того, требуется чтобы каждая операция была доставлена ровно один раз.
+
=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===
 +
* [[Gossip-протоколы]]
 +
* [[CRDT]]
  
−
todo дельта-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»