Merkle-CRDTs
https://www.youtube.com/watch?v=XGehT8tNuWw
Merkle Tree x CRDT: 両者の特性を活かして、DAGを論理的な時計(タイムスタンプ? kekeho.icon)とすることができる
Contributions
Merkle DAGベースの論理時計
CRDTで活用されるバージョンベクタ・論理時計のかわりに、Merkle Treeが使えることを示すンゴ Merkle-CRDTs
CRDTのペイロードのための汎用トランスポート・永続化レイヤ
詳細
Merkle Clock
DAGは(ブロックチェーンでの使用例のように)因果関係を表すのにも使える
Merkle Clock $ Mは、各ノードがEventを表すMerkle DAGである
$ M_{\alpha}と$ M_{\beta}は以下の手順でマージできる ($ \alpha, \betaはCID, TreeのRoot) $ \alpha = \betaの場合: 同じDAGなので何もしなくていい
$ \alpha \in M_{\beta}の場合: $ M_\alphaの履歴はすでにその一部なので、$ M_\betaを残す (その逆もしかり)
それ以外: 全然別の不連続なDAGなので、$ \alpha, \betaという2つのノードを子に持つ$ \gammaを作る(マージ)
↑より、Merkle Clockは因果関係情報を含んでいるといえる。Merkle DAGがたしかに論理時計として使える Strict Partial Orderなので、全部のイベントについて前後がわかるわけではない、並行も存在することに注意。
Merkle Clock DAGはG-Set CRDTとみなせるので、収束するンゴ (ちゃんとした証明は元論文にある)
Merkle CRDTs
ノードが任意のCRDTペイロードを持つMerkle-Clock
CRDTペイロード: CRDTのOperationとかStateを指す
Partial Orderなので、ディスオーダーが起きない👍
Operation BasedなCRDTに向いてる。Stateもできるけど、ノードにStateを埋め込むことになるので、大きくなっちゃってどうだろねー
論文にはアンチエントロピーアルゴリズムの紹介もある
DAG-Syncer Component
レプリカがCIDを与えられた他のレプリカからリモートでMerkle DAGのノードを取得するコンポーネント 以下のメソッドを持つ
Get(CID): Node
Put(Node)
Broadcaster Component
以下のメソッドを持つ
Broadcast(Data)
DAG-SyncerとBroadcasterとして、IPFSが使える IPFSはDAG-Syncerとして動作し、libp2p層が提供するPubSub機構の一つがBroadcastを担当する 限界と最適化
DAGがどんどん大きくなってしまう
アプリケーション
Markle-CRDTsで分散KVSとか作れちゃう 多分Read/Write等の順序付けにCRDTを使ってる?(要調査)kekeho.icon