結合半束, join-semilattice

結論

以下の定義と特性を満たすことができると，

状態ベースCRDTでは、各レプリカが自分の状態を他のレプリカにブロードキャストし、受け取った側は自身の状態とマージします。ネットワークは信頼できず、メッセージは順序通りに届くとは限らず、重複したり、遅延したりします。

結合半束という構造は、こうした信頼性の低いネットワークにおいても、最終的に全てのレプリカが同じ状態に収束すること（結果整合性）を保証するために極めて重要です。

メッセージが順序不同で届いても、可換律と結合律によってマージ結果は変わりません。

メッセージが重複しても、冪等律によってシステムの状態は変わりません。

この数学的な保証があるおかげで、状態ベースCRDTは複雑な合意形成プロトコル（コンセンサスアルゴリズム）なしに、シンプルかつ堅牢にデータを同期できるのです。

---

## 数学的定義

結合半束を理解するには、まず半順序集合から定義する必要があります。

1. 半順序集合 (Partially Ordered Set)

ある集合 $ S と、その上の二項関係 $ \le があり、すべての要素 $ a, b, c \in S に対して以下の3つの公理を満たすとき、組 $ (S, \le) を半順序集合と呼びます。

反射律 (Reflexivity): $ a \le a

（自分自身は自分自身以下である）

あるファイルFはそのファイルF自身の内容を持っているとこれを満たすことができる

反対称律 (Antisymmetry): $ a \le b かつ $ b \le a ならば $ a = b

（互いに入れ子になっているなら、それらは同一である）

推移律 (Transitivity): $ a \le b かつ $ b \le c ならば $ a \le c

（$ aが$ bに、その$ bが$ cに含まれるなら、$ aは$ cに含まれる）

何が「半」なのか？

集合の中のペアの中に比べることができないペアがある

2. 上限 / 結合 (Least Upper Bound / Join)

半順序集合 $ (S, \le) の2つの要素 $ a, b に対して、ある要素 $ c \in S が$ aと$ bの上限（または結合）であるとは、$ cが以下の条件を満たすことを言います。この上限を $ a \lor b と書きます。

$ a \le c かつ $ b \le c （$ cは$ aと$ bの上界である）

$ a \le d かつ $ b \le d となる任意の要素 $ d \in S に対して、$ c \le d が成立する（$ cは全ての上界の中で最小のものである）

3. 結合半束 (Join-Semilattice)

半順序集合 $ (S, \le) が結合半束であるとは、集合内の任意の2つの要素 $ a, b に対して、その上限（結合）$ a \lor b が必ず集合S内に存在することを言います。

例

1. 半順序集合

集合S = {A, B, C, D, E}

A - Eの5つのセットがあり，それぞれ

A = {a, c}

B = {c, a}

C = {a, c, g}

ここまでで，反射律，反対照律，推移律まで満たすことができる

D = {b, d}

E = {c, f}

何が半なのか？

理由は，D, Eにある

DとEでそれぞれ自分たちの要素で上の3つを満たせず，上や下を比べることができない

つまり，どんなペアでも必ず比べられる関係は全順序であり，

例えばブロックチェーンではガス代で処理順を全順序で実装している

2. 上限 / 結合

2つの集合

A = {a}

B = {b}

上界

上の2つの集合の両方を含むことができる集合S

S = {a, b}

S = {b, c, a}

S = {d, a, b}

など

上限 / 結合

以上の中で最も要素が少ない（=無駄が一切ない）上界: S = {a, b}

集合論位おいて，2つの集合AとBの上限は，その2つの和集合（$ A \cup B）である

## 結合操作が持つべき3つの特性

結合反則は，ネットワークが不安定な分散システムにおいて、データの同期を極めてシンプルかつ堅牢にするための、数学的な定義であり，

結合操作 ∨ は、CRDTにおけるマージ操作として不可欠な以下の3つの性質を自動的に満たします。

可換律 (Commutative): $ a \lor b = b \lor a

解説: 2つの状態をどちらの順序でマージしても結果は同じです。レプリカAの状態とレプリカBの状態をマージするのは、BとAをマージするのと同じです。

結合律 (Associative): $ (a \lor b) \lor c = a \lor (b \lor c)

解説: 3つ以上の状態をマージする際、どのペアから先にマージしても最終結果は同じです。「AとBをマージし、その結果とCをマージする」のは、「BとCをマージし、その結果とAをマージする」のと同じです。

冪等律 (Idempotent): $ a \lor a = a

解説: 同じ状態を何度マージしても、状態は変化しません。ネットワークの都合で同じ更新メッセージを複数回受信しても、システムに悪影響を与えません。