Unstructured Communication Schemes

BAP Online Manuals : Bap Language Tutorial : Parallelism with Brain Aid Prolog : Unstructured Communication Schemes
Previous: Continuos against Burst Mode
Next: BAP Communication Layers

2.3.5. Unstructured Communication Schemes

Boiled down to the pragmatic level 'unstructured communications' means that the communication structure of a system may depend on runtime conditions (in opposition to the static communication of a pipeline or a farm). Unstructured communication simply means that any object or process may exchange messages with any other. The user is responsible for the elimination of deadlocks and the resource management within such an 'unstructured' application.

The following chapters will explain a few techniques for this class of algorithms.

Academic institutions have developed a huge amount of new communication schemes and paradigms in the recent years, some very different from farms or pipelines. Some of these approaches are designed to fit certain problems and reach high performance.

BAP supports all of these new ideas by providing a very general message passing mechanism (on the object layer, an even more general mechanism exists at the process layer, but this is more difficult to use).

The idea is to use the message operators ('Obj -> Msg' and 'Obj <-> Msg') for simple asynchronous and synchronous message passing. Objects may to some extent be thought of as processes, so a BAP system can be understood as pool of communicating processes. This is the most general paradigm within the CSP model. Any user specific communication scheme may be implemented on top of it. This includes techniques like 'black board' (Linda), bound variable synchronization (Strand 88), chained frame architecture (used in many expert system shells), AND/OR parallel logic language execution and many more. Some of these techniques are already implemented using BAP. Please consult the list of example programs.

Black Board

The idea of a Black Board communication scheme is that one global 'black board' manages the communication of many distributed processes or objects. It serves as a global scheduler that coordinates and distributes work.

Many objects or processes (which means the same in this context) are spread over the net and partially perform some task. Pending tasks (that can not be solved by such an object) are sent back to the blackboard, are sorted or otherwise processed there and finally distributed to (other) suitable objects.

At a glance the communication structure of the blackboard seems to be similar to the farm. There are however several major differences:

the participating objects (before: servers) keep their state during the execution of the application
the actual communication depends on the results of other computations. Within the farm, the communication is determinated by distribution scheme of the program and the execution time of the server processes.
it is possible to generate or kill objects during the runtime of the application. This is not indended with the farm.

Features:

more flexible communication structure than a farm or pipeline
potential for optimization by grouping messages for one object.
rather easy debugging by tracing the tasks in the black board
knowledge about application status and object ids is centralized in the blackboard

Problems:

all communication is directed towards the blackboard so that this process is likely to become a bottleneck

Distributed Objects

Distributed Objects are quite similar to the idea of the Black Box, but do not use a centralized scheduler (the black board). Instead each object (or processes) has the knowldge about related object (ids) and directly communicates with each other.

Features:

most flexible communication structure
no bottleneck due to the decentral communication of the objects
potential of hirarchically structured application on large networks

Problems:

the user has to overtake responsibility for the resource handling
system status and object ids are spread over the network
overhead caused by the system information that exists in many copies in the communicating objects
the most flexible communication structure requires the most effort to control

Forward Inference and Demons

Forward Inference is a special form of the Distributed Objects communication scheme. Here objects reason about data, update their state and then update the state of other objects by sending suitable messages. A system that communicates in such a manner acts as a forward inference engine.

A Demon is thought of as a process that supervises the state of a variable and takes some action in case of a change, an initialization or similar events. Demons are easily implemented as part of the messages that are executed to change certain (database) values and work similar to the the forward inference scheme.

Related topics:

Distributed Objects , Black board