2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ If I understand correctly, the Chord algorithm constructs a hashtable? If it does so well, average search time is constant -- that's way better than what AVL can do. $\endgroup$ – Raphael Dec 3 '14 at 11:46
  • $\begingroup$ it's not exactly a hash table. It places nodes in a ring and each node points to some others. When a search query comes to a node the node knows where to search or where to redirect the search based on what he knows. It's somewhat of a hashtable but not completely. Both Chord algorithm and an AVL tree need to be reconfigured in cases a new node arises or a dead one comes back to life $\endgroup$ – John Demetriou Dec 3 '14 at 11:48
  • $\begingroup$ It's a distributed hash table. Each node has "fingers" that point to other nodes. It is not stored in a single location that helps finding all nodes at once. Search time for Chord is usually $logN$. Similar to AVL $\endgroup$ – John Demetriou Dec 3 '14 at 12:04
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What if the AVL is simply pointers and a search query can go to each of the nodes in the tree? But then again there is no going up the tree in this way $\endgroup$ – John Demetriou Dec 3 '14 at 13:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.