Chemical Programming of Self-Organizing Systems

by Jean-Pierre Banâtre, Pascal Fradet and Yann Radenac

Chemical programming relies on the 'chemical metaphor': data are seen as molecules and computations as chemical reactions. This programming paradigm exhibits self-organizing properties and allows the description of autonomic systems in an elegant way.

The Chemical Programming Model
This formalism was proposed to capture the intuition of computation as the global evolution of a freely interacting collection of atomic values. It can be introduced through the chemical reaction metaphor. The unique data structure is the multiset (a set possibly containing identical elements), which can be seen as a chemical solution. A simple program consists of a reaction condition and an action. Execution proceeds by replacing elements that satisfy the reaction condition with the elements specified by the action. The result of such a program is obtained when a stable state is reached; that is to say, when no more reactions can take place. For example, the computation of the maximum element of a non-empty set can be described as:
replace x, y by x if x ≥ y

Any couple of elements x and y of the multiset is replaced by x if the condition is fulfilled. This process continues until only the maximum element remains. Note that in this definition, nothing is said about the order of evaluation of the comparisons. If several disjoint pairs of elements satisfy the condition, reactions can be performed in parallel.

Chemical Programming and Self-Organizing Systems
Autonomic computing provides a vision in which systems manage themselves according to some predefined goals. The essence of autonomic computing is self-organization. Like biological systems, autonomic systems maintain and adjust their operation in the face of changing components, workloads, demands and external conditions, such as hardware or software failures, either innocent or malicious. The autonomic system might continually monitor its own use and check for component upgrades. We believe that chemical programming is well suited to the description of autonomic systems. It captures the intuition of a collection of cooperative components that evolve freely according to some predefined constraints (reaction rules). System self-management arises as a result of interactions between members, in the same way as 'intelligence' emerges from cooperation in colonies of biological agents.

A Self-Organizing Sorting Algorithm
Consider the general problem of a system whose state must satisfy a number of properties but which is submitted to external and uncontrolled changes. This system must constantly reorganize itself to satisfy the properties. Let us illustrate this class of problem by a simple sorting example where the system state is made of pairs (index : value) and the property of interest is that values are well ordered (ie a smaller index means a smaller value). If the environment keeps adding random pairs to the state, the system must reorganize itself after each insertion of an ill-ordered element. The system is represented by a chemical solution "State = <sort, (i₁ : v₁),..., (i_n : v_n)>", consisting of pairs and the following active molecule:
sort = replace (i : x), (j : y) by (i : y), (j : x) if i < j and x > y

The molecule sort looks for couples of ill-ordered values and swaps them. The solution evolves up to the point where no more reactions are possible: the solution has reached a stable state and the ordering property is satisfied.

Adding new ill-ordered values breaks the 'equilibrium', since the ordering property is violated. However, sort searches continuously for new ill-ordered values and causes reactions so that the state will reach a new stable state.

This very simple example shows how chemical programming can naturally express self-organizing systems. A program is made of a collection of rules (active molecules), which react until a stable state is reached and the corresponding invariant properties satisfied. These rules remain present and are applied (without any external intervention) as soon as the solution becomes unstable again.

Examples of Applications
An autonomic mail system has been described within the chemical framework. Rules ensure that all messages have reached their destination; if it is not the case some reactions occur to reach that state. The system includes rules that ensure other autonomic properties such as self-healing (rules that set and unset emergency servers in case of failures), self-optimization (rules that balance the load between several servers), self-protection (rules that suppress spam or viruses), self-configuration (rules that forward messages to the new address of a user) and so forth.

We have also specified a chemical Distributed Versioning System. In this application, several editors may concurrently edit a document consisting of a set of files. The editors are distributed over a network and each works on a different version, making modifications to the files and committing them locally. From time to time, two or more editors merge their modifications to propagate them. This system can be easily described with reaction rules to reflect the self-organization of the system. The system is also self-repairing: if an editor loses his local version it can revert to a previous state by synchronizing with one or several other editors.

Future Plans
We are currently studying the application of this model to the coordination of program execution on grids. In a first step, applications are programmed in an abstract manner, essentially describing the chemical coordination between (not necessarily chemical) software components. In a second step, chemical service programs are specifically provided to the run-time system in order to obtain the expected quality of service in terms of efficiency, reliability, security etc.

Link:
J.-P. Banâtre, P. Fradet and Y. Radenac. Higher-Order Chemical Programming Style. In Proceedings of the Workshop on Unconventional Programming Paradigms (UPP'04), LNCS 3566. Springer-Verlag.
Also available as preprint at: http://www.irisa.fr/paris/Biblio/Papers/Banatre/BanFraRad04UPP.pdf

Please contact:
Jean-Pierre Banâtre, Pascal Fradet, Yann Radenac, INRIA/IRISA, France
E-mail: {Jean-Pierre.Banatre, Pascal.Fradet, Yann.Radenac}inria.fr