16 ms·

Shameless plug of a blog series where I try to list and summarize every paxos variant: https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ https://va

Shameless plug of a blog series where I try to list and summarize every paxos variant: https://vadosware.io/post/paxosmon-gotta-concensus-them-all/ https://vadosware.io/post/paxosmon-gotta-concensus-them-all/

anchpop 5y ago
Great read. One thing you may be interested to know: when do you need paxos or similar, and when can you get away with gossip and CRDTs? the answer is that the set of domains that can be expressed using CRDTs is exactly the set of monotonic logic. It’s a bit tricky to explain precisely in an HN comment but basically, something is monotonic if, once you learn that something is true, nothing can disprove it. For example, let’s say you know of a bunch of nodes on a graph, and you’re slowly learning about edges between the nodes. Once you see a cycle, no amount of new edges will ever “disprove” the cycle. So this means that, if what you care about is cycles, then a CRDT is fine. However, let’s say you’re trying to do disturbed garbage collection of nodes that have no edges leading to them. (And as before you’re slowly learning about new edges.) You can see a node has no edges leading to it that you know of, but if you think a node of garbage-collectible you might always be proved wrong by learning about a new edge. So the problem of distributed garbage collection can’t be solved using CRDTs. There’s a paper on this that you’ll find if you google for the CALM theorem.
- hardwaresofton 5y ago
  Thanks for taking the time to write this out -- I'm digging into the CALM theorem right now to try and get it to sink in. This explanation is fantastic and it makes me feel like I understand the concepts better than I probably do in reality.
bla3 5y ago
That was an interesting read, thanks!
- hardwaresofton 5y ago
  Thanks! Hope it is a decent introductory reference -- there's so much out there.
AtlasBarfed 5y ago
This is utterly fantastic stuff. Assuming it's correct, which with Paxos...
- hardwaresofton 5y ago
  Don't worry you don't have to take my word for it! I left all the links in and copied some PDFs to my domain as well just to make sure people could read the actual papers with the actual insight! :)

anchpop 5y ago

Great read. One thing you may be interested to know: when do you need paxos or similar, and when can you get away with gossip and CRDTs? the answer is that the set of domains that can be expressed using CRDTs is exactly the set of monotonic logic. It’s a bit tricky to explain precisely in an HN comment but basically, something is monotonic if, once you learn that something is true, nothing can disprove it. For example, let’s say you know of a bunch of nodes on a graph, and you’re slowly learning about edges between the nodes. Once you see a cycle, no amount of new edges will ever “disprove” the cycle. So this means that, if what you care about is cycles, then a CRDT is fine. However, let’s say you’re trying to do disturbed garbage collection of nodes that have no edges leading to them. (And as before you’re slowly learning about new edges.) You can see a node has no edges leading to it that you know of, but if you think a node of garbage-collectible you might always be proved wrong by learning about a new edge. So the problem of distributed garbage collection can’t be solved using CRDTs. There’s a paper on this that you’ll find if you google for the CALM theorem.

hardwaresofton 5y ago
Thanks for taking the time to write this out -- I'm digging into the CALM theorem right now to try and get it to sink in. This explanation is fantastic and it makes me feel like I understand the concepts better than I probably do in reality.

bla3 5y ago

That was an interesting read, thanks!

hardwaresofton 5y ago
Thanks! Hope it is a decent introductory reference -- there's so much out there.

AtlasBarfed 5y ago

This is utterly fantastic stuff. Assuming it's correct, which with Paxos...

hardwaresofton 5y ago
Don't worry you don't have to take my word for it! I left all the links in and copied some PDFs to my domain as well just to make sure people could read the actual papers with the actual insight! :)