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