Accession Number:

ADA256841

Title:

A Distributed Data-Balanced Dictionary Based on the B-Link Tree

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1992-02-01

Pagination or Media Count:

22.0

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 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.

Subject Categories:

  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE