# CRDT

### crdt

[yt_ref](https://www.youtube.com/watch?v=CD_0u03EdcA&ab_channel=CNCF%5BCloudNativeComputingFoundation%5D)

### non-CRDT example : lose information


### crdt example


* application_data: the main message
* metadata: offer information for mergeing between peer-to-peer

before sync
after sync

key value= device_id increment_count

#### crdt-tradeOff

* extra memory for metadata

---
#### network protocal

you choose:
* websocket
* gossip protocol
* mesh network(libp2p)
* WebRTC

##### operation-based CRDTs

基於操作的CRDT也被稱為交換性複製資料類型（commutative replicated data types，或CmRDT）。CmRDT副本只通過傳輸更新操作來傳播狀態。例如，單一整數的CmRDT可以廣播操作（+10）或（-20）。副本接收更新並在本地應用這些更新。這些操作是可交換的。然而，它們不一定冪等。因此，通信基礎設施必須確保一個副本上的所有操作都被傳遞給其他副本，沒有重複，但以任何順序傳輸都是可以的。

##### state-based CRDTs

基於狀態的CRDT被稱為收斂複製資料類型（convergent replicated data types，或CvRDT）。與CmRDT相反，CvRDT將其完整的本地狀態傳送給其他副本，在這些副本中，狀態必須通過可交換的、可結合的並且是冪等的函式合併。合併函式為任何一對副本的狀態提供連接，因此所有狀態的集合形成一個半格。更新函式必須按照與半格相同的偏序規則，單調地增加內部狀態。函式必須內部狀態，根據與半網格相同的偏序規則。

#### propagate update to peers

* idempotent: an update from one peer to another can be applied multiple times and the merging result is the same effect.(ex. send count:{100:1} get same result with multiple applied)
* commutative : X\*Y ===Y\*X , ordering doesn't matter.
* associative: \(X\*Y\)\*z ===Y\*\(X\*z\)