A Distributed Data-Balanced Dictionary Based on the B-Link Tree
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Pagination or Media Count:
Many concurrent dictionary data structures have been proposed, but usually in the context of shared memory multiprocessors. In this paper, we present an algorithm for a concurrent distributed B-tree that can be implemented on message passing parallel computers. Our distributed B-tree the db-tree replicates the interior nodes in order to improve parallelism and reduce message passing. We show how the db-tree algorithm can be used to build an efficient, highly parallel, data-balanced distributed dictionary, the dE-tree. concurrent dictionary data structures, message passing multiprocessor systems, balanced search trees B-link trees, Replica coherency.
- Computer Systems