Search IconIcon to open search


Last updated Oct 20, 2022 Edit Source

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

Kleppmann and Howard prove an equivalent result which states that $\mathcal I$-confluence is a necessary and sufficient condition for the existence of a Byzantine 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 $\mathcal I$-confluent with regard to an invariant $\mathcal I$ if

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

A few examples:

I conjecture that if a data structure is $\mathcal I$-confluent, then it can be expressed in monotonic Datalog. That is, $\mathcal 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).