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

-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 that takes a replica state and returns either true or false.

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

  1. Each replica can execute a subset of the transaction with preserved on that replica
  2. Merging the updates from the transactions still preserves

A few examples:

  • -confluent: consider an invariant that is true if every user in has a non-negative balance
    • If each transaction only increases a user’s account balance, then any combination of transactions will still satisfy
    • Note that this example is no longer -confluent if transactions can deduct from a user’s account balance
      • Say has a balance of $50
      • If results in deducting $40 from and results in deducting $25 from , each transaction is valid on its own
      • But when combined, it violates the invariant
      • As a result, we can’t model anything like a cryptocurrency using CRDTs
  • Not -confluent: consider an invariant that is true if there are no duplicate values in (i.e. ensure that is a set)
    • If and 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 -confluent, then it can be expressed in monotonic Datalog. That is, -confluence holds if and only if states can be represented as a join semilattice.

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