📖Merkle Search Trees: Efficient State-Based CRDTs in Open Networks

merkle-trees can be used to rapidly identify set-differences (ref dynamo paper)

Merkle search tree is a way to construct merkle tree that preserve order of keys while keeping the tree balanced.

To keep merkle tree balanced, the dynamo implementation had to hash all keys to make distribution uniform, thus destroying ordering.

This destruction of order decreases performance where consecutive keys are updated together (which is quite often the case in real life). (as more subtrees will get updated. with order preserved, all updates would be clumped in fewer subtrees, so less data needs to be transferred.)

merkle search tree can be used to build an ordered log of events, which can then be used to distribute updates (ensuring causal delivery) and build other crdts on top

compared to scuttlebutt, merkle search tree performs best with low rate of events

• merkle search trees scale better with the number of nodes in the network, as communication costs only depend on the rate of message and not the number of nodes