Title: A Spontaneous Overlay Search Tree

Authors:Hung-Chang Hsiao, Chuan-Mao Lin, and Chung-Ta King.

Date: January 1, 2003

Abstract

Due to the explosive information generated by billions of devices ranging from supercomputers to miniatures sensors deployed over the unreliable and untrusted ubiquity wired and wireless network, managing and manipulating this vast information becomes essential without assuming there is a reliable, powerful and trustable centralized server available. In this study, design a distributed search tree data structure, called Pyramid, which is operated atop end systems without relying on a centralized server, and artificial layout and control. Pyramid support high-level operations including search, insert, delete, update and query. A Pyramid search tree is co-managed by a set of end hosts. An end system and its atop applications can transparently store, remove and update data items it generated via created Pyramid search trees. Pyramid is based on the peer-to-peer model and its self-configuration and -healing features fulfill manipulating information in an unreliable and unstable environment. We evaluate Pyramid via simulation and the results present that a Pyramid tree is robust and data items it hosts are highly available. Two optimizations for Pyramid are also studied and they can significantly boost the performance of Pyramid. We also show a wireless application based on a prototype of Pyramid. Potential applications based on Pyramid are also discussed.