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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1992
Accession Number
ADA256841

Entities

People

  • A. Colbrook
  • T. Johnson

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computations
  • Computer Science
  • Computers
  • Control Systems
  • Dictionaries
  • Digital Information
  • Hash Tables
  • Lists (Data Structures)
  • Massachusetts
  • Mathematics
  • Multiprocessors
  • Multithreading
  • Processing Equipment
  • Trees (Data Structures)

Fields of Study

  • Computer science
  • Engineering

Readers

  • Graph Algorithms and Convex Optimization.
  • Materials Science.
  • Parallel and Distributed Computing.