Параллельное программирование — различия между версиями
Yeputons (обсуждение | вклад) (→23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast) |
Yeputons (обсуждение | вклад) (→24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов) |
||
| Строка 94: | Строка 94: | ||
Пусть в системе имеется ''n'' узлов, каждому задано начальное число. | Пусть в системе имеется ''n'' узлов, каждому задано начальное число. | ||
| − | Пусть из них максимум ''f'' могут в любой момент упасть(crash). | + | Пусть из них максимум ''f'' могут в любой момент упасть навсегда (crash), "воскрешения" не разрешены. |
| − | Тогда | + | Тогда [[Консенсус в распределённой системе#Решение при отсутствии отказов|базовый алгоритм]] всё ещё не работает, хотя мы и можем "дождаться всех сообщений": |
| + | узел может отказать в процессе рассылки предложений: кому-то послал, а кому-то не успел. | ||
| − | *Делаем в каждом узле | + | Но можно решить задачу консенсуса за ''f+1'' фазу (секция 15.4.1 на странице 240 в Garg): |
| + | |||
| + | *Делаем в каждом узле множество из ''n'' значений (своё записываем, остальные пока неизвестны) | ||
*В каждом раунде каждый узел посылает каждому все свои числа (или только те, которые не посылал ранее - без разницы) | *В каждом раунде каждый узел посылает каждому все свои числа (или только те, которые не посылал ранее - без разницы) | ||
*Процессы записывают пришедшие числа в свой вектор | *Процессы записывают пришедшие числа в свой вектор | ||
*После ''f+1'' - го раунда выбираем минимум из известных чисел. | *После ''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=== | ||
Версия 18:04, 3 июня 2019
Содержание
- 1 Программирование параллельных и распределенных систем
- 1.1 6 семестр
- 1.1.1 Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью
- 1.1.2 1-2 билеты. Логические часы Лампорта и векторные часы, их свойства
- 1.1.3 3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы
- 1.1.4 5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы
- 1.1.5 8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)
- 1.1.6 11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя
- 1.1.7 13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы
- 1.1.8 15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена
- 1.1.9 16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки
- 1.1.10 17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка
- 1.1.11 20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина
- 1.1.12 22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)
- 1.1.13 23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast
- 1.1.14 24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов
- 1.1.15 25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1
- 1.1.16 26 билет. Синхронные системы. Проблема византийских генералов. Невозможность решения при N = 3, f = 1
- 1.1.17 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора.
- 1.1.18 28 билет. Paxos. Алгоритм, его свойства.
- 1.1.19 29 билет. Paxos. Общие принципы. Основные модификации.
- 1.1.20 30 билет. Транзакции в распределенных системах. 2 Phase Locking
- 1.1.21 31 билет. Транзакции в распределенных системах. 2 Phase Commit.
- 1.1.22 32 билет. СAP теорема (концепции, подходы, без доказательства)
- 1.1.23 33 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)
- 1.2 Ссылки
- 1.1 6 семестр
Программирование параллельных и распределенных систем
- Базовые определения и формализм
- Алгоритмы взаимного исключения
- Стек Трайбера
- Формализм распределённых систем
6 семестр
Введение. Масштабируемость распределенных и параллельных систем, закон Амдала. Отличия распределенных систем от систем с разделяемой памятью
1-2 билеты. Логические часы Лампорта и векторные часы, их свойства
3-4 билеты. Часы с прямой зависимостью (и их свойства) и матричные часы
- Часы с прямой зависимостью
- Матричные часы (билет весной 2019 года убран)
5-7 билеты. Взаимное исключение в распределенной системе. Централизованный, алгоритм Лампорта, алгоритм Рикарта и Агравалы
8-10 билеты. Взаимное исключение в распределенной системе. Алгоритм обедающих философов, на основе токена, на основе кворума (простое большинство, рушащиеся стены)
11-12 билеты. Согласованное глобальное состояние (согласованный срез). Алгоритм Чанди-Лампорта. Запоминание сообщений на стороне отправителя и получателя
13-14 билеты. Глобальные свойства. Стабильные и нестабильные предикаты. Слабый конъюнктивный предикат. Централизованный и распределенный алгоритмы
- Глобальные свойства системы
- Слабый конъюнктивный предикат (WCP)
- Централизованный алгоритм для WCP
- Распределенный алгоритм для WCP
15 билет. Диффундирующие вычисления. Останов. Алгоритм Дейкстры и Шолтена
16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки
TODO
- Локально стабильный предикат
- Согласованный интервал
- Барьерная синхронизация (3 алгоритма)
- Применение для определения дедлока.
Каждый процесс поддерживает свою часть графа ожидания (ребра, которые из него исходят), а также флажок changed, который равен true, если его часть графа поменялась с последнего сообщения координатору. Координатор периодически опрашивает процессы, получая их графы. Процесс отвечает новым графом, если есть изменение, а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если в нем есть цикл, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, дедлок найден.
Рассмотрим два среза:
- когда взаимно блокирующие процессы прислали координатору свои графы;
- когда они прислали ему notChanged.
Эти срезы не обязательно согласованны, но они барьерно-синхронизированы (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез , а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для он также выполнен.
17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка
- Иерархия порядков сообщений
- Алгоритм для FIFO порядка
- Алгоритм для причинно-согласованного порядка
- Алгоритм для синхронного порядка
20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина
TODO? (CHECK)
22 билет. Иерархия ошибок в распределенных системах. Отказ узла в асинхронной системе - невозможность консенсуса (доказательство Фишера-Линча-Патерсона)
- Иерархия ошибок в распределённых системах
- Асинхронные и синхронные распределённые системы
- Консенсус в распределённой системе
- Теорема Фишера-Линча-Патерсона (FLP)
23 билет. Консенсус в распределенных системах. Применение консенсуса: выбор лидера, terminating reliable broadcast
- Иерархия ошибок в распределённых системах
- Асинхронные и синхронные распределённые системы
- Консенсус в распределённой системе
- Переформулировки консенсуса в распределённой системе
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
Проблема византийских генералов - прийти к нетривиальному консенсусу 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
Задача византийских генералов — мысленный эксперимент, призванный проиллюстрировать проблему синхронизации состояния систем в случае, когда коммуникации считаются надёжными, а процессоры — нет. (Вики)
Проблема византийских генералов формулируется так: имеется n генералов из которых f являются предателями. Как прийти к консенсусу честным генералам?
Известно, что при n > 3f задача решаема, а иначе нет.
- Каждый рассылает каждому свое число;
- Каждый рассылает каждому собранные значения;
- В полученных векторах каждый проводит голосование.
Можно доказать, например, что при n = 3, f = 1 консенсус невозможен.
Доказательство от Елизарова:
Пусть каждому процессу подаётся число 0 или 1 на вход(могут быть разными на разных процессах). Задача - прийти к нетривиальному консенсусу всем работающим процессам на одном значении, которое было дано на вход хотя бы одному работающему процессу. (Сильный консенсус)
Тогда если считать 2 верхних процесса рабочими, а 2 нижних - одним сбойным, верхние обязаны прийти к консенсусу на 0. Аналогично, если считать 2 нижних процесса рабочими, а 2 верхних - одним сбойным - нижние приходят к консенсусу на 1.
И если мы считаем рабочими 2 правых, а 2 левых - одним сбойным(ведущим себя как пара из верхнего рабочего и нижнего рабочего) - то верхний правый придет к консенсусу на 0 вместе с воображаемым верхним соседом, а нижний правый - к консенсусу на 1 с воображаемым нижним соседом. Fail.
Поэтому такого алгоритма нет, и консенсус при N=3 и f=1 невозможен.
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) — объект, который можно реплицировать на много узлов и обновлять параллельно без координации между узлами.
Репликация на основе состояния
Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике. Та применяет функцию merge, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д..
Достаточные условия согласованности:
1. Множество возможных состояний образует полурешетку, т.е. частично упорядоченное множество с операцией наименьшей верхней грани, причем merge реализует эту операцию;
2. Обновления возрастают.
Репликация на основе операций
Реплика посылает не все состояние, а только обновление всем репликам. Согласованность можно гарантировать, если обновления коммутативны. Кроме того, требуется чтобы каждая операция была доставлена ровно один раз.
todo дельта-CRDT
