BIB-VERSION:: CS-TR-v2.0
          ID:: SBCS//stark/prolog.dvi
       ENTRY:: July 24, 1994
ORGANIZATION:: State University of New York at Stony Brook, Computer Science
       TITLE:: Fully Distributed, AND/OR Parallel Execution of Logic Programs
        TYPE:: Preprint
      AUTHOR:: Raman, Prabhakaran, Stark, Eugene W.
     CONTACT:: Eugene W. Stark, Department of Computer Science,
                   SUNY at Stony Brook, Stony Brook, NY 11794-4400
                   Tel: 516-632-8444 <stark@cs.sunysb.edu>
	DATE:: February, 1988
   RETRIEVAL:: HTTP from BSD7.CS.SUNYSB.EDU with the URL
		   http://bsd7.cs.sunysb.edu/~stark/REPORTS/prolog.ps.gz
       NOTES:: A version of this paper appeared as:
                   P. Raman, E. W. Stark
                   "Fully Distributed, AND/OR-Parallel Execution
                       of Logic Programs (extended abstract),"
                   Fifth International Logic Programming Conference
                   Seattle, WA,
                   1988.

ABSTRACT::

We consider a distributed model for the execution of logic programs,
in which a process is assigned to each node of the AND/OR tree for
a program, and in which each process communicates directly only with its
immediate neighbors in the tree.  We derive an interpreter, or
execution method, for this model, in which each node process maintains
in its state a set of substitutions that represents a current local
approximation to the set of answer substitutions.  Execution consists
of each process repeatedly sending its current state to
its neighbors, and updating its state using information it receives.
Eventually, ``exact'' answer substitutions accumulate at the root node,
and are output.  The interpreter supports both AND- and OR-parallelism
in a completely unrestricted fashion.  In particular, bidirectional
communication can occur between two children of the same AND-node,
a feature not present in previous work.  We prove that our interpreter
is sound and complete.  The proof, which is nontrivial, hinges on
an interesting property of information flow in the AND/OR-tree.

END:: SBCS//stark/prolog.dvi