Distributed systems come in a number of forms. In the broadest terms, they range from tightly coupled to loosely coupled. The coupling is seen in both the instruction path and the data path. For most problems, decoupling the instructions for distribution is not that hard. Decoupling data is a difficult problem to solve for the general case, however.
This work deals with the problems of decoupling the instruction streams automatically for a set of tightly coupled data stream problems. The implementation is in Prolog. The experiments were directed at seeing how well a logic problem could be distributed over several processors in an automatic way that was determined near runtime.
Most of the work centers on determining how to distribute the problem. This is never an easy task. If the data objects are not tightly coupled across instruction streams, the problem is much easier to solve, since the difficulty in such problems is ensuring that the global copies of shared data objects are current in all local copies. No general way to ensure consistency of those data objects across all copies is known. There are methods, however, that based on assumptions about the coupling of the variable can tell how much inconsistency can be allowed while still converging on the correct solution.
In the experiments that are discussed, assume that the problems are such that there is a single set of global variables that are tightly coupled across all the data streams (the single instruction path single data path machine model). This means the parallel processes request a copy of the data at set checkpoints from a central processor. The underlying design may be extended to multiple instruction path multiple data path (MIMD) systems with major caveats.
The authors demonstrate that it is possible to effectively distribute a flat Prolog problem over a number of processors at runtime as long as the instruction stream across the processor is in step and the global data objects are centrally controlled. This results is known for non-logic-oriented distributed problems. For those involved in large rule-based AI systems, the results may be interesting, however.
The theorems about how to divide a problem and distribute the data may interest those who specialize in distributed data theory. None of the results are surprising, however, although the results with respect to the distribution and control of logic variables and sequences should interest those working on distributed Prolog systems.