Нам требуется, чтобы операции образовывали '''полурешётку''' (semilattice) — полугруппа с коммутативной и идемпотентной операцией объединения (merge) операций.
Более формально: для любых двух операций $a$, $b$, $c$ верно:
# $a \wedge sqcup a = a$# $(a \wedge sqcup b) \wedge sqcup c = a \wedge sqcup (b \wedge sqcup c)$# $a \wedge sqcup b = b \wedge sqcup a$
Это позволяет нам очень просто реплицировать состояния: каждый узел при получении нового состояния от соседа объединяет его со своим состоянием.
Получили полурешётку, но разрослись данные: не только счётчик, но и все идентификаторы операций.
== Репликация на основе состояния (CRDT) ==Это обобщается: просто говорим, что операция — это множество операций, которые надо применить. У каждой операции есть время: пара из логических часов и номера процесса. Тогда, конечно, тяжёлое состояние и сложно получать реальные данные, зато работает.
Получив обновление от клиента, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике. Та применяет функцию merge, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. д.. == Репликация на основе состояния ==
Достаточные условия согласованностиТеперь данные хранятся как $n$ независимых счётчиков:по одному на каждый процесс.
1Операция: установить компоненты в такие-то значения. Множество возможных состояний образует полурешетку, т.е. частично упорядоченное множество с операцией наименьшей верхней грани, причем merge реализует эту операцию;
2Объединение операций: покомпонентный максимум (коммутативно и идемпотентно). Обновления возрастают Теперь у нас состояние не растёт со временем, а инкремент всё ещё можно делать: процесс увеличивает свой локальный счётчик и рассылает своё новое состояние всем.
== $\delta$-CRDT ==
Оптимизация CRDT: отсылаем не весь вектор, а только изменения в этом векторе: установить такую-то компоненту в такое-то значение.
То есть у нас теперь есть не только операции, но и "кусочки операций", которые надо не только уметь применять, но ещё и склеивать между собой.
Относится к обоим видам CRDT.
