I recently finished a 2nd reading of DDIA and while listening to a podcast featuring an interview with Martin Kleppmann, I got so thrilled when he mentioned that he plans to release another book in the coming years.<p>DDIA is so good that I feel the same kind of anticipation I have as when waiting for a next in a series fantasy book to take me back to a parallel world with characters I've come to love and miss like one misses a good friend they haven't seen for a while.
Really nice to see BFT starting to be taken seriously in CRDT research. I had done some research in this area last year and came to a lot of the same solutions (i.e. BRB protected CRDTs when dealing with VClock based CRDTs):<p><a href="https://github.com/davidrusu/bft-crdts" rel="nofollow">https://github.com/davidrusu/bft-crdts</a><p>We ended up moving away from VClock crdts entirely for our work and going with grow-only hash-graph CRDTs as they have don't need the BRB overhead (as Martin has found in his research as well).
The idea of DAG-embedded CRDTs is far from new and was introduced here:<p><a href="https://arxiv.org/abs/2004.00107" rel="nofollow">https://arxiv.org/abs/2004.00107</a> (I'm among the authors)<p>Unfortunately, the verification that the author proposes (not accepting new updates until the dag below is verified) will need a lot of caveats for real world usage.<p>Currently we use these CRDTs for a key value database of 40M+ keys in a deployment of ipfs-cluster, which uses <a href="https://github.com/ipfs/go-ds-crdt" rel="nofollow">https://github.com/ipfs/go-ds-crdt</a> .
Woah. This paper looks freaking awesome - and surprising! “The proposed scheme can tolerate any num- ber of Byzantine nodes (making it immune to Sybil attacks)” - this is really intriguing because of the strong impossibility results in consensus algorithms around how many faulty nodes can be tolerated. I’m looking forward to reading more than just the abstract tho (confession).<p>Martin - thanks for all your cool work!
Hyper Hyper Space [1] is a library for modeling distributed data structures that uses operational CRDTs represented over a Merkle-DAG (using the partial order defined by causal relationships, like the paper describes).<p>It is also designed to work in a Byzantine environment (it can run inside a browser, using WebCrypto, WebRTC, etc. to connect to untrusted peers over the open internet).<p>[1] <a href="https://www.hyperhyperspace.org" rel="nofollow">https://www.hyperhyperspace.org</a>
> The 3f + 1 assumption means these protocols cannot be deployed in open peer-to-peer systems, since they would be vulnerable to Sybil attacks. In contrast, my approach makes no assumption about the number of Byzantine nodes.<p>I'm confused - probably because I haven't finished reading the paper.<p>1. Sybil-proof-ness requires a CA [1]. It's orthogonal to whether or not a protocol is BFT. Specifically, the classical BFT protocols "assume" there exist a CA, and then prove their protocols to be BFT.<p>2. I won't comment whether 3f+1 protocols cannot be deployed in open P2P systems (they can), but "makes no assumption about the number of Byzantine nodes" is weird. This result is valid in a particular system/time model eg. With PKI, in synchronous setting, for any `f` one can achieve consensus in `f+1` rounds using Dolev-Strong. This means you make no assumption about `n`, but the protocol is impractical for variety of reasons eg. large `n`, strong synchrony etc.<p>[1] <a href="https://www.microsoft.com/en-us/research/wp-content/uploads/2002/01/IPTPS2002.pdf" rel="nofollow">https://www.microsoft.com/en-us/research/wp-content/uploads/...</a>
Martin's writing and explanation style is truly awesome! I read his book DDIA (Designing data intensive applications) and listened to his distributed systems class lectures [1]. It was a joy learning. I wish I had him or someone like him in graduate school. I would've probably taken all his courses :-).<p>[1] <a href="https://www.youtube.com/watch?v=UEAMfLPZZhE&list=PLeKd45zvjcDFUEv_ohr_HdUFe97RItdiB" rel="nofollow">https://www.youtube.com/watch?v=UEAMfLPZZhE&list=PLeKd45zvjc...</a>
> Further work is required to demonstrate whether the techniques presented here are indeed effective in the context of particular CRDT algorithms, to prove their correctness in the face of Byzantine nodes, and to measure the performance impact of Byzantine fault tolerance.<p>This paper is super interesting, but it'd be even more interesting when we see this future work is completed.
This is pretty interesting! Skiff (<a href="https://www.skiff.org/" rel="nofollow">https://www.skiff.org/</a>) also uses private, encrypted CRDTs for their collaborative docs, but not in a BFT manner (the updates are encrypted but still sent to a central server AFAIK).