1632
правки
Изменения
м
TODO
TODO? (CHECK)
Как известно из 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)$ сообщений на консенсус.синхронных системах]]
=== 28 билет. Paxos. Алгоритм, его свойства.====== 29 билет. Paxos. Общие принципы. Основные модификации.====== 30 билет. Транзакции * [[Иерархия ошибок в распределенных распределённых системах. 2 Phase Locking===]]* [[Асинхронные и синхронные распределённые системы]]=== 31 билет. Транзакции * [[Консенсус в распределенных системах. 2 Phase Commit.===распределённой системе]]=== 32 билет. СAP теорема (концепции, подходы, без доказательства)====== 33 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===CRDT (Conflict* [[Алгоритм Бен-Free Replicated Data Type) — объект, который можно реплицировать на много узлов и обновлять параллельно без координации между узлами.Ора]]
'''Репликация на основе состояния'''=== 28-29 билеты. Paxos. Алгоритм, его свойства. Общие принципы. Основные модификации.===* [[Консенсус в распределённой системе]]* [[Replicated State Machine]]* [[Paxos]]
Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике=== 30 билет. Raft. Та применяет функцию mergeАлгоритм, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д.свойства. ===* [[Консенсус в распределённой системе]]* [[Replicated State Machine]]* [[Raft]]
Достаточные условия согласованности:=== 31 билет. Транзакции в распределенных системах. 2 Phase Locking===* [[Транзакции в распределённых системах]]* [[2 Phase Locking]]
1=== 32 билет. Множество возможных состояний образует полурешетку, тТранзакции в распределенных системах.е2 Phase Commit. частично упорядоченное множество с операцией наименьшей верхней грани, причем merge реализует эту операцию;===* [[Транзакции в распределённых системах]]* [[2 Phase Commit]]
2. Обновления возрастают=== 33 билет.СAP теорема (концепции, подходы, без доказательства)===* [[CAP теорема]]
'''Репликация на основе операций'''=== 34 билет. Gossip. СRDT и дельта-CRDT (концепции, примеры алгоритмов, см. работу с семинара)===* [[Gossip-протоколы]]* [[CRDT]]
Реплика посылает не все состояние, а только обновление всем репликам=== 35 билет. Согласованность можно гарантировать, если обновления коммутативныСамостабилизирующиеся алгоритмы. Кроме того, требуется чтобы каждая операция была доставлена ровно один разИдея.Алгоритмы взаимного исключения и поиска остовного дерева ===* [[Иерархия ошибок в распределённых системах]]todo дельта-CRDT* [[Самостабилизирующиеся алгоритмы]]
rollbackEdits.php mass rollback
===16 билет. Локально-стабильные предикаты, согласованные интервалы, барьерная синхронизация (3 алгоритма). Применение для определения взаимной блокировки===
*[[Локально стабильный предикат]]
*[[Согласованный интервал]]
*[[Барьерная синхронизация (3 алгоритма)]]
* Применение для определения дедлока. Каждый процесс <tex>P_i</tex> поддерживает свою часть графа ожидания (ребра, которые из него исходят), а также флажок changed, который равен true, если его часть графа поменялась с последнего сообщения координатору. Координатор периодически опрашивает процессы, получая их графы. Процесс отвечает новым графом, если есть изменение, а иначе шлет notChanged. Координатор собирает весь граф ожидания. Если в нем есть цикл, он отправляет процессам запрос на изменение. Если все процессы в цикле ответили notChanged, дедлок найден. Рассмотрим два среза: * когда взаимно блокирующие процессы прислали координатору свои графы;* когда они прислали ему notChanged.Эти срезы не обязательно согласованны, но они барьерно-синхронизированы (из-за сообщений координатору и обратно), а значит образуют согласованный интервал. Поэтому между ними есть согласованный срез <tex>G</tex>, а так как состояние процессов в цикле не менялось на всем интервале, и в первом срезе предикат выполнен, для <tex>G</tex> он также выполнен.[[Определение взаимной блокировки]]
===17-19 билеты. Упорядочивание сообщений. Определения, иерархия порядков. Алгоритм для FIFO. Алгоритм для причинно-согласованного порядка. Алгоритм для синхронного порядка ===
===20-21 билеты. Общий порядок (total order). Алгоритмы Лампорта и Скина===
*[[Общий порядок сообщений]]
*[[Алгоритм Лампорта]]
===24 билет. Синхронные системы. Алгоритм для консенсуса в случае отказа заданного числа узлов===
===25 билет. Синхронные системы. Проблема византийских генералов. Алгоритм для N >= 4, f = 1. Объяснить идею обобщения для f > 1===
=== 27 билет. Недетерминированные алгоритмы консенсуса. Алгоритм Бен-Ора. ===
==Ссылки==
<references/>
