|
Abstract : |
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 riB-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., |
