BATON Overlay
Encyclopedia
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(logN).
BATON is a binary tree. Each node in BATON keeps four kinds of links:
In each tree level, the node is named by its position in the tree. For example, node h is named 3:0, node i is named 3:1 and node p is named 4:6. For a node at position p, it will fill its left routing table by nodes at position p-2x for any valid
and fill its right routing table by nodes at position p+2y for any valid 
.
When a node wants to leave the network, it must update the routing tables of its parent node, child nodes, adjacent nodes and routing nodes. If this node is a leaf node, it can leave the network safely. Otherwise, it must find a leaf node to replace its position.
For a range query q, BATON first locats its left bound, q.low. And then the search process will travel the tree in in-order (by adjacent link), until reach the upper bound, q.up. For locating a single key, BATON performs the similar routing strategy as Chord. First, the request is routed to the farthest routing nodes which does not over hit the key. If no such routing nodes exist, the parent link, child link or adjacent link is used.
system, x notifies y to replace its position, and notifies its right adjacent node z that x will replace z's position. z then checks its right adjacent node t to see if its left child is empty. If it is, and adding a child to t does not affect the tree balance, z takes the position of t's left child as its new position and the restructuring process stops. If t's left child is full or t cannot accept x as its left child without violating the balance property, z occupies t's position while t needs to find a new position for itself by continuing to its right adjacent node.
Distributed hash table
A distributed hash table is a class of a decentralized distributed system that provides a lookup service similar to a hash table; pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key...
(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
AVL tree
In computer science, an AVL tree is a self-balancing binary search tree, and it was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. Lookup, insertion, and deletion all take O time in both the average and worst...
. And hence, the search cost is bounded by O(logN).
Architecture
- link to its parent node
- links to its child nodes
- links to its adjacent nodes in in-order
- links to the routing nodes in the same level
In each tree level, the node is named by its position in the tree. For example, node h is named 3:0, node i is named 3:1 and node p is named 4:6. For a node at position p, it will fill its left routing table by nodes at position p-2x for any valid
and fill its right routing table by nodes at position p+2y for any valid .Node Joining and Leaving
The new node's joining request will always be forwarded to the leaf node. The leaf node will check to see whether it routing table is full. If the routing table is full, this level is full of nodes and the leaf node can accept the new node as its child to create a new level node. Otherwise, it must forward the new node to take over one of the empty positions.When a node wants to leave the network, it must update the routing tables of its parent node, child nodes, adjacent nodes and routing nodes. If this node is a leaf node, it can leave the network safely. Otherwise, it must find a leaf node to replace its position.
Routing
In BATON, each node maintains a continuous key space. Once a new node joins as its child, it splits its space and assigns half of it to the child. In this partition way, if we travel the tree in in-order, we can search the whole space in ascendant order. That's why BATON supports range queries.For a range query q, BATON first locats its left bound, q.low. And then the search process will travel the tree in in-order (by adjacent link), until reach the upper bound, q.up. For locating a single key, BATON performs the similar routing strategy as Chord. First, the request is routed to the farthest routing nodes which does not over hit the key. If no such routing nodes exist, the parent link, child link or adjacent link is used.
Restructure
When a node x accepts a joining node y as its child and detects that the tree balance is violated, it initiates the restructuring process. Without loss of generality, suppose that this restructuring is towards the right. Assume that y joins as x's left child. To rebalance thesystem, x notifies y to replace its position, and notifies its right adjacent node z that x will replace z's position. z then checks its right adjacent node t to see if its left child is empty. If it is, and adding a child to t does not affect the tree balance, z takes the position of t's left child as its new position and the restructuring process stops. If t's left child is full or t cannot accept x as its left child without violating the balance property, z occupies t's position while t needs to find a new position for itself by continuing to its right adjacent node.
Load Balancing
BATON adopts two kinds of load balancing strategy. Once a node n detects that it is over loaded,- If its left or right adjacent node is light loaded, the node will transfer some data to the adjacent node to lower its load
- If its adjacent nodes are not capable to share the load, the node will invoke a process to find a randomly light loaded node in the network. The light loaded node leaves its original position and joins as the child of the overloaded node to take over part of its data. The restructure process may be invoked.