3 ms·

> In this model, the results of the executions of programs are also mergeable. Not all updates are commutative. The ordering of events in (add 1, add 2, add 3

> In this model, the results of the executions of programs are also mergeable. Not all updates are commutative. The ordering of events in (add 1, add 2, add 3) does not affect the outcome. The order of events in (add 1, multiply 2, divide 3) does matter. The problem of linearity exists as soon as you have a commutative operation in a relativistic universe where information cannot be simultaneously updated in two coordinates simultaneously. Until now there have been heroic engineering efforts to hide this from software developers. Hardware has conspired to conceal that even in a space a few centimetres wide, values can become inconsistent. Once you have independent memory spaces, all bets are off and you are forced to pay a high price for losing the abstraction.

marknadal 11y ago
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.

marknadal 11y ago

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.