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

Материал из Викиконспекты
Перейти к: навигация, поиск
(34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара))
(30 билет. Raft. Алгоритм, его свойства.)
 
(не показано 7 промежуточных версий этого же участника)
Строка 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)
 
 
 
*[[Общий порядок сообщений]]
 
*[[Общий порядок сообщений]]
 
*[[Алгоритм Лампорта]]
 
*[[Алгоритм Лампорта]]
Строка 112: Строка 103:
 
* [[Алгоритм Бен-Ора]]
 
* [[Алгоритм Бен-Ора]]
  
=== 28 билет. Paxos. Алгоритм, его свойства.===
+
=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===
=== 29 билет. Paxos. Общие принципы. Основные модификации.===
+
* [[Консенсус в распределённой системе]]
 +
* [[Replicated State Machine]]
 +
* [[Paxos]]
 +
 
 
=== 30 билет. Raft. Алгоритм, его свойства.===
 
=== 30 билет. Raft. Алгоритм, его свойства.===
 +
* [[Консенсус в распределённой системе]]
 +
* [[Replicated State Machine]]
 +
* [[Raft]]
 +
 
=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
 
=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===
 
* [[Транзакции в распределённых системах]]
 
* [[Транзакции в распределённых системах]]
Строка 129: Строка 127:
 
* [[Gossip-протоколы]]
 
* [[Gossip-протоколы]]
 
* [[CRDT]]
 
* [[CRDT]]
 
CRDT (Conflict-Free Replicated Data Type) &mdash; объект, который можно реплицировать на много узлов и обновлять параллельно без координации между узлами.
 
 
'''Репликация на основе состояния'''
 
 
Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике. Та применяет функцию merge, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д..
 
 
Достаточные условия согласованности:
 
 
1. Множество возможных состояний образует полурешетку, т.е. частично упорядоченное множество с операцией наименьшей верхней грани, причем merge реализует эту операцию;
 
 
2. Обновления возрастают.
 
 
'''Репликация на основе операций'''
 
 
Реплика посылает не все состояние, а только обновление всем репликам. Согласованность можно гарантировать, если обновления коммутативны. Кроме того, требуется чтобы каждая операция была доставлена ровно один раз.
 
 
todo дельта-CRDT
 
  
 
=== 35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева ===
 
=== 35 билет. Самостабилизирующиеся алгоритмы. Идея. Алгоритмы взаимного исключения и поиска остовного дерева ===

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

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