Abstract | ||
---|---|---|
Search algorithms are a key issue to share resources in large distributed systems as peer networks. Several distributed interconnection structures and algorithms have already been studied in this context. With expanding ring algorithms, the efficiency of searches depends on the topology used to send query requests and the dynamics of the structure. In this paper, we present an interconnection structure that limits the number of messages needed for search queries. This structure, called Distributed Spanning Tree (DST), defines each node as the root of a spanning tree. So, it behaves as a tree for the number of messages but it balances the load generated by the requests among computers, and thus, it avoids to overload the root node. This structure is scalable because it needs only a logarithmic memory space per computer to be maintained. A formal and practical description of the structure is presented and we describe traversal algorithms. Simulations show that DST-based searches behave better than randomly generated graphs and trees as it generates less messages to query all computers while avoiding the tree bottlenecks. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1109/TPDS.2009.22 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
tree structure,practical description,interconnection structure,search algorithm,search query,root node,query request,dst-based search,logarithmic memory space,key issue,tree bottleneck,tree graphs,distributed systems,indexing terms,network topology,distributed system,computer networks,search algorithms,broadcasting,computational modeling,tree data structures,computer simulation,spanning tree | Tree traversal,Distributed minimum spanning tree,Computer science,Theoretical computer science,Spanning tree,Segment tree,Fractal tree index,Search tree,Minimum spanning tree,Distributed computing,Interval tree | Journal |
Volume | Issue | ISSN |
20 | 12 | 1045-9219 |
Citations | PageRank | References |
4 | 0.46 | 15 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sylvain Dahan | 1 | 7 | 1.35 |
Laurent Philippe | 2 | 71 | 12.95 |
Jean-Marc Nicod | 3 | 95 | 18.10 |