5 ms·

CRDTs are great examples of what the NoSQL movement called Eventual Consistency. I never understood why this movement assumed that abandoning ACID-style consist

CRDTs are great examples of what the NoSQL movement called Eventual Consistency. I never understood why this movement assumed that abandoning ACID-style consistency automatically gave you Eventual Consistency. As a side question, have any new algorithms been developed over the last decade that have significantly improved automatic source branch merging?

shinzui 6y ago
Yes. Take a look at Pijul. Here is an article explaining the algorithm. https://jneem.github.io/merging/ https://jneem.github.io/merging/
- billconan 6y ago
  very good read. however, I'm confused. the article doesn't mention how to handle changes within a line?
  - lioeters 6y ago
    I have no real understanding of this, but following the bread crumbs, I found this in Pijul's site (my emphasis below): > In that paper, and in Pijul, the definition of a file is slightly expanded, to included these cases, and “artificially add” all pushouts of all possible patches to the space of files. > The resulting structure is a graph of byte chunks (which can be for instance binary blocks, lines, or smaller parts, such as indentation). > The relation between them, described by the graph edges, is the order in which they appear in the files. This graph acts as a “cache” of applied patches. From: https://pijul.com/model/#pushouts-and-distributed-algorithms https://pijul.com/model/#pushouts-and-distributed-algorithms The paper is they mention is the same one in GP's linked article. A Categorical Theory of Patches - https://arxiv.org/abs/1311.3903 https://arxiv.org/abs/1311.3903
Taek 6y ago
Eventual consistency and ACID are not at odds, you can have one or the other or neither or both.
- swyx 6y ago
  depends how you interpret ACID. for some interpretaions, only strong consistency qualifies
- dboreham 6y ago
  Not true. Eventual consistency can not (provably) provide consensus.
  - IggleSniggle 6y ago
    sure it can! A particle can be either this or that until someone looks at it, and when they do, the act of looking at it causes the state to collapse and propagate. Sure, a partitioned group may come to alternate realities before they reunite, but then you just get to do the same thing again! Like Conways Game of Life, except with application state. (I am joking of course)

shinzui 6y ago

Yes. Take a look at Pijul. Here is an article explaining the algorithm. https://jneem.github.io/merging/ https://jneem.github.io/merging/

billconan 6y ago
very good read. however, I'm confused. the article doesn't mention how to handle changes within a line?
- lioeters 6y ago
  I have no real understanding of this, but following the bread crumbs, I found this in Pijul's site (my emphasis below): > In that paper, and in Pijul, the definition of a file is slightly expanded, to included these cases, and “artificially add” all pushouts of all possible patches to the space of files. > The resulting structure is a graph of byte chunks (which can be for instance binary blocks, lines, or smaller parts, such as indentation). > The relation between them, described by the graph edges, is the order in which they appear in the files. This graph acts as a “cache” of applied patches. From: https://pijul.com/model/#pushouts-and-distributed-algorithms https://pijul.com/model/#pushouts-and-distributed-algorithms The paper is they mention is the same one in GP's linked article. A Categorical Theory of Patches - https://arxiv.org/abs/1311.3903 https://arxiv.org/abs/1311.3903

Taek 6y ago

Eventual consistency and ACID are not at odds, you can have one or the other or neither or both.

swyx 6y ago
depends how you interpret ACID. for some interpretaions, only strong consistency qualifies
dboreham 6y ago
Not true. Eventual consistency can not (provably) provide consensus.
- IggleSniggle 6y ago
  sure it can! A particle can be either this or that until someone looks at it, and when they do, the act of looking at it causes the state to collapse and propagate. Sure, a partitioned group may come to alternate realities before they reunite, but then you just get to do the same thing again! Like Conways Game of Life, except with application state. (I am joking of course)