In our case the individuals are the adaptor agents that we will place between communication partners. Representing the programs we place in an adaptor can be done in a number of different ways: we can use Scheme [10], Java [3] or other human-used languages as a representation. The problem with this is that human-usable languages are very verbose and the space of valid programs is very small. If we would generate a random program, there is 99% chance it won't even be syntactically correct. Therefore we choose another (well known) format for our programs: classifier systems. These will be explained in section 6.

A problem of genetic algorithms, and learning systems in general, is that they cannot learn what they do not see. How can we make sure that our adaptors/individuals have enough input from the environment to make correct decisions ? This will be discussed in the next section.

How can we make sure that our concurrency adaptors have enough input from the environment ? Our concurrency adaptors should at least know

1. which state the client agent expects the server to be in. (or the projected client-state).
2. in which state the server agent is.

Representing the state and state-transitions of an agent will be done by means of Petri-nets [11]. Petri-nets offer a model in which we can have multiple actors which each go from state to state by means of state transitions. Both concepts, the states as well as the state transitions, are modelled.

Figure:semaphore locking strategy, described in a Petri-net. The red boxes (marked with *) are the messages which either comes in are goes out. The blue ones (marked with **) are exactly the opposite.

For example, in figure 4 one sees how a binary semaphore locking strategy is modelled. States are shown as circles, while transitions are shown as boxes. The current state unlocked is coloured in yellow (marked with a '!'). From this state the agent requiring this interface, can choose only one action: lock. When it chooses this action, it is in the locking state until lock_true or lock_false comes back. Note that we can also use this Petri-net to model the behaviour of an agent which provides this interface. It is perfectly possible to offer an interface which adheres to this specification, in which case, the incoming lock is initiated from the client, and lock_true or lock_false is sent back to the client when making the transition.

Figure 5:Counting semaphore locking Strategy described as a Petri-net.

Figure 5 represents the counting semaphore locking strategy. One sees how a transition can only be made when a certain condition holds true: an agent can only unlock when it has a lock count which is larger than 0. The agent state holds this extra field: ?lockcount.

In the next section we will discuss the representation we will use for our adaptors (the individuals in the genetic algorithm). To be able to make correct decisions this representation needs enough input from its environment. In our experiment we use the petri-net states as input for our adaptors.

Adaptors should ease the semantic differences between two agents. Since we want to learn this we need to specify our programs in some kind of way. We choose to use classifier systems for this because it is simple, contains a memory and is Turing complete.

A classifier system [12] is a system which has an input interface, a classifier-list and an output interface. The input and output interface put and get messages to and from the classifier-list. The classifier list takes a message list as input and produces a new message list as output. Every message in the message list is a set of bits (0 or 1) which are matched against a set of classifiers. A classifier, also called a classifier rule, contains a number of (possible negated) conditions and an action. We will work with four conditions.

Conditions and actions are both ternary strings which can contain 0, 1 or #. A '#'-character is a pass-through which, in a condition, means 'either 0 or 1 matches'. If found in an action, we simply replace that character with the character from the original message (see figure 6).

Figure 6: Illustration of how actions produce a result when the condition matches. ~ is negation of the next condition. In this illustrative example only two conditions are used.

Such a classifier system will need to reason about the actions to be performed based on the available input. The input of a classifier system consists of a full description of the client state, a full description of the server state and possible the requested actions from either the client or the server. To be able to distinguish all those different kinds of messages we reserve the 3 first bits in every message for internal use (shown in figure 9). After the first 3 bits comes either some domain dependent description of the state (of client or server), or a domain dependent description of the action which should be taken.

Figure 7: The first 3 bits of a classifier message describes what kind of message it is.

If we consider for example actions coming from the client, it would contain the name of the message and the position. The possible actions sent to the client are return of different function calls. On server side, the outgoing actions are returns from function calls and the incoming actions are the calls which can be executed upon the server. Figure 8 illustrates this.

Figure 8: Possible client and server actions. Please note that the symbols are bit- encoded in practice.

The representation of the Petri-net state offered by both agents will us the semantics described in figure 9. We model the full state representation one classifier message. We define the semantics of our messages as a 14 bit tuple (shown in figure 9), where the first 7 bits are the possible server actions, the next 7 bits represent the possible client actions. In our example we do not model the petrinet states of client of server, but only the petri-net transitions, because it reduces the complexity and expresses the same.

Figure 9: L = lock; L#t = lock_true; L#f = lock_false; U = unlock; U# = unlock_done; A = act; A# = act_done. A bit is set when either a certain action is possible or a certain action is required.

With these semantics for the messages, simply translating a request from the client to the server requires 1 rule. Another rule is need to translate requests from the server to the client (see figure 10).

Figure 10: Blind translation between client and server agents. Column condition 2 to 4 are omitted because they are not neceassary.

Although this is a simple example, more difficult actions can be represented. Suppose we are in a situation where the client uses a nested-locking strategy and the server uses a non-nested locking strategy. In such a situation we don't want to send out the lock-request to the server if there is a lock count is larger than zero. Figure 11 shows how we can represent such a behaviour.

Figure 11:Translating a client-lock to a server lock when necessary.

