CaltechAUTHORS
  A Caltech Library Service

The Balanced Cube: A Concurrent Data Structure

Dally, William J. and Seitz, Charles L. (1985) The Balanced Cube: A Concurrent Data Structure. California Institute of Technology . (Unpublished) http://resolver.caltech.edu/CaltechCSTR:1985.5174-tr-85

[img]
Preview
Postscript
See Usage Policy.

2589Kb
[img]
Preview
Other (Adobe PDF (2.3MB))
See Usage Policy.

2231Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechCSTR:1985.5174-tr-85

Abstract

This paper describee the balanced cube, a new data structure for implementing ordered seta. Conventional dats structures such as heaps, balanced trees and B-trees have root bottlenecks which limit their potential concurrency and make them unable to take advantage of the computing potential of concurrent machines. The balanced cube achieves greater concurrency by eliminating the root bottleneck; an operation in the balanced cube can be initiated from any node. The throughput of the balanced cube on a concurrent computer is O times O/Log N compared with O(1) for a conventional data structure. Operations on the balanced cube are shown to be deadlock free and consistent with a sequential execution ordered by completion time.


Item Type:Report or Paper (Technical Report)
Group:Computer Science Technical Reports
Record Number:CaltechCSTR:1985.5174-tr-85
Persistent URL:http://resolver.caltech.edu/CaltechCSTR:1985.5174-tr-85
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26957
Collection:CaltechCSTR
Deposited By: Imported from CaltechCSTR
Deposited On:25 Jul 2002
Last Modified:26 Dec 2012 14:10

Repository Staff Only: item control page