Нам требуется, чтобы операции образовывали '''полурешётку''' (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) ==Операция: добавить $x$ к значению счётчика.
Получив обновление от клиентаЭта операция коммутативна, реплика сперва обновляет локальное состояние, затем отправляет это состояние другой реплике. Та применяет функцию merge, чтобы объединить свое состояние с полученным и отправляет его еще одной реплике, и т. дно не идемпотентна.Поэтому добавим в каждой операции уникальный идентификатор.
Достаточные условия согласованностиПолучили полурешётку, но разрослись данные:не только счётчик, но и все идентификаторы операций.
1. Множество возможных состояний образует полурешеткуЭто обобщается: просто говорим, что операция — это множество операций, ткоторые надо применить.еУ каждой операции есть время: пара из логических часов и номера процесса. частично упорядоченное множество с операцией наименьшей верхней граниТогда, конечно, тяжёлое состояние и сложно получать реальные данные, причем merge реализует эту операцию;зато работает.
2== Репликация на основе состояния == Теперь данные хранятся как $n$ независимых счётчиков: по одному на каждый процесс. Обновления возрастают Операция: установить компоненты в такие-то значения. Объединение операций: покомпонентный максимум (коммутативно и идемпотентно). Теперь у нас состояние не растёт со временем, а инкремент всё ещё можно делать: процесс увеличивает свой локальный счётчик и рассылает своё новое состояние всем.
== $\delta$-CRDT ==
Оптимизация CRDT: отсылаем не весь вектор, а только изменения в этом векторе: установить такую-то компоненту в такое-то значение.
То есть у нас теперь есть не только операции, но и "кусочки операций", которые надо не только уметь применять, но ещё и склеивать между собой.
Относится к обоим видам CRDT.
