ふわふわ時間

0%

CRDT 学习笔记。

## 背景知识

### A CRDT Primer Part I: Defanging Order Theory

#### Order

Definition

An Order set is a binary relation $\le$ on a set $\mathcal{S}$, written $(\mathcal{S},\le)$.

Core concepts

• If we can say that $a \le b$ or $b \le a$, then we know that $a$ is comparable to $b$.
• In order theory, if $a$ and $b$ are incomparable, we write $a \parallel b$.
• A join between two elements, written $a \vee b$.

Type of order

• An order is total if for any $a$ and $b$ in the set, either $a \le b$ or $b \le a$.

例: 集合是自然数，二元关系为小于等于

• A partial order is weaker than a total. It does not require that every pair $a$ and $b$ in a set can be compared.

例: 集合是地理位置，二元关系为"位于"

#### Join

Upper bound

For a set $\mathcal{S}$, an order $(\mathcal{S},\le)$, and $\mathcal{A} \subseteq \mathcal{S}$ is an aibitrary subset, then an element $u \in \mathcal{S}$ is said to be an upper bound of $\mathcal{A}$ if $a \le u, \forall a \in \mathcal{A}$.

Definition

For a set $\mathcal{S}$, an order $(\mathcal{S},\le)$, and two elements $a,b \in \mathcal{S}$, then join of $a$ and $b$ (written $a \vee b$) is a least upper bound of $\{a, b\}$ according to our order $(\mathcal{S},\le)$.

In total order, a join of two elelments is always equals to one of those two elements. However, if we're talking about partial orders, this is not guaranteed.

Properties

1. Commutativity: $a \vee b = b \vee a$
2. Associativity: $(a \vee b) \vee c = a \vee (b \vee c)$
3. Idempotence: $a \vee a = a$

Join-semilattice

A join-semilattice is a order set $(\mathcal{S},\le)$ that has a join(a least upper bound) for any nonempty finite subset.

Dually, a meet-semilattice (or lower semilattice) is a ordered set which has a meet (or greatest lower bound) for any nonempty finite subset.