Martin Kleppmann and Heidi Howard: *Byzantine Eventual Consistency and the Fundamental Limits of Peer-to-Peer Databases*

$I$-confluence is a necessary and sufficient condition for the existence of a byzantine fault-tolerant eventual consistency replication algorithm

They define an invariant is a predicate over replica states, i.e. a function $I(S)$ that takes a replica state $S$ and returns either true or false.

A set of transactions is $I$-confluent with regard to an invariant $I$ if

- Each replica can execute a subset of the transaction with $I$ preserved on that replica
- Merging the updates from the transactions still preserves $I$

A few examples:

- $I$-confluent: consider an invariant $I(S)$ that is true if every user in $S$ has a non-negative balance
- If each transaction only increases a user’s account balance, then any combination of transactions will still satisfy $I$
- Note that this example is
*no longer*$I$-confluent if transactions can deduct from a user’s account balance- Say $A$ has a balance of $50
- If $T_{1}$ results in deducting $40 from $A$ and $T_{2}$ results in deducting $25 from $A$, each transaction is valid on its own
- But when combined, it violates the invariant $I$
- As a result, we can’t model anything like a cryptocurrency using CRDTs

- Not $I$-confluent: consider an invariant $I(S)$ that is true if there are no duplicate values in $S$ (i.e. ensure that $S$ is a set)
- If $T_{1}$ and $T_{2}$ are both transactions that create data items with the same value in that attribute, each of transaction preserves the constraint
- However the combination of the two does not

I conjecture that if a data structure is $I$-confluent, then it can be expressed in monotonic Datalog. That is, $I$-confluence holds if and only if states $S$ can be represented as a join semilattice.

This shows equivalence with the CALM conjecture (proof left as an exercise for the reader).