A DISTRIBUTED, REPLICATED, DATA-BALANCED SEARCH STRUCTURE
Theodore J. Johnson, Adrian Colbrook · International Journal of High Speed Computing · 1994
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 computer systems. Our distributed B-tree (the dB-tree) replicates the interior nodes in order to improve parallelism and reduce message passing. The dB-tree stores some redundant information in its nodes to permit the use of lazy updates to maintain replica coherency. We show how the dB-tree algorithm can be used to build an efficient implementation of a highly parallel, data-balanced distributed dictionary, the dE-tree. Keywords: Concurrent dictionary data structures, Message passing multiprocessor systems, Balanced search trees, B-link trees, Replica coherency. 1. Introduction. We introduce a new balanced search tree algorithm for distributed memory architectures. The search tree uses the B-link tree [27] as a base, and distributes ow...