As seen in section 4 a genetic algorithm requires individuals to test. We defined our individuals as classifier systems. They form the chromosomes of the genetic algorithm while the classifier conditions and actions are the genes. This method of using full classifier systems is also known as the Pittsburgh approach.

Individuals are initially empty. Every time a certain situation arises and there is no matching gene we will add a new gene. This gene, which is a classifier rule has a matching condition with a random action on the server and/or the client from the list of possible actions. This guarantees that we don't start with completely useless rules which cover situations which will never exist and allows us to generate smaller genes which can be checked faster.

Mutating individuals is done by randomly adapting a number of genes. A gene is adapted by selecting a new random action.

To create a crossover of individuals we iterate over both classifier-lists and each time we decide whether we keep the rule or throw it away.

Fitness is measured by means of a number of test-sets (which will be discussed in the next section). Every test-set illustrates a typical behaviour (scenario) the client will request from the server. The fitness of an individual is determined by how far the scenario can execute without unexpected behaviour. Of course this is not enough, we should not have solutions which completely avoid the server. For example, return lock_true every time a request comes in from the client, without even contacting the server. To avoid this kind of behaviour from our algorithm the test-set will need a covert channel over which it can contact the server to verify some things.

Figure 12:The setup of the system.

The experiment (pictured in 12) is set up as a connection broker between two components. The first component tries to make contact with the server by means of the broker. Before the broker sets up the connection it will generate an adaptor between the two parties to mediate slight semantic differences. It does this by requesting a test-agent from both parties. The client will produce a test-client and a test-scenario. The server will produce a test-server. In comparison with the original agent, these testing agents have an extra testing port, over which we can reset them. Furthermore, this testing port is also used as the covert channel for validating actions at the server.

The genetic algorithm, using a gene pool of 100 agents, will now use the test-agents to measure the fitness of a particular classifier system. Only when a perfect solution is reached; ie a correct adaptor has been found, the connection is set up.

The scenarios offered by the client are the ones which will determine what kind of classifier system is generated. We have tried this with three scenarios. Scenario 1 is a sequence: [lock(), act(), unlock()] x 3. (See figure 13) Scenario 2 is basically the same: [lock(), act(), act(), unlock()] x 3. The reason why we added such a second look-alike scenario will become clear in our observations. The third scenario is the case we explained earlier in the paper.

Figure 13:The three test scenarios we used to measure the fitness of an adaptor. The dashed vertical lines are waits for a specific message (Eg: Lock_true).

If we don't use the covert channel to check the actions at the server side, the genetic algorithm often creates a classifier which doesn't even communicate with the server. In such a situation the classifier would immediately respond lock_true whenever the client requests a lock.

If we use the covert channel to measure the fitness more accurately, we see that a perfect solution is created within approximately 11 generations. In this case the fitness of each individual was measured by scenario 1 and scenario 3. See figure 14.

Figure 14:Fitness of the individuals in each generation

One of the learned classifiers developed a strange behaviour. Its fitness was 100%, but it worked asynchronously, as illustrated in figure 15. At the moment an act request arrived from the client it sent this message to the server, which would respond with act_done. In response to this act_done the adaptor would automatically send back an unlock operation to the server. The server would respond with unlock_done, to which the classifier would send an act_done to the client. The client in its turn now send a lock_request which immediately results in an unlock_done from the classifier.

Figure 15:How an adaptor anticipates the next request from the client and afterwards fakes a correct response.

This example shows how such a learned algorithm can anticipate future behaviour.

A problem we encountered was the fact that sometimes, the adaptor anticipates too much and after the first act, doesn't stop acting anymore. We solved this problem by assigning a fitness of zero to such solutions.

If we measure the fitness with both scenarios, we avoid a lot of the (wanted or unwanted) anticipated behaviour. After maximum 10 generations we find a perfect solution.

In this paper we gave an overview of how we can create intelligent interfaces which can be used in open distributed systems.

Our approach lets a genetic algorithm learn a classifier system. This classifier system contains classifiers which react upon the context they receive from client and server. The context is defined as a combination of the possible client-side and server-side states.

The case studied was concurrency because this is known to be a major problem in peer to peer computing. It is clear that this approach is not restricted to the domain of concurrency.

As for future work there remains some important problems. First of all we need to do more rigorous experiments. This includes, using larger interfaces (with more functions, or larger petri-nets), using Turing complete classifier-systems and see how they evolve.

A second problem involves the use of the test-scenarios. The test scenarios should cover all the actions which will be invoked upon the server in all possible combinations. How can we write good tests which doesn't leave any open holes for the programmer. And if we can, are the petri-nets still necessary ? In other words: can we learn the model automatically just by looking at the interaction between the agents. The reason we used petri-nets is because they offer immediately a set of possible actions for each state. This reduces the time needed to learn an adaptor because it reduces the search space drastically. Of course these are not necessary, if we know the state we should now enough

A third problem is the representational mapping. In our example we use two alike representations. This makes learning an adaptor easy. To make this algorithm stronger we need a representational mapping which is able to translate one state to another state.

I would like to thank my promotor Theo D'Hondt for the discussions we had on this subject and for giving me the time to investigate this matter. Thanks to Johan Fabry, Tom Tourwe and Tom Mens for proofreading this paper.

http://werner.yellowcouch.org/ werner@yellowcouch.org