Distributed Hash Tables are beautiful and elegant and I love them dearly, but they have the problem where nodes that are nearby in the keyspace may not be close for communication purposes. I wonder what protocol changes will be needed when node latency starts to be measured in minutes!
With DAGs this can be pretty easily resolved by placing some kind of summary of the nodes lower down in the tree at various intervals so that one can batch fetch nodes. More generally, this problem can be solved with walk trees. Basically, you request a node, and send the server a topological query (an automata designed to walk the graph in the topology that you require starting at the requested node). This way the server can walk the graph for you eliminating the back and forth.
I developed walk trees several years ago and have yet to have time to really do a good write up on them. The best I can offer is this unfinished tutorial:
Distributed Hash Tables are beautiful and elegant and I love them dearly, but they have the problem where nodes that are nearby in the keyspace may not be close for communication purposes. I wonder what protocol changes will be needed when node latency starts to be measured in minutes!
With DAGs this can be pretty easily resolved by placing some kind of summary of the nodes lower down in the tree at various intervals so that one can batch fetch nodes. More generally, this problem can be solved with walk trees. Basically, you request a node, and send the server a topological query (an automata designed to walk the graph in the topology that you require starting at the requested node). This way the server can walk the graph for you eliminating the back and forth.
I developed walk trees several years ago and have yet to have time to really do a good write up on them. The best I can offer is this unfinished tutorial:
https://github.com/timthelion/rust-jupyter/blob/master/walk-trees-part1-zzstructures.ipynb
https://github.com/timthelion/rust-jupyter/blob/master/walk-trees-part2-walks.ipynb