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)

See Usage Policy.

Other (Adobe PDF (2.3MB))
See Usage Policy.


Use this Persistent URL to link to this item:


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:
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
Deposited By: Imported from CaltechCSTR
Deposited On:25 Jul 2002
Last Modified:26 Dec 2012 14:10

Repository Staff Only: item control page