Tweeted twitter.com/#!/StackCompSci/status/540547878486564865
2 edited tags
| link
1
source | link

Use AVL trees instead of Chord algorithm for Distributed Peer to peer Hash tables

In distributed systems we use the Chord algorithm to create a p2p distributed hash table. While this algorithm is very useful and efficient wouldn't it be better if we used an AVL tree? Chord algorithm relies a lot to the hash function (in order for the nodes to be distributed evenly).

An AVL tree on the other is always balanced so in the worst case it will take $O(h)$ time to search for something, whereas h is the height of the tree and given that AVL trees are always balanced the height of the tree is at most $logN$ (whereas N is the number of living nodes in the network).

In my opinion AVL trees can give the same search speed (or maybe even better). So what is the need to use Chord algorithm instead of an AVL tree? I understand that Chord Algorithm is more of a Peer to peer system as many nodes know many others while in an AVL tree each node knows two descendants. Is this the sole purpose of not using AVL trees?

Is there an issue with handling churns that makes one better than the other?