How to handle concurrent adds on the same key in Last Write Wins map?

Question

I am implementing an LWW map and in my design, all added key-value pairs have timestamps as is expected from LWW. That works for me until the same key is added in two replicas with different values at the same time. I can't understand how to make the merge operation commutative in this scenario.

Example:

Replica1 => add("key1", "value1", "time1")
Replica2 => add("key1", "value2", "time1")
Merge(Replica1, Replica2) # What should be the value of key1 in the resulting map?

Answer 1

Let's see what last write wins means in terms on causality. Let's say two clients C1 and C2 changed the same data D (same key) to values D1 and D2 respectively. If they don't ever talk to each other directly, you can pick D1 or D2 as the last value, and they will be OK.

But, if they talk to each other like, C1 changed the value to D1, informed C2, which as the result changed it to D2. Now, D1 and D2 have causal dependency, D1 happens before D2, so if your system picks D1 as the last value in merge, you have broken the last write wins guaranty.

Now coming to your question, when two clients make two requests in parallel, those two requests no way can have causal dependency, as both were inflight together, so any value you pick is fine.