BATON: A Balanced Tree Structure for Peer-to-Peer Networks
We propose a balanced tree structure overlay on a peer-to-peer network capable of supporting both exact queries and range queries efficiently. In spite of the tree structure causing distinctions to be made between nodes at different levels in the tree, we show that the load at each node is approxima...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2005
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/30214 |
| _version_ | 1826195477591228416 |
|---|---|
| author | Jagadish, H.V. Ooi, Beng Chin Rinard, Martin C. Vu, Quang Hieu |
| author_facet | Jagadish, H.V. Ooi, Beng Chin Rinard, Martin C. Vu, Quang Hieu |
| author_sort | Jagadish, H.V. |
| collection | MIT |
| description | We propose a balanced tree structure overlay on a peer-to-peer network capable of supporting both exact queries and range queries efficiently. In spite of the tree structure causing distinctions to be made between nodes at different levels in the tree, we show that the load at each node is approximately equal. In spite of the tree structure providing precisely one path between any pair of nodes, we show that sideways routing tables maintained at each node provide sufficient fault tolerance to permit efficient repair. Specifically, in a network with N nodes, we guarantee that both exact queries and range queries can be answered in O(logN) steps and also that update operations (to both data and network) have an amortized cost of O(logN). An experimental assessment validates the practicality of our proposal. |
| first_indexed | 2024-09-23T10:13:17Z |
| format | Article |
| id | mit-1721.1/30214 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T10:13:17Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/302142019-04-12T08:25:04Z BATON: A Balanced Tree Structure for Peer-to-Peer Networks Jagadish, H.V. Ooi, Beng Chin Rinard, Martin C. Vu, Quang Hieu Balanced Tree Structure Load Balancing peer-to-peer system range query We propose a balanced tree structure overlay on a peer-to-peer network capable of supporting both exact queries and range queries efficiently. In spite of the tree structure causing distinctions to be made between nodes at different levels in the tree, we show that the load at each node is approximately equal. In spite of the tree structure providing precisely one path between any pair of nodes, we show that sideways routing tables maintained at each node provide sufficient fault tolerance to permit efficient repair. Specifically, in a network with N nodes, we guarantee that both exact queries and range queries can be answered in O(logN) steps and also that update operations (to both data and network) have an amortized cost of O(logN). An experimental assessment validates the practicality of our proposal. Singapore-MIT Alliance (SMA) 2005-12-14T18:59:56Z 2005-12-14T18:59:56Z 2006-01 Article http://hdl.handle.net/1721.1/30214 en Computer Science (CS) 398340 bytes application/pdf application/pdf |
| spellingShingle | Balanced Tree Structure Load Balancing peer-to-peer system range query Jagadish, H.V. Ooi, Beng Chin Rinard, Martin C. Vu, Quang Hieu BATON: A Balanced Tree Structure for Peer-to-Peer Networks |
| title | BATON: A Balanced Tree Structure for Peer-to-Peer Networks |
| title_full | BATON: A Balanced Tree Structure for Peer-to-Peer Networks |
| title_fullStr | BATON: A Balanced Tree Structure for Peer-to-Peer Networks |
| title_full_unstemmed | BATON: A Balanced Tree Structure for Peer-to-Peer Networks |
| title_short | BATON: A Balanced Tree Structure for Peer-to-Peer Networks |
| title_sort | baton a balanced tree structure for peer to peer networks |
| topic | Balanced Tree Structure Load Balancing peer-to-peer system range query |
| url | http://hdl.handle.net/1721.1/30214 |
| work_keys_str_mv | AT jagadishhv batonabalancedtreestructureforpeertopeernetworks AT ooibengchin batonabalancedtreestructureforpeertopeernetworks AT rinardmartinc batonabalancedtreestructureforpeertopeernetworks AT vuquanghieu batonabalancedtreestructureforpeertopeernetworks |