Higher level parallel programming models express parallelism in an implicit way. Instead of imposing programmers to create multiple tasks that can run concurrently and handle their communications and synchronizations explicitly, these models allow programs to be written without assumptions of artificial sequenciality. The programs are naturally parallel. Examples of such kind of models include the Chemical Reaction Models (CRMs) (Banatre & Le Metayer, 1990 & 1993), Linda (Carriero & Gelernter, 1989), and Unity (Chandy & Misra, 1988; Misra, 1989). These models are created to address higher level programming issues such as formal program specification, program synthesis, program derivation and verification, and software architecture. Efficient implementation of these models has limited success and therefore obscures its direct applications in software design (Creveui, 1991; Gladitz, 1996). Despite this limitation, efforts have been made in both academic and industrial settings to avail these models in real-world programming. For example, Unity has been used in industrial software design and found successful; execution efficiency of Linda has been affirmed by experiments and it is implemented by IBM Tuple Space. Recent discussions of these models in multi-agent system design have also been found in literature (Cabri, 2000). In the following discussion, we focus on the Chemical Reaction Models and its applications.

The Chemical Reaction Models describe computation as “chemical reactions”. Data (the “solution”) are represented as a multiset. A set of “reaction” rules is given to combine elements in the multiset and produce new elements. Reactions take place until the solution becomes inert, namely there are no more elements can be combined. The results of computation are represented as the inert multiset. Gamma is a kernel language in which programs are described in terms of multiset transformations. In Gamma programming paradigm, programmers can concentrate on the logic of problem solving based on an abstract machine and are free from considering any particular execution environment. It has seeded follow-up elaborations, such as Chemical Abstract Machine (Cham) (Berry & Boudol, 1992), higher-order Gamma (Le Metayer, 1994; Cohen & Muylaert-Filho, 1996), and Structured Gamma (Fradet & Le Metayer, 1998). While the original Gamma language is a first-order language, higher order extensions have been proposed to enhance the expressiveness of the language. These include higher-order Gamma, hmm-calculus, and others. The recent formalisms, γ-Calculi, of Gamma languages combine reaction rules and the multisets of data and treat reactions as first-class citizens (Banâtre, Fradet, & Radenac, 2004, 2005a, 2005b). Among γ-Calculi, γ0-Calculus is a minimal basis for the chemical paradigm; γc-Calculus extends γ0-Calculus by adding a condition term into γ-abstractions; and γn-Calculus extends γ0-Calculus by allowing abstractions to atomically capture multiple elements. Finally, γcn-Calculus combines both γc-Calculus and γn-Calculus. For notational simplicity, we use γ-Calculus to mean γcn-Calculus from this point on.

The basic term of a Gamma program is molecules (or γ-expressions), which can be simple data or programs (γ-abstractions). The execution of the Gamma program can be seen as the evolution of a solution of molecules, which react until the solution becomes inert. Molecules are recursively defined as constants, γ-abstractions, multisets or solution of molecules. The following is their syntax:

The multiset constructor “,” is associative and commutative (AC rule). Solutions encapsulate molecules. Molecules can move within solutions but not across solutions. γ-abstractions are elements of multisets, just like other elements. They can be applied to other elements of the same solution if a match to pattern P is found and condition C evaluates to true and therefore facilitate the chemical reaction. The pattern has the following syntax:

where x is a variable. In addition, we allow for the use of tuples (written x1:… : xn) and names of types. For example, γ-abstraction

can be interpreted as: replace x, y by x if x ≥ y, which is equivalent to finding the maximum of two integers.

The semantics of γ-Calculus is defined as the following:

(γp[c].m1), m2 = фm1 if match(p/ m2) = ф and фc ; γ-conversion

m1, m2 = m2, m1 ; commutativity

m1, (m2, m3) = (m1, m2), m3 ; associativity

E1 = E2 => E[E1] = E[E2] ; chemical law

The γ-conversion describes the reaction mechanism. When the pattern p matches m2, a substitution ф is yielded. If the condition фc holds, the reactive molecules γp[c].m1 and m2 are consumed and a new molecule фm1 is produced. match(p/m) returns the substitution corresponding to the unification of variables if the matching succeeds, otherwise it returns fail.

Chemical law formalizes the locality of reactions. E[E1] denotes the molecule obtained by replacing holes in the context E[ ] (denoted by [ ]) by the molecule E1. A molecule is said to be inert if no reaction can be made within:

A solution is inert if all molecules within are inert and normal forms of chemical reactions are inert γ-expression. Elements inside a solution can be matched only if the solution is inert. Therefore, a pattern cannot match an active solution. This ensures that solutions cannot be decomposed before they reach their normal form and therefore permits the sequentialization of reactions. The following inference rule governs the evolution of γ-expressions:

For example, if a list is represented by multiset M = {(a, i) | a is value and i an index and i’s are consecutive}, the following recursive γ-abstraction replaces any ill-ordered pairs by two other pairs:

It specifies that any two selected pairs (a, i) and (b, j) that satisfy the condition, i < j ∧ a > b are replaced by two other pairs (b, i) and (a, j), and a copy of itself. No global control is imposed on the way multiset elements are selected to ignite the reaction. If sigma is placed in an initial set M0 of pairs, it will replace ill-ordered pairs until the entire list is sorted. So a sorting program can be defined as:

