# 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?

• 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. – Raphael Dec 3 '14 at 11:46
• 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 – John Demetriou Dec 3 '14 at 11:48
• 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 – John Demetriou Dec 3 '14 at 12:04

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.