Gowtham Kaki
gowthamkaki.bsky.social
Gowtham Kaki
@gowthamkaki.bsky.social
Assistant Professor at CU Boulder. Programming Languages. Formal Methods. Distributed Systems. Security.

https://gowthamk.github.io
respects causal and arbitration orders simultaneously. What should take the priority in this case? (the above example is credited to @guiltygyoza.bsky.social ).
May 29, 2025 at 5:35 PM
example is a counter that admits additions and multiplications. Suppose I want `add` to win over `mult`. How would I use this intuition to linearize the following partial order?:

-> mult1 -> add2
/
add1
\
-> mult2 -> add3

I don't see a linearization that...
May 29, 2025 at 5:35 PM
E.g.., in an "add-wins" set, `Add(e)` is always ordered after a concurrent `Remove(e)`. This is easy because an `Add(e)` only ever conflicts with `Remove(e)` and vice-versa. But what if there are several kinds of conflicts? Is the arbitration order transitive/symmetric/anti-symmetric? A simple...
May 29, 2025 at 5:35 PM
+1 also for lack of (principled) read semantics. In your demonstration of how an op-based CRDT is a semi-lattice of partially-ordered logs, it is assumed that concurrent ops are commutative. This is not always the case; an "arbitration order" is defined to order concurrent conflicting ops...
May 29, 2025 at 5:35 PM
then we also need a buffer to store `Remove(e)` effects until preceding `Add(e)` effects arrive. This makes the implementation disproportionately complex compared to the simple spec of "add-wins" crdt, e.g., see the attached pic (from an earlier paper).
May 29, 2025 at 5:12 PM
is received, it is applied only if the tagged vector clock is no less than e’s local vector clock, i.e., only if the arriving Remove has seen (i.e., causally succeeds) at least those `add(e)` ops the current replica is aware of. Otherwise it is a no-op. If casual delivery is not guaranteed ...
May 29, 2025 at 5:12 PM
+1. Implicit causal delivery assumption is frustrating. Oftentimes the causality tracking mechanism is type-specific. E.g., in "add-wins" set, there need to be a vector clock for every element `e` to keep track of the number of `add(e)` operations executed on each node. When a `Remove(e)` effect ...
May 29, 2025 at 5:12 PM