Monas: CRSL data structure

https://scrapbox.io/files/688dd6d34734b92ee1485c95.png

somaさんのアイコンだけ残してた笑

1. 基本要素: バージョンノード Node

すべてのデータは、以下の要素を持つノードとして表現される。

$ \text{Node} \triangleq (id, \text{data}, P_{\text{parents}})

id: ノードを一位に識別するID (例: コンテンツのハッシュ値)

data: ノードが保持するペイロード (バージョン情報)

2. 全体構造: 有向非巡回グラフ (DAG)

V: すべてのバージョンノード Node の集合

$ V = \{ v_1, v_2, v_3, \dots \}

E: ノード間の有向リンク（親子関係）の集合。uがvの親であることを示す。

$ E = \{ (u, v) \in V \times V \mid u.id \in v.P_{\text{parents}} \}

3. ローカル更新: ツリー構造の形成

新しいバージョンを作成する操作は、1つ以上の親ノードから新しい子ノードを生成する。この操作自体がツリー構造を形成する。

create_version: 親ノードの集合を受け取り、新しいノードを返す操作。

$ v_{\text{new}} = \text{create\_version}(\{v_{p1}, v_{p2}, \dots \})

この時、新しいノードの親は以下のようになる。

$ v_{\text{new}}.P_{\text{parents}} = \{ v_{p1}.id, v_{p2}.id, \dots \}

4. グローバルな順序付け: CRDTによる全順序の保証

CRDTは、DAGによって定義される因果順序を拡張し、全てのノード間に矛盾のない単一の順序（全順序）を定義する。

DAGの親子関係をたどれる場合、2つのノード間に因果関係があると言える。