BATON Overlay

BATON, BAlanced Tree Over-lay Network, is a distributed tree structure for peer-to-peer (P2P) systems. Different from other overlays that use a distributed hash table (DHT), such as in the Chord system, BATON organizes peers in a distributed tree to support range search. In addition, BATON tries to keep the tree in a balanced manner as the AVL tree. And hence, the search cost is bounded by O ( log ⁡ N ) {displaystyle O(log N)} . BATON, BAlanced Tree Over-lay Network, is a distributed tree structure for peer-to-peer (P2P) systems. Different from other overlays that use a distributed hash table (DHT), such as in the Chord system, BATON organizes peers in a distributed tree to support range search. In addition, BATON tries to keep the tree in a balanced manner as the AVL tree. And hence, the search cost is bounded by O ( log ⁡ N ) {displaystyle O(log N)} .