Idempotence

How do we avoid cases where losing an ACK could lead to users doing an action multiple times (e.g. pressing the like button)? Idempotence!

$f$ is idempotent if $f(x)=f(f(x))$

For example

• Not idempotent: $f(likeCount)=likeCount+1$
• Idempotent: $f(likeSet)=likeSet\cup \{userID\}$

Idempotent requests can be retried without deduplication.

However, this isn’t perfect when there are other actors/actions that intermix. For example, $f(f(x))=f(x)$ but $f(g(f(x)))\ne g(x)$ (e.g. liking, unliking, then liking is not the same as unliking!)

To somewhat fix this, use tombstones and record logical timestamp for when events happen

• Then, we can reconcile replicas by propagating the record with the latest timestamp and discard the records with earlier timestamps
• Then, to fix concurrent writes by different clients
  • Last writer wins (LWW): resolve conflicts using a logical clock that gives total ordering (e.g. Lamport clock)
  • Multi-value register (give all options to let user/algorithm above resolve it): use a Vector clock, $v_2$ replaces $v_1$ if $t_2>t_1$; preserve both $\{v_1,v_2\}$ if $t_1\parallel t_2$