論文筆記：[Inria RR-7506] A comprehensive study of Convergent and Commutative Replicated Data Types

這篇論文總結了兩類可以達成最終一致性的數據結構構型原則：CvRDT & CmRDT，並且總結了一系列相關的數據結構：Counter，Register，Set，Graph。

總結的兩種構型原則都是充分（不必要）條件。

CvRDT (Convergent Replicated Data Type)

1. Values partially ordered (monotonic)
2. Merge(x,y) := the least upper bound of x, y (idempotent & commutative)
3. Communication channel: eventually-reliable p2p channel

CmRDT (Commutative Replicated Data Type)

1. Reliable Broadcast Channel
2. All concurrent operations commute

If a weaker ordering suffice,

1. If concurrent, need commute
2. If causally related but not ordered in delivery order, must commute

With these 2, we got all received operations applied in correct order. (commute if necessary)

CvRDT 和 CmRDT 可以互相模擬。

Counters:

• Op-based Counter: trivial
• G-Counter: State-based increment-only Counter
• PN-Counter: (positive & negative G-Counters?) 模擬有增有減的 Counter
• Non-negative Counter: 沒有好辦法

Registers:

• LWW-Register: Last-Writer-Wins Register
• MV-Register: Multi-Value Register

Sets:

• G-Set: grow-only set
• 2P-Set: two-phase set (Allow both add & remove, but actually remove wins)
• U-Set
• LWW-element-Set
• PN-Set
• OR-Set: Observed-Remove Set

Graphs

TODO: Add more details to LWW-Register, MV-Register, 2P-Set, OR-Set

基於值的信息交換保證最終一致性的充分非必要條件，單調和最小上確界，操作順序可交換。每次在單一節點上的操作導致值增加，合併操作則取兩個值的最小上確界。只要求值是偏序的。既有加又有減的操作最好轉換為只增加。例如準備兩個值，其中一個記錄加法，一個記錄減法，這樣兩個值分別都是單調的。

基於操作的信息交換保證最終一致性的充分非必要條件，按操作順序到達副本。可以通過增加唯一標識做到這一點。

相關論文：

[1] P.Viotti and M. Vukoli?, 「Consistency in Non-Transactional Distributed Storage

[2] M. Shapiro, N. Pregui?a, C. Baquero, and M. Zawirski, 「A comprehensive study of Convergent and Commutative Replicated Data Types,」 2011.

[3] P. Bailis, A. Davidson, A. Fekete, A. Ghodsi, J. M. Hellerstein, and I. Stoica, 「Highly Available Transactions: Virtues and Limitations (Extended Version),」 pp. 181–192, 2013.