Name
Abstract | ||
|---|---|---|
We present the first snap-stabilizing distributed binary search tree (BST) algorithm. A snap-stabilizing algorithm guarantees that the system always behaves according to its specification provided some processor initiated the protocol. The maximum number of items that can be stored at any time at any processor is constant (independent of the size (n) of the network). Under this space constraint, we show a lower bound of Ω(n) on the time complexity for the BST problem. We then prove that starting from an arbitrary configuration where the nodes have distinct internal values drawn from an arbitrary set, our algorithm arranges them in a BST order in O(n) rounds. Therefore, our solution is asymptotically optimal in time and takes O(n) rounds. A processor i requires O(logsi) bits of space where si is the size of the subtree rooted at i. So, the root uses O(logn) bits. The proposed algorithm uses a heap algorithm as a preprocessing step. This is also the first snap-stabilizing distributed solution to the heap problem. The heap construction spends O(h) (where h is the height of the tree) rounds. Its space requirement is constant (independent of n). We then exploit the heap in the next phase of the protocol. The root collects values in decreasing order and delivers them to each node in the tree in O(n) rounds following a pipelined delivery order of sorted values in decreasing order. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11577327_1 | Self-Stabilizing Systems |
Keywords | Field | DocType |
bst order,space constraint,bst problem,optimal binary search tree,heap construction,heap algorithm,binary search tree,pipelined delivery order,heap problem,snap-stabilizing algorithm guarantee,proposed algorithm,lower bound,time complexity | Discrete mathematics,Combinatorics,Prim's algorithm,Min-max heap,Optimal binary search tree,Heap (data structure),Binary heap,Time complexity,Binary search tree,Mathematics,d-ary heap | Conference |
Volume | ISSN | ISBN |
3764 | 0302-9743 | 3-540-29814-2 |
Citations | PageRank | References |
8 | 0.58 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Doina Bein | 1 | 103 | 21.64 |
| Ajoy K. Datta | 2 | 369 | 35.83 |
| Vincent Villain | 3 | 544 | 45.77 |