讲座时间:2005年3月14日下午2:20
讲座地点:曹光彪西楼101教室
讲座题目: BATON: Supporting Range Queries in an Overlay P2P Network
讲座内容的介绍:
Abstract:
Peer-to-Peer (P2P) systems have become popular recently. The
central strength of P2P systems is the capability of sharing
resources so that larger costly servers can be replaced by systems of smaller computers. The biggest challenge in building an effective P2P system is in tying together these multiple autonomous computers into a cohesive system. This is usually done by means of a logical ``overlay network'' used to organize the data managed by these computers, which represent nodes in this overlay network. Various topologies have been suggested for this network, including a ring , and a multi-dimensional grid. With several of these overlays, it is well-known how to build ``distributed hash tables'' across nodes in a P2P system. However, these structures are not able to support range queries effectively.
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(log N)$ steps and also that update operations (to both data and network) have an amortized cost of $O(log N)$. An experimental assessment validates the practicality of our proposal.
Biography:www.comp.nus.edu.sg/~ooibc
讲座地点:曹光彪西楼101教室
讲座题目: BATON: Supporting Range Queries in an Overlay P2P Network
讲座内容的介绍:
Abstract:
Peer-to-Peer (P2P) systems have become popular recently. The
central strength of P2P systems is the capability of sharing
resources so that larger costly servers can be replaced by systems of smaller computers. The biggest challenge in building an effective P2P system is in tying together these multiple autonomous computers into a cohesive system. This is usually done by means of a logical ``overlay network'' used to organize the data managed by these computers, which represent nodes in this overlay network. Various topologies have been suggested for this network, including a ring , and a multi-dimensional grid. With several of these overlays, it is well-known how to build ``distributed hash tables'' across nodes in a P2P system. However, these structures are not able to support range queries effectively.
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(log N)$ steps and also that update operations (to both data and network) have an amortized cost of $O(log N)$. An experimental assessment validates the practicality of our proposal.
Biography:www.comp.nus.edu.sg/~ooibc
