Distributed Data Structures and Algorithms for 
                Grobner Basis Computation
            Soumen Chakrabarti and Katherine Yelick
 
We present the design and implementation of a parallel algorithm for computing
Grobner bases on distributed memory multiprocessors.  The parallel
algorithm is irregular both in space and time: the data structures are dynamic
pointer-based structures and the computations on the structures have
unpredictable duration.  The algorithm is presented as a series of refinements
on a transition rule program, in which computation proceeds by
nondeterministic invocations of guarded commands.  Two key data structures, a
set and a priority queue, are distributed across processors in the parallel
algorithm.  The data structures are designed for high throughput and latency
tolerance, as appropriate for distributed memory machines.  The programming
style represents a compromise between shared-memory and message-passing
models.  The distributed nature of the data structures shows through their
interface in that the semantics are weaker than with shared atomic objects,
but they still provide a shared abstraction that can be used for reasoning
about program correctness.  In the data structure design there is a classic
trade-off between locality and load balance.  We argue that this is best
solved by designing scheduling structures in tandem with the state data
structures, since the decision to replicate or partition state affects the
overhead of dynamically moving tasks.