7. Our Approach

UNTIL NOW WE HAVE EXPLAINED how Petri-nets can be used to describe the behavior of interfaces, we have described which case we will use and which conflicts we will investigate. We will now explain which solution we propose to solve the problem of conflicting concurrency strategies. In general, we will do this by inserting an adaptor between the different communicating components. This adaptor will mediate the differences between the different interfaces. To do so, the adaptor will make use of three different modules: a liveness module, an enforce-action module and a concurrency module. Every module will be responsible for a certain functionality, which will meet certain requirements.

In this chapter we will first explain which assumptions we make on the components, then we will explain which requirements we place on the adaptor and last we will describe which modules we propose.

7.1 Assumptions about Petri-Nets and Components

BELOW WE INTRODUCE A number of important assumptions that form the basis of our research.

The first assumption we make is that the concurrency behavior of all involved components is documented by means of a Petri-net description. These Petri-net descriptions follow the guidelines presented in section 3.8 and are used by the adaptor to keep track of the underlying component behavior. For every component involved, a marking resides within the adaptor. Whenever a message $m$ comes in from a component, the associated Petri-net will execute the transition corresponding to $m$. As such, the adaptor always has a correct representation of the state of the underlying components.

A second assumption is that the concurrency adaptor, which is placed between conflicting components, needs to work at runtime. Working at runtime means that the adaptor will choose certain synchronization actions to modify the behavior of the synchronization overall. However, before the adaptor can verify whether this overall synchronization behavior is correct, the adaptor should be able to obtain some kind of feedback. However, because the adaptor itself has no explicit supervisor, it needs some point of reference that can be used to verify its own behavior. Such a point of reference should allow the adaptor to verify a number of requirements of the mediated concurrency behavior, hence our point of reference should strongly correlate with the concurrency behavior. Therefore we will assume that the core functionalities of the communicating components is compatible, while the concurrency behavior of the different components might be incompatible. In our case we will separate these as follows:

1. All messages that deal with the core functionality of the components are said to be part of the logic interface. E.g.: the Act or SetPosition message.
2. A concurrency strategy is an algorithm that helps synchronize the behavior of some core functionality of the underlying component. We will say that all messages that deal with this behavior are part of the synchronization interface. E.g.: messages such as Lock and Unlock.

Thirdly, we assume that, as good software writing practices dictate, there is a clear separation between different functionalities. This implies that we should be able to say for every concurrency strategy whether it is required or whether it is provided. If a component requires a concurrency strategy we say that the component is a client component, if it provides a concurrency strategy it is said to be a server component. A second implication of a clear separation of functionalities is that we should be able to say for every message present on an interface whether it belongs to the synchronization behavior or to the logic behavior. Therefore we now define the $logic$ and $synchro$ sets formally. When given two Petri-net interface descriptions $N_{0}=(T_{0},P_{0},A_{0},\ldots)$ and $N_{1}=(T_{1},P_{1},A_{1},\ldots)$. We define $logic$ as the set of all in-transitions or out-transitions that involve no synchronization. Because all logic actions are known to be compatible, we can say that $logic\subseteq T_{0} \wedge logic\subseteq T_{1}$. All the other transitions of $N_{0}$ and $N_{1}$ are assumed to be synchronization operations. Hence $synchro_{0}=T_{0}\setminus logic$ and $synchro_{1}=T_{1}\setminus logic$. We also assume that $synchro_{0}\cap synchro_{1}=\Phi$. If this might be the case a renaming operation in one of both transition should be used.

Fourthly, we assume that no concurrency strategy of any of the components within the conflict locks out certain core functionality, because this would make it effectively impossible to mediate the conflict.

7.2 Requirements for the Adaptor

GIVEN THE ABOVE ASSUMPTIONS we will now define the requirements of our concurrency adaptor. The three requirements we present have been introduced after doing preliminary experiments (discussed in chapter 11). Initially we tried to create an adaptor between different components simply requiring that no-conflict should arise. This however, resulted often a) in adaptors that either behaved in such a way that no communication with the server component occurred (by feeding always a lockFalse back to the originator), or b) in adaptors that mediated the conflict in such a way that race conditions were allowed.

Therefore we have introduced three requirements: the no-conflict requirement, the no-races requirement and the liveness requirement. Below we will explain these three requirements in more detail. Together, if satisfied, they lead to an adaptor that will mediate concurrency conflicts in an appropriate way. However, the three requirements we will present are not exhaustive. For instance other requirements with respect to timing, or requirements with respect to dead-locks might need to be added in other domains.

7.2.1 The No-Conflict Requirement

If we assume that the adaptor contains Petri-nets for all participating components and that the marking of every Petri-net represents the current state of the underlying component, then we can intuitively declare a certain situation to be a conflict whenever one logic transition can be executed within one Petri-net but not in the other.

Formally, two interfaces $N_{0}$ and $N_{1}$ are, given two markings $M_{0}$ and $M_{1}$, in conflict when a logic transition exists that is enabled in only one of both interfaces. We will use $\not\approx$ to denote a conflict between two Petri-net markings:

$$(N_{0},M_{0})\not\approx(N_{1},M_{1}) \Leftrightarrow \exi... ...c, \vert M_{0}[t\rangle_{N_{0}}\wedge M_{1}[t\rangle_{N_{1}}$$ (7.1)

When $(N_{0},M_{0})\not\approx(N_{1},M_{1})$ at the moment a $logic$ message arrives then we can be sure that the adaptor is not working correctly. We will define this to be the no-conflict requirement

• No-conflict requirement: No sequence of actions taken by the adaptor should bring the associated Petri-nets into conflict.

The above definition is a 'good-enough' definition but not a 'cover-all' definition. The definition states that the adaptor is not working correctly if the precondition doesn't hold, but it does not ensure that every incorrect working adaptor is detected by the precondition. In practice, this requirement is difficult to check because there should be no possible execution trace leading to a conflict. This means, that if we want to verify this requirement, we must be sure that we have investigated all possible traces. We will come back to this issue later on.

7.2.2 The No-Races Requirement

The no-conflict requirement immediately results from the fact that we want to solve a conflict between interfaces. Nevertheless, it does not guarantee that enabled actions do not interfere with each other. To guarantee this we need to make sure that actions that are in the same critical section (which we will formally explain in section 10.2) are executed atomically. Therefore we need another requirement:

• No-race requirement
  1. An adaptor should avoid race-conditions on actions and data. Critical sections should be entirely executed or not.
  2. An adaptor should allow some degree of interleaving. An adaptor that consecutively executes every connected client until it terminates, cannot be considered a good concurrency strategy.

The no-races requirement, if satisfied, guarantees that no unwanted behavior as a result from race conditions will occur. However, often other requirements such as no-deadlocks or fairness could be also in place. Here we assume that, whenever appropriate the no-races requirement can be extended to include these extra requirements.

The problem with the above requirement is that it is difficult to define a critical section. Neither within the Petri-nets, nor within the components, there is a uniform notion of 'a critical section'. Therefore we define a critical section as a set changes that cannot be interrupted without bringing the corresponding Petri-nets in conflict. In section 10.2 (page ) we will elaborate further on this and explain more intuitively why this is a good definition.

7.2.3 The Liveness Requirement

With the above no-conflict and the no-races requirements, we do not avoid adaptors that do not work. Adaptors that simply avoid any synchronization operation by always feeding a LockFalse back to the requester will match both previous requirements. However, such an adaptor is clearly not doing what is expected. Therefore we introduce the concept of liveness, or how well a component can proceed with its core functionality. The problem with the notion of liveness is that it can be either defined formally using Petri-nets, or informally based on some reward from the underlying component. Below we will present two possible definitions of liveness.

• Formal Liveness Requirement: In any situation should the involved Petri-nets be alive. A Petri-net is alive if every possible transition can always be enabled again in the future.

The first definition defines formally liveness on the Petri-nets involved. If the Petri-net is alive we assume that the underlying component is alive as well. Liveness on a Petri-net is defined as the number of transitions that still have an option to be enabled in the future. If under a marking a transition exists that can no longer be enabled, the Petri-net is not alive. However, this formal definition is very strong because not even all Petri-nets, received from the underlying components, will be alive when they start. For instance, a Petri-net with an Init transition might, after executing this transition, not be alive anymore, because this Init transition will never be enabled. This indicates that the formal definition of liveness might be a bit too strong.

• Liveness Requirement: The adaptor should try to obtain as much rewards as possible, as defined by the underlying component.

The second definition introduces rewards. Here we assume that the underlying component knows exactly what it wants to obtain in the future and indicates this by sending rewards to the adaptor. A component developer could specify this kind of information as checkpoints within the source code or as favorite transitions within the offered Petri-net. In both cases, the liveness requirement specifies that as many as possible positive future branches need to be executed, or in other words need to obtain as much reward as possible from the underlying client component. How the rewards are defined will be discussed in detail in section 9.2 (page ) and will later on be used as the rewards within a reinforcement learning algorithm (section 9). This definition of liveness is similar to the description given in [Lyn96].

7.3 Pure Approaches

THE PROBLEM OF CONCURRENCY STRATEGY conflicts, embodied in our case, the availability of formal interface descriptions and the functional requirements of a solution now allow us to investigate which techniques are suitable to solve the problem. In general two techniques are possible: formal deduction of an adaptor and learning. We will investigate for every requirement the applicability of each technique. A pure application of one of both techniques will be impossible, as we will explain below, therefore in section 7.4 we will explain how we create a hybrid, modularized adaptor.

7.3.1 Automatic Deduction of an Adaptor

Figure 7.1: Formal deduction of an adaptor. Blue lines honor a logic protocol, red lines honor a synchronization protocol.

Given the formal Petri-net description of all involved components and assuming that we have a full formal definition of the requirements we might expect that it is possible to automatically deduce an adaptor, which satisfies all requirements and honors all restrictions. Such a formal technique would, given the Petri-nets as input, find some algorithm $\sigma$ that could be placed in between the different Petri-nets such that all requirements hold. If we assume that $\sigma$ itself is a Petri-net that directly links the two involved Petri-nets together, then we might not be able to verify the liveness requirement because the formal liveness property of Petri-nets is not yet known to be decidable or not (see section 3.10 on page ). From this observation, it becomes clear that it is unlikely to create $\sigma$ automatically.

7.3.2 Applicability of Pure Learning Algorithms

Figure 7.2: A fully learning adaptor. Blue lines honor a logic protocol, red lines honor a synchronization protocol.

In this section we will investigate whether a pure learning-algorithm approach (as pictured in figure 7.2) might be suitable. Learning algorithms are applicable in situations where formal techniques fail to offer solutions. A learning algorithm is typically a search algorithm that uses a number of heuristics (implicitly or explicitly represented) to find solutions. However, learning algorithms still remain probabilistic processes and proving that a probabilistic process will only result in adaptors that satisfy all requirements might be very difficult. Especially if the requirements state $\forall$-behavior (= $\not\exists$-behavior), such as the no-races or no-conflicts requirements.

• The no-races requirement is difficult to guarantee because a race should never occur.
• The no-conflict requirement is also difficult to guarantee because a conflict should never occur.

These two no-requirements are, aside from being difficult to guarantee by a learning algorithm, also difficult to express numerically. However, in contrast to the other requirements, the liveness requirement can be measured numerically and spurious liveness failures are not a disaster.

7.4 Modularizing The Adaptor

Figure 7.3: Cascade of components that avoids conflicts and honors a good working concurrency strategy. Blue lines honor a logic protocol, red lines honor a synchronization protocol. The green line is a separate protocol between the concurrency-adaptor and the learned adaptor.

IN SECTION WE EXPLAINED that a purely formal or a purely learning based approach cannot solve the problem of concurrency adaptors. The main reason why a purely formal approach won't work is because of the liveness-requirement. The main reason why a purely learning approach won't work is because the no-conflict and no-races requirement cannot be guaranteed. Therefore, to solve the problem of creating a concurrency adaptor we will resort to an hybrid approach in which the no-conflict requirement and the no-races requirement are formally deduced, or validated, while the liveness requirement will be ensured by a learning algorithm. We will do this by placing these three requirements into separate modules, which together form the concurrency adaptor. Figure 7.3 illustrates how this could be done.

7.4.1 An Enforce-Action Module

The enforce-action module is placed between the server component and the remaining modules of the adaptor (see figure 7.3). Its main goal is to prepare the server for incoming $logic$ messages. It does this by inserting appropriate synchronization messages in the message stream. For instance, when an setPosition arrives, and the server has not yet been locked, this module will lock it and send through the setPosition message.

This way, the adaptor fulfills the no conflict requirement, because it can always enforce requested $logic$ actions upon the server component. If the client component expects a certain transition to be enabled (for instance setPosition), the adaptor should be able to enable this transition at the server component. Given the Petri-net description of an interface it is not too difficult to deduce formally what should be done to enable a certain action, or to reach a certain state. In chapter 8 we will explain how we do this. The responsibilities of the enforce-action module are:

1. Bypass all concurrency behavior of the server component by inserting synchronization messages whenever appropriate.
2. Present the adaptor-side only a logic interface that has only the core functionality of the server component.

7.4.2 A Liveness Module

A second important part of the concurrency adaptor are the liveness-modules. For every client-component there will be one liveness module. Every module is responsible for learning at runtime how to keep a client component alive, thereby honoring the constraints offered by the Petri-net. How the rewards are defined and assigned at runtime will be described in detail in section 9.2. The working of the entire liveness module is described in chapter 9. The responsibilities of the liveness module are:

1. Pass through any logic actions.
2. React on all synchronization messages by feeding some synchronization message back to the client, such that no synchronization message needs to be passed through to the server component.
3. Keep the client component alive by accumulating as much reward as possible.
4. If multiple actions can be taken in response to an incoming synchronization message, the different possible actions and enough information to recognize critical sections, will be presented to the concurrency module, which will choose an appropriate action.

7.4.3 A Concurrency Module

The concurrency module is placed between the two other modules. However, the problem of a good concurrency strategy is even more prominent than before, because any possible action chosen by the client will always be able to execute at the server (because of the enforce-action module), resulting in data and action races. Solving this problem is the responsibility of the concurrency module.

The concurrency module will be discussed in chapter 10. It receives from the client all the $logic$ actions that should be forwarded to the server, from the liveness modules it receives the necessary information to be able to recognize critical sections. The concurrency module will use this information and make the different connected client components work together in a way that avoids colliding critical sections. The responsibilities of the concurrency module are:

1. Proxy the server component in such a way that nobody else can access the server component.
2. Deduce which resources, actions and critical sections are present.
3. Interleave critical sections to avoid race conditions.
4. Be fair with respect to the liveness of all connected client components.

7.5 Argumentation of a Correct Construction

THE PRESENTED MODULES make our initial requirements much more accessible. Two of the 'no-'-requirements (no-conflicts, no-races) are satisfied by known-to-work solutions and the liveness-requirement is satisfied by means of a learning algorithm. Cascading these three modules as pictured in figure 7.3 will result in a concurrency adaptor. In this section we will argument that this construction results in an adaptor that honors all the previously stated requirements.

7.5.1 Satisfying the No-Conflict Requirement

The no-conflict requirement declares that at no point in time the possibility of an immediate conflict should exist, that is a transition that is enabled in one Petri-net but not in the other. Formulated in terms of messages, that there is no message that can be sent but not received. The enforce-action module guarantees that it will always be able to execute any incoming $logic$ message on the server-component. The two other modules present, the concurrency module and the liveness module, literally pass through any $logic$ message. So any, possible $logic$ request from any client component will always be executed. Hence no message exists that can be posted but not received, thus satisfying the no-conflict requirement.

7.5.2 Satisfying the No-Races Requirement

The concurrency module its main responsibility is recognizing and interleaving critical sections. So, if we know that no component but the concurrency module can contact the server-component, we know that there are no races. To argument this, let us assume the inverse, that the whole setup allows for two colliding critical sections. The only place where this collision could happen is at the concurrency module, because this is the only place where both critical sections will be present at the same time. The liveness modules work separately, hence cannot result in an incorrect interweaving of messages. The action enforcer module comes after the concurrency module and simply does not interleave any message, every incoming $logic$ message is simply passed through. Thus normally all critical sections should already be serialized. Therefore, if two colliding critical sections can occur, the fault will lie in the concurrency module. Thus, if the concurrency module works correctly, then the interconnection of the three modules will also be correct.

7.5.3 Satisfying the Liveness Requirement

The liveness requirement states that all components should stay alive. This will be guaranteed by the interaction of the concurrency module and the liveness module. Every liveness module is responsible for keeping one component alive and because the concurrency module is, among other things, responsible for being fair with respect to liveness, all components will be alive.

7.6 Summary

IN THIS CHAPTER we have stated the assumptions we make. Firstly we assume that the core functionality of the conflicting components is compatible, secondly we assume that all components offer a Petri-net description of their concurrency behavior and that the concurrency behavior does not hide any core functionality. Thirdly we assume that a clear separation of functionalities exists with respect to the role of clients and server interfaces, and with respect to the role of every message involved in an interface. Messages that take part in the core functionality of a component are called logic messages. Messages that take part in the synchronization behavior are called synchronization messages.

After presenting the assumptions made, we have stated the requirements of a concurrency adaptor. These are the no-conflict requirement, the no-races requirement and the liveness requirement. With these requirements in mind we explained that neither a pure formal deductive, nor a pure learning approach will work to find a solution that will satisfy all requirements. Therefore we modularized the adaptor into three modules. The first module is an enforce-action module, which will solve the no-conflict requirement. The second module is a concurrency module, that satisfies the no-races requirement. And the third module is a liveness module that satisfies the liveness requirement. Finally we have argued that, given the assumptions and the responsibilities of the different modules, the interconnection of these three modules will result in an adaptor that satisfies all three requirements. In the following chapters we will describe every module in detail.