We found that the dynamic nature of distributed agents makes it an ideal object for modeling using the Gamma languages (Lin, 2004). An agent shows a combination of a number of characteristics, such as autonomy, adaptability, knowledge, mobility, collaboration, and persistence. These features exist in different types of agent systems such as collaborative agents, interface agents, reactive agents, mobile agents, information agents, heterogeneous agents, and economic agents. The concurrency and automation of agents require that the modeling language does not have any sequential bias and global control structure. In addition, the dynamic nature and non-determinism of interaction between an agent and its environment are suited to a computation model with a loose mechanism for specifying the underlying data structure. For example, data, which move around the Internet, can be well modeled by chemical solution; and mobile agents, which are created dynamically and transferred from clients to servers, can be represented as molecules containing γ-abstractions that transfer among solutions. This provides a mechanism for describing inter-agent communications and agent migration in a single framework. It is notable that CRM specifications separate architectures from nonessential features of the system effectively. For example, it catches the way program units interact with one another and leaves nonessential specifications, such as the number of program units, connection links for communications, and organizations of data, to the subsequent design phases.

We refer the readers to the literature for detailed justifications for the appropriateness of using the CRM to model MAS (Lin & Yang, 2006; Lin, 2007a, 2007b, 2007c; Ma et al, 2007). Here we give the summary of the benefits of using the CRM to model MAS: (1) The architectural design of the system can be separated from the design of individual units that have to deal with proprietary features of the underlying computing resources, because CRM allows us to treat each node in the distributed networking systems as an element of a multi-set data structure, which in-turn can be an active program to be defined in a lower level of the program structure. (2) Parallelism can be easily achieved without extra efforts in designing communication and synchronization mechanism because CRM express them implicitly. (3) Concurrency and dynamic nature of MAS can be easily reflected by CRM’s non-determinism feature. (4) Autonomy can be expressed naturally by CRM’s locality of reaction feature. (5) Combining different programming technologies is made feasible in Gamma framework because no assumptions are made about the way for implementing each node in the system hierarchy. (6) The reusability of the agent systems can be promoted by higher-order CRM languages because the existing agents can be combined by using higher-order operations defined in those languages.

A special issue in a distributed system is that the system is composed of interacting, but independent program units, each has its own data domain; and the architectural design focuses on the conversation among these units (Lin, Norrie, Flores, & Kremer, 2000; Lin, Lin, & Holt, 2003). A conversation is a sequence of messages involving two or more agents and centering on a set of pre-designated topics, intended to achieve a particular purpose. To correctly and efficiently engineer software architecture, we can model and specify agent interactions in distributed learning as conversation schemata, in which interaction patterns and task constraints in collaborative agent systems are constructed within class hierarchies of conversation schemata. For example, let’s consider an online course material maintenance system. The conversation schema is shown in Figure 1. As we know of e-learning systems, the online course materials are updated often in order to keep them as current as possible, esp. in some rapidly changing fields like “computing and information systems”. As part of the duty of the course instructor in his/her effort to make the necessary adjustments for the benefit of students, whenever there’s a significant change in the content of several designated web pages of online course materials, he/she should notify by e-mails the students who are taking the course and those who are interested in the topic. The conversation model of the system consists of the following core elements:

Figure 1: The conversation schema of course maintenance

There are two databases used by this system:

Note that although we will focus on modeling the agent conversation in the following discussion, we would like to point out that by no means we are talking about the entire system for e-learning. Our point is to describe our methodology to specify agent conversation in a distributed system.

Based on the above conversation schema, the following constraints apply:

A1: If the instructor makes any update (u) on any topic link (l), a notification message (n) is generated to notify the change made on the topic link.

A2. For any notification message (n) that is generated to notify a change made on any topic link (l), an email (e) is sent to deliver the notice.

A3. For any email (e) that is generated to deliver any notice (n), the email to sent to all students.

The design goal of the system conversation schemata is that for any update made by the instructor, an email notification is sent to all students. A predicate logic specification of the goal is:

However, the goal is not verifiable with respect to the given input because the input (viz., the update u) and the output (viz., the email e) are not handled by the same agent. Based on constraint A3, we can create a sub-goal (goal2) to check that any notice (n) leads to the creation of an email (e). This can be done by the Notification Agent (NT). However, although goal2 checks domain NF, it still does not contain input u. Using A2, we obtain another sub-goal (goal1) to check that a notification (n) is created when a change is made on a topic link (l) and this can be done by the Monitoring Agent (MT). With a similar deduction using A1, we obtain goal0 to ensure a change on the topic link (l) is made according to the update (u) and this is done by the Maintenance Agent (MA). Note that the input and output of the sub-goals form a pipelining structure:

A Gamma program of goal0 can be constructed as:

where MA[u, l] denote the molecule constructed to verify specification MA(u, l).

Similarly, <goal1> can be constructed as:

Because the input l in <goal1[l]> is computed using expression:

the verification program should be:

With similar reasoning, we can construct:

To construct the program for

we firstly construct the program for

we get:

Then we have:

Though we omitted some details of the construction process of the above program, we would like to point out that these programs can be constructed using predefined rules and the process can be semi-automated (Lin, 2007a). This sample application of the Chemical Reaction Model shows that parallelism can be achieved in a very high level and this approach is especially suitable to address architectural design issues of a large software system. Interested readers are welcome to contact the author at linh@uhd.edu.

Content actions

Footer

This work is licensed by Hong Lin under a Creative Commons Attribution License (CC-BY 2.0), and is an Open Educational Resource.

Last edited by Hong Lin on Jan 22, 2009 2:59 pm US/Central.