[Solved]: Use AVL trees instead of Chord algorithm for Distributed Peer to peer Hash tables

Problem Detail: 

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?

Asked By : John Demetriou

Answered By : Peter

Chord is meant to be used in a distributed system where we need to be concerned with load balancing and handling failures of individual machines.

If you try to maintain an AVL tree in a distributed system by spreading the nodes among the available machines, the machine that has to take care of the root node will have a very high load as it is involved in every single request. Moreover, if this machine failed, the AVL tree would be partitioned, which requires you to introduce additional pointers for redundancy (similarly to what is done in Chord using "fingers").

A data structure that is suitable for distributed systems are Skip Graphs, which essentially have the same functionality as balanced trees, in particular, they provide $O(\log n)$-time operations. Moreover, a Skip Graph has built-in fault-tolerance (i.e. can handle churn), as it contains an expander graph as a subgraph (with high probability), and therefore can withstand even a constant fraction of node failures.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33783

3.2K people like this

 Download Related Notes/Documents