- Communication-efficient parallel algorithms for distributed
random-access machines. C. E. Leiserson and B. M. Maggs,
Algorithmica, Vol. 3, 1988, pp. 53-77.
- This paper introduces a model for parallel computation called the
distributed random-access machine (DRAM). A DRAM is an abstraction
of a parallel computer in which memory accesses are implemented by
routing messages through a communication network. A DRAM explicitly
models the congestion of messages across cuts of the network. We
introduce the notion of a conservative algorithm as one whose
communication requirements at each step can be bounded by the
congestion of pointers of the input data structure across cuts of a
DRAM. We give a simple lemma that shows how to ``shortcut'' pointers
in a data structure so that remote processors can communicate without
causing undue congestion. We give O(log n)-step, linear-processor,
linear-space, conservative algorithms for a variety of problems on
n-node trees, such as computing treewalk numberings and evaluating
all subexpressions in an expression tree, and O(log^2 n)-step
conservative algorithms for problems on graphs of size n, including
finding a minimum-cost spanning forest, computing biconnected
components, and constructing an Eulerian cycle.

**Back to other
publications**

**Back to my home page**