Register

Register CRDT Design

Replacement for single-valued constraint.

LWWRegister

(For comparison)

A Last-Writer-Wins Register (LWW-Register) creates a total order of assignments by associating a timestamp with each update... Timestamps are assumed unique, totally ordered, and consistent with causal order.

Clone1	Clone2	Clone3
1.1 set A {A}
	2.1 set B {B}	1.1 {A}
		3.1 set null {}
		2.1 {}
2.1 {B}	1.1 {B}
3.1 {}	3.1 {}

Works because ordering by clock & clone ID; null is also timestamped.

• TIDs are not ordered
  • They could be order preserving
• Will not work for maxCount > 1

Hide Excess Values

Hide conflicting value from graph but not TIDs map.

• Receipt of deletion should reinstate hidden
  • Recover hidden by subject-predicate; triple keys are ordered in triple-TID map
  • Large number of hidden values?
• Hidden values can persist forever
  • Delete queries only match what is in the graph
  • Anomaly: local delete causes a hidden greater value to appear
  • Local replace (inc delete) should assert delete of all hidden lesser values

Clone1	Clone2	Clone3
1.1 add A ({A},{A→{1.1}})	2.1 add B ({B},{B→{2.1}})
		1.1 ({A},{A→{1.1}})
		3.1 del A ({},{})
		2.1 ({B},{B→{2.1}})
2.1 ({A},{A→{1.1},B→{2.1}})	1.1 ({A},{A→{1.1},B→{2.1}})
3.1 ({B},{B→{2.1}})	3.1 ({B},{B→{2.1}})

(Wrong) Entailed Removal

Remove conflicting value from graph but not TIDs map.

Clone1	Clone2	Clone3
1.1 add A ({A},{A→{1.1}})	2.1 add B ({B},{B→{2.1}})
		1.1 ({A},{A→{1.1}})
		3.1 del A ({},{})
		2.1 ({B},{B→{2.1}})
2.1 ({A},{A→{1.1},B→{2.1}})	1.1 ({A},{A→{1.1},B→{2.1}})
3.1 ({},{B→{2.1}}) ⚠️ no B!	3.1 ({},{B→{2.1}}) ⚠️ no B!

(Wrong) Do Not Publish Assertion

Just don't publish the delete of the conflicting value.

Clone1	Clone2	Clone3
1.1 add A ({A},{A→{1.1}})	2.1 add B ({B},{B→{2.1}})
		1.1 ({A},{A→{1.1}})
		3.1 del A ()
		2.1 ({B},{B→{2.1}})
2.1 ({A},{A→{1.1}})	1.1 ({A},{A→{1.1}})
3.1 ({},{})	3.1 ({},{})	⚠️ still has B!

• Does work if deletion is not allowed
• Also will not work for maxCount > 1

(Wrong) Tombstone Graph

Store conflicting values in a tombstone map, so can be searched for.

Clone1	Clone2	Clone3
1.1 add A ({A},{},{A→{1.1}})	2.1 add B ({B},{},{B→{2.1}})
		1.1 ({A},{},{A→{1.1}})
		3.1 del A ({},{},{})
		2.1 ({B},{},{B→{2.1}})
2.1 ({A},{B},{A→{1.1},B→{2.1}})	1.1 ({A},{B},{A→{1.1},B→{2.1}})
3.1 ({B},{},{B→{2.1}})	3.1 ({B},{},{B→{2.1}})

• ⚠️ Tombstones can persist forever
  • Mitigated by delete queries matching tombstones?
  • But that requires graph indexing, doesn't work for query-then-update, doesn't work if delete value explicitly matched.