3 ms·

Not all updates are commutative, but there exists an entire class of algorithms that solve for each of these scenarios - see CRDTs, DAGs, even linked lists.

• jacques_chester 11y ago
  I'm skimming, so I am probably getting it wrong. But on my reading, CRDTs just kick the can down the road to the implementer of the operation or merge function. The way they solve for commutativity is to ... require commutativity. That's a win if your changes are commutative. Lots of things aren't.
  • marknadal 11y ago
    From my research the only thing you truly can't handle is The Double Spending problem, blockchain ledgers help against this but are not immune to it. Any and all arithmetic operations can be fully solved with CRDTs without further can kicking. The trivial solution is to give every number you are adding/subtracting a unique identifier, then as the values come in you do a sum across them, deduplicating in the process. This means you can resend the math operations as many times as you want and you still get an idempotent result.
    • jacques_chester 11y ago
      Sounds like Event Sourcing. The idea of giving every integer a unique identity sounds expensive but plausible.
    • skybrian 11y ago
      "Fully solved" seems like a bit of an exaggeration, considering that mathematical operations on computers often aren't commutative if you look into the details. Consider catastrophic cancellation in floating point and overflow in fixed-point calculations with range checks. To get a consistent answer, you'd also have to sort the numbers consistently, so instead of a sum this becomes an insert into a sortable list. This is far more expensive than the typical kinds of aggregate operations people want to do at scale - the point of aggregation is not to just save all the original data.