Item

Abstract

We describe new randomized parallel algorithms for the problems
of interval allocation, construction of static dictionaries,
and maintenance of dynamic dictionaries.
All of our algorithms run optimally in constant time
with high probability.
Our main result is the construction of
what we call a \emph{perfect dictionary}, a scheme that
allows $p$ processors implementing a set $M$
in space proportional to $|M|$
to process batches of $p$ \emph{insert}, \emph{delete},
and \emph{lookup} instructions on $M$ in
constant time per batch.

Our best results are obtained for a new variant of
the CRCW PRAM model of computation called the
OR PRAM.
For other variants of the CRCW PRAM we show slightly
weaker results, with some resource bounds
increased by a factor of $\Theta(\log^k n)$,
where $k\in\IN$ is fixed but arbitrarily large.