6. Conflicting Interfaces

THIS DISSERTATION IS FOCUSED around interface conflicts. Interface conflicts arise at the moment two interfaces offer a similar, but not exactly the same, behavior. In such situations those interfaces will be able to contact each other, but the performed actions will probably induce incorrect behavior. We try to show that the concept of creating an automatic intelligent adaptator is possible. To show this we need a set of conflicts on which we can demonstrate the correct working of our technique. Doing this in a formal way by selecting a statistically significant subset of possible adaptors is impossible, therefore we will design a set of conflicts. To this end, we will create a set of concurrency strategies based on the variabilities presented in the previous chapter. Initially we will investigate conflicts between two non matching interfaces. Afterward we will investigate how multiple concurrency strategies can conflict. For every conflict presented we will investigate, as an exercise to explore the domain, how this conflict can be manually solved.

6.1 The Nature of Interface Conflicts

BEFORE WE DELVE into creation of an intelligent adaptor we need some idea of what such an adaptor might and might not do. We will therefore illustrate that it is not always possible to write an adaptor that will mediate differences between conflicting interfaces. It will also become clear that most adaptors depend largely on the usage involved and that some adaptors can be written between two conflicting interfaces but will fail to work when used in combination with multiple conflicting interfaces.

In the explanation below a one-one conflict refers to a conflict between two components. In our case, one being a server component and the other being a client component. A one-multi conflict refers to a conflict that arises between one server component and multiple client components. A multi-multi conflict refers to a conflict in which multiple servers and multiple clients are involved. We will start with a typical one-one conflict. A client component is a component that requires a the availability of a concurrency strategy. A server component is a component that provides a concurrency strategy.

Figure 6.1: A simple conflict between a client that expects a counting semaphore on server side and a server that only offer a binary semaphore.

6.1.1 Interface Usage is of Vital Importance

We will now explain that the way interfaces are used largely determines how an adaptor should be written.

A first trivial one-one interface conflict arises whenever a client expects a counting semaphore from the server, but where the server only offers a binary semaphore. In such a case there an interface conflict can arise. Consider the usage scenario depicted in figure 6.1: at the moment the client locks the server a second time, the server will still think it has been locked only once. The next unlock from the client will release the server, while the client still thinks it has a lock. Adapting such an interface conflict can be easily done. The code for such an adaptor is pictured in algorithm 17: basically what is done is that the adaptor keeps a counter with which it determines in what state the client is supposed to be and in what state the server is supposed to be. When necessary the adaptor will contact the server to change its state to the clients expected state. Basically this means: the adaptor will only forward a lock request when the server is still unlocked and the client wants a lock. Also the adaptor will only forward an unlock request when the client has released its last lock.

At the moment this adaptor is only used between a waiting client and a waiting server there will be no problems. Problems arise when the client works asynchronously. In such a situation the client would send out a number of lock requests at the same time, each of which will be forwarded to the server. Which brings the adaptor in an uncertain state: a number of the lock requests will return LockFalse while others will return LockTrue. To solve this problem we should add a queue that can hold messages until they are ready to be processed. This effectively means that we need to process the first lock request completely before we can pass through other requests. So we set the appropriate requests on hold.

Again, within another usage context, the client interface and server interface may be connected immediately without the need for an adaptor. This happens when the client simply doesn't lock a certain resource more than once. These initial examples illustrate that the way interfaces are used largely determines how an adaptor should be written.

6.1.2 Not All Conflicts can be Mediated

The next example will show that it is not always possible to write an interface adaptor. As an example we go back to the the line actor and moving dot actors. The line actor expects a nested, non-waiting locking strategy from the server, with a granularity at squares. The server on the other hand provides a nested, waiting locking strategy for the whole server. With respect to the one-one conflict between both interfaces, an adaptor can easily be written. A lock of a square is translated to a server lock and released at the moment the adaptors lock count reaches zero.

However, in practice the whole server may be locked forever by the line actor. Such a situation can arise at the moment the line's trail is kept locked over a single movement. The following sequence illustrates how this can happen:

1. line has locked the positions (5,5..15) and the trail (4,6).
2. line locks position (6,5..15) and the trail (5,7). The position (5..6,5..15) and (4,6) are locked. Position (5,7) is locked twice.
3. the line releases its original position and its original trail. Now the positions (6,5..15) and (5,7) are locked.

In the above scenario the line actor will always have a lock somewhere on the whiteboard and will never release all its locks. If we are locking squares this doesn't matter; in this case however, the whole server will be locked. This shows that certain interfaces cannot be adapted to each other. Whether we can only mediate trivial differences or whether we can also mediate more difficult interfaces is an important question.

6.1.3 Adaptors Need to Cooperate

The third example illustrates how concurrency interface conflicts can be solved between two interfaces (one-one conflicts) but afterward fail to work in the global picture (one-multi and multi-multi conflicts), unless other interfaces are also adapted using a similar technique.

Consider therefore the case where the server supplies a locking granularity at squares, and a client that requires a locking at whiteboard level (this is the enter/leave locking strategy). Adapting the client to work with the server may seem easy: it suffices to lock all the squares on the whiteboard. The problem with this is that locking all fields is a relatively large task, especially when other actors are also on the whiteboard. We cannot expect to lock all squares without any other square being locked by somebody else. What we do in such a situation can differ, but in both cases it will provide a sub optimal solution:

• Try and release again: If a lock cannot be acquired release all locks we already have and try again at a later time. By doing so, the client will almost never have a lock on the whole server when other actors are working on the server as well.
• Be persistent and once locked never release: If a lock cannot be acquired we wait until the lock is released again. It is clear that this can lead to a deadlock.

So in any case, this simple solution: lock all squares, does not work. Luckily this can be remedied by adapting all connections to the server. If all connections are adapted to obtain a field lock instead of a square lock, we can easily make this situation to work. (provided that there are no line actors that wants to lock the whiteboard whole the time of course)

6.1.4 Brief Summary

In this section we described some of the intrinsic properties of interface adaptors:

• Adapting interfaces to each other depends largely on how the interface is used.
• We cannot always adapt any interface to any other interface: some at first sight simple adaptors will not work in practice.
• When adapting two interfaces, indirectly linked other actors may need to be adapted also.

We will initially not investigate the latter since creating two interfaces that go along with each other is already quite a difficult thing to do. In chapter 10 we will investigate how multiple different adaptors can be made to work together.

6.2 A Selection of Interface Conflicts

AN INTERFACE CONFLICT is a conflict between two (or more) interfaces. This means that the space of interface conflicts is a space with two axes for one-one conflicts and more axes for one-multi and multi-multi conflicts. Every axis in conflict space represents all possible interfaces (which are either provided or required). We have illustrated in section 5.11 that every interface can be represented by a number of (not necessarily orthogonal) variabilities. This means that conflict space is at least 12 dimensional: 6 dimensions per interface, and at least 2 interfaces for every conflict. For one-multi and multi-multi this is even larger.

If we want to show that our approach to intelligent adaptors is valid and can provide a help within the domain of interface conflicts we should select a number of representative interface conflicts. The problem with this is that 'representative' is not well defined.

6.2.1 Selecting a Set of Interface Conflicts

In practice human programmers will have the tendency to implement a certain functionality according to existing functionalities or according to what they need. In fact there will be a lot of interface conflicts but not as many as covered by the entire conflict space. For example, a programmer will almost never implement a two layered concurrency strategy where the second layer has a granularity lower than the first layer. It is important to realize that adaptor generation algorithms are useful if they cover a lot of conflicts that will occur in real life. When an adaptor generation algorithm is unable to generate an adaptor for a conflict that almost never occurs, it still remains a useful algorithm.

The problem with selecting a set of real interface conflicts is that the behavior of programmers changes over time and that we don't have any information about current often recurring interface conflicts. So, we cannot select a number of existing often recurring interface conflicts.

6.2.2 Designing a Representative Subset of Conflicts

To design a representative set of conflicts we will fall back to the orthogonalities we have identified earlier. The 6 different orthogonalities (which are by no means exhaustive) allows us to investigate how we can mediate slight difference, that is differences on only one orthogonality, and create more complex conflicts by altering multiple variabilities simultaneously. Therefore, we will create a conflict-set which

• contains conflicts within the given domain of concurrency only.
• contains basic conflicts, that is conflicts on only one variability. We need these because we want to know how small conflict changes compare to solving the conflicts. Hopefully this will give some indication to the structure of the problem space because a number of variabilities are orthogonal.
• contains combined conflicts, that is interface conflicts that conflict on more than one variability. This is an important issue, because we don't know anything about the conflict space, therefore we certainly need to randomly select a number of conflicts. How these are selected will be explained later.
• contains conflicts that can be solved by humans as well as conflicts that cannot be solved, not even by humans. We will actively search for conflicts that cannot be solved, because this also gives some indication on the structure of the problem.

Afterward this conflict set will be expanded with other conflicts ...

• that can be solved in one-one and can be readily extrapolated to one-multi and multi-multi situations.
• that can be solved in one-one but cannot be solved, or are substantially much more difficult to solve, in one-multi or multi-multi situations.
• that cannot be solved in one-one but can be solved within one-multi and multi-multi situations by means of cooperation.
• that cannot be solved in one-one and cannot be solved in one-multi or multi-multi situations.

Depending on the observations with these conflict sets we can create a new conflict set that will provide us with more information, when necessary. The remainder of this chapter will focus on generating the set of 'designed' conflicts, such as conflicts on one variability, or conflicts that meet certain other requirements. The set of randomly selected interfaces will be presented in chapter 3.

6.3 One-One Conflicts on One Variability

AS DESCRIBED IN SECTION 5.11, there are 6 variabilities that we identified for concurrency strategy interfaces. We will now try to obtain possible as well as impossible to solve conflicts on every variability. An impossible conflict is a conflict that cannot be mediated by any possible adaptor. An example of this can be found in section 6.1.2. The conflicts that are not impossible to solve are possible to solve.

6.3.1 Syntax

Table 6.1: One-one simple syntax conflict

Server	Client	Variability
Squares	Squares	Granularity
in Lock(<X, Y>)	out Lock(<Y, X>)
out LockFalse() / LockTrue()	in LockResult(<Res>)	Syntax
Non-waiting	Non-waiting	Control Flow
Non Nested	Non Nested	Reentrancy
Immediately	Immediately	Transition

Syntax conflicts can easily be found. We will use a syntax conflict between a non-waiting, non-nesting client and server as illustrated in table 6.1. The server requires the client to define a position on the whiteboard in $(x,y)$ order, while the client thinks the server works in $(y,x)$ order. The server returns LockFalse when the lock could not be obtained; LockTrue when the lock could be obtained, from the server. As a result the client expects a LockResult(<Boolean|Res>), where res contains either true or false. This interface conflict can easily be remedied. For every incoming or outgoing position pair the adaptor needs simply to swap the two coordinates. When an incoming LockFalse or LockTrue comes back a new message LockResult should be sent out.

Table 6.2: Encoding conflict

Server	Client	Variability
Squares	Squares	Granularity
in Do(<Action:0>, <Pos: X + Y * 100>)	out Lock(<X, Y>)
in Do(<Action:1>, <Pos: X + Y * 100>)	out UnLock(<X, Y>)
out Do(<Action:2>)	in LockFalse()
out Do(<Action:3>)	in LockTrue()/UnlockDone()
out Do(<Action:4>)	in UnlockFailed()	Syntax
Non-waiting	Non-waiting	Control Flow
Non Nested	Non Nested	Reentrancy
Immediately	Immediately	Transition

The conflict presented in table 6.2 is a bit more difficult. The server uses some kind of calling channel over which messages should be encoded. For example, a lock request should be encoded to the call Do(0, $x+y*100$), an unlock request should be encoded to the call Do(1,$x+y*100$). Messages from the server to the client are also encoded through the same calling channel, with the difference that some different returns are mapped to the same return value. In this case: Do(3) is send out to notify success. In case of failure the server will send out an appropriate action. Mapping these two onto each other is difficult because we need the ability to encode the outgoing $x$ and $y$ coordinates to one position, this requires some mathematical functions. A second difficult thing for an adaptor is distinguishing a SuccesLock from a SuccessUnlock message. This requires some knowledge about the context, more specifically what the previous message was.

6.3.2 Reentrancy

A reentrancy conflict is a conflict that occurs due to the fact that somebody is requesting something from the server, while the server is already doing such an action. Recursion (with some form of stack management) is a typical case of reentrancy; shared global states often do not offer reentrant behavior.

Table 6.3: Simple reentrancy conflict

Server	Client	Variability
Field	Field	Granularity
Waiting	Waiting	Control Flow
Non Nested	Nested	Reentrancy
Immediately	Immediately	Transition

The first reentrancy conflict presented in table 6.3 is the example we explained in the beginning of this chapter (see figure 6.1). A conflict arises at the moment the client expects the server to be a counting server, while in practice the server is a simple non counting semaphore. At the moment a client locks the server twice and then unlocks the server, the server will be unlocked while the client still thinks it has a lock upon the server. This is a conflict that often can be solved quit easily by means of keeping a counter within the adaptor.

Table 6.4: Asynchronous reentrancy conflict

Server	Client	Variability
Field	Field	Granularity
Non-waiting	Non-waiting	Control Flow
Non Nested	Nested	Reentrancy
Immediately	Immediately	Transition

The second reentrancy (table 6.4) conflict is a bit harder to solve. Like the previous conflict, the server only supports a binary semaphore, while the client expects a counting semaphore. The big difference now is that the client actively sends out a lot of lock requests and afterward gathers the answers. So the client works asynchronously. As discussed in the beginning of this chapter writing an adaptor between both concurrency strategies is possible, but is a bit more difficult since we need the ability to set incoming messages on hold, until the server answers.

6.3.3 Control Flow

Control flow conflicts are conflicts that arise from the fact that some messages will wait before returning while others don't wait.

Table 6.5: Simple control flow conflict

Server	Client	Variability
Squares	Squares	Granularity
Waiting	Non-waiting	Control Flow
Non Nested	Non Nested	Reentrancy
Immediately	Immediately	Transition

The first control flow conflict (table 6.5) concerns a server offering a waiting locking strategy while the client expects a non-waiting locking strategy. If the client doesn't behave too unconventional, this will work since the client will always get a LockTrue back from the server. It is in fact not a real conflict because the interaction between both will work out well, even without an adaptor.^6.1

Table 6.6: Control flow conflict when idling

Server	Client	Variability
Squares	Squares	Granularity
	Non-waiting
Waiting	Expects to do things while idling	Control Flow
Non Nested	Non Nested	Reentrancy
Immediately	Immediately	Transition

Table 6.6 illustrates what can go wrong between a waiting server and a non-waiting client. It has to be said that the example is a bit far fetched but can actually occur in practice. The unconventional thing this client does, is relying on the request-lock to return false sometimes. It relies on this to advance with some other important virtual thread. If the server never returns such a LockFalse the second virtual thread will cease to work. This is in fact a scheduling conflict due to the control flow between the two components.

Table 6.7: Control flow conflict that is almost impossible to solve

Server	Client	Variability
Squares	Squares	Granularity
Non-waiting	Waiting	Control Flow
Non Nested	Non Nested	Reentrancy
Immediately	Immediately	Transition

Another interesting conflict, presented in table 6.7, is where the server offers non-waiting locking semantics and the client expects waiting locking semantics. The only thing an adaptor can do in this situation is start polling the server until the server returns LockTrue. Since this generates lots of network traffic this is clearly not a good solution. It brings down the network and the adaptor possible gets locked out when at too large a distance from the server. Probably there is no good general solution to this problem. Luckily solutions can be found within certain environments. Suppose we are working on a local network where packets are queued in a fair way, the server may be able to do exactly what is required without any explicit provisions for it.

6.3.4 Granularity

Granularity conflicts arise at the moment the size of resources differs. Sometimes a resource encompasses a whole server, while in other cases a resource description refers to a number of underlying data structures, while again in other cases a resource is directly mapped onto the underlying data structures. For our whiteboard example this means that a resource can be either a single square, a line or the whole whiteboardf.

Table 6.8: A simple granularity conflict

Server	Client	Variability
Lines	Squares	Granularity
Non-waiting	Non-waiting	Control Flow
Nested	Nested	Reentrancy
Immediately	Immediately	Transition

The granularity conflict presented in table 6.8 concerns a server that offers a locking granularity at the level of lines (vertical ones). The client requires a locking granularity at the level of squares. Since the granularity that the client requires is smaller than the granularity offered by the server it is not too hard to interface the client with the server. Instead of locking a certain $(x,y)$ position, the client can lock a certain line $x$. The client is sure that the position to lock is certainly locked.

Table 6.9: A more difficult granularity conflict

Server	Client	Variability
Lines	Squares	Granularity
Non-waiting	Non-waiting	Control Flow
Non Nested	Non Nested	Reentrancy
Immediately	Immediately	Transition

The granularity conflict presented in table 6.9 is of a more difficult sort to solve. Here the server offers a non nested locking strategy for lines, while the client requires a non locking strategy for squares. This is the same as the previous granularity conflict, the only difference between both lies in the reentrancy. The fact that the server is non nested complicates a possible adaptor a lot. To illustrate this, think about locking two points at the same vertical line. In such a case, the first lock request will be translated to a lock on the given line, while the second request will be translated also to a lock on the same line. Since both are the same line on the server. Unlocking the first point will also unlock the second point immediately. To solve this the adaptor should keep track of positions it thinks are locked and map this on the server. The adaptor needs some form of memory.

Table 6.10: An impossible to solve granularity conflict

Server	Client	Variability
Squares	Field	Granularity
Non-waiting	Non-waiting	Control Flow
Non Nested	Non Nested	Reentrancy
Immediately	Immediately	Transition

The conflict presented in table 6.10 is impossible to solve. The server offers a granularity at the level of squares, while the client expects a granularity at the level of the full whiteboard. Although a solution might seem easy, it won't work properly. One might think to write an adaptor that simple starts locking all squares within the whiteboard. Only when all squares are locked is the field considered locked and a LockTrue is sent to the client. The problem with this solution is that there will be other actors on the whiteboard (otherwise we wouldn't need to lock), so locking all resources can be a difficult operation.

Surprising about this example is that an adaptor can be generated between two components, while in practice when multiple components are running the adaptor will simply not work. The only good solution to this problem is either to add an extra layer or to agree between a number of components to lock everything in a certain order.

6.3.5 Layering

When guarding access to different components, concurrency problems often occur within the concurrency layer itself. To solve these kind of problems, extra layers can be added until we have reached a suitable solution. In this section we will only cover one extra layer, because other extra layers require other topologies, which do not fit within the one-one scenarios. We will discuss these in section 6.4.

When multiple layers are present, the conflict tables will contain a description of granularity, control flow, reentrancy and transition for each layer. The server in table 6.11, contains two layers. The first layer works at a granularity of squares, while the second layer (the red fields in the server column) works at the whole whiteboard. When presenting two (conflicting) interfaces we will put layers with the same granularity at the same level.

Table 6.11: Simple layering conflict

Server	Client	Variability
Squares	Squares	Granularity
Waiting	Waiting	Control Flow
Nested	Nested	Reentrancy
Immediately	Immediately	Transition
Field		Granularity
Waiting		Control Flow
Nested		Reentrancy
Immediately		Transition

The first conflict (table 6.11) occurs when the server request from the client to announce a series of locking operations and afterward finish the lock request operation. A series of square locking operations is announced by a single lock upon the whole server/whiteboard. Finishing the square locking operations is done by unlocking the server/whiteboard. In this conflict, the client in this case simply doesn't know that such a thing should be done. This conflict can easily be solved simply by wrapping every lock request within the required start and stop operations.

Table 6.12: Difficult layering conflict

Server	Client	Variability
Squares	Squares	Granularity
Waiting	Waiting	Control Flow
Nested	Nested	Reentrancy
Immediately	Immediately	Transition
	Field	Granularity
	Waiting	Control Flow
	Nested	Reentrancy
	Immediately	Transition

Table 6.12 covers a layering conflict where the server offers a single layer to lock resources. The client on the other hand expects from the server to offer some kind of server lock to start and stop requesting locks. This conflict cannot be easily solved by ignoring the start and stop operations. If we do so, we might end up with a set of deadlocks. The reason why one may need such an extra layer is to avoid deadlocks on the server. This implies that an adaptor should be able to detect deadlocks in some way and resolve them. Detecting them can be done with some form of timeout. Solving them will be a bit more difficult, therefore we will need to release all the locks we already requested, including the one pending at the moment. In this way, other waiting parties will be able to obtain their locks.

6.3.6 Transition

Transition refers to how locks influence resources. If changes made to a resource are in effect immediately, there is not much to say about transition: we say that the transition is immediate, because there is no time difference between changing a state and being in that state. On the other hand if changing a resource only results in actual changes when the lock is committed or rolled back there is a time difference. So in this case the transition is a commit/rollback transition.

Table 6.13: Simple transition conflict

Server	Client	Variability
Squares	Squares	Granularity
Non-waiting	Non-waiting	Control Flow
Non Nested	Non Nested	Reentrancy
Immediately	Abort/Commit	Transition

The first illustration of such a transition conflict is illustrated in table 6.13. Here the server has no special transition provisions. It simply does immediately what is asked. The client on the other hand wants the ability to lock resources and then choose to abort or commit the lock. In both cases the lock is released. The resource state becomes either what is requested (a commit) or what the state of the resource was before the lock (an abort). Adapting these two different interfaces is no problem. This can be done by an adaptor that obtains the state of the resource immediately after locking.

Table 6.14: Nested transition conflict

Server	Client	Variability
Squares	Squares	Granularity
Non-waiting	Non-waiting	Control Flow
Nested	Nested	Reentrancy
Immediately	Abort/Commit	Transition

In the conflict represented by table 6.14, we have a nested locking strategy in combination with a commit/abort transition. This means that for every new lock on the same resource we can undo the changes. Suppose we lock a resource, with value $A$, and change that value to $B$; and afterward we lock that resource again and change that value to $C$, then this resource will be brought back to value $B$ after the first abort and back to value $A$ after the second abort. The conflict between two interfaces will pop up at the moment the client aborts a lock, while the serve is unable to undo the changes already made. This will leave the server in an unanticipated, possibly wrong, state. In essence mediating this interface conflict is similar to conflict 6.13, with the big difference now that the adaptor needs to have a stacked memory for every square on the board.

Table 6.15: Typical transaction transition conflict

Server	Client	Variability
Squares	Squares	Granularity
Non-waiting	Non-waiting	Control Flow
Nested	Nested	Reentrancy
Immidiatelly	Immediately	Transition
Field	Field	Granularity
Waiting	Waiting	Control Flow
Non Nested	Non Nested	Reentrancy
Commit/Abort	Immediately	Transition

Scenario 6.15 covers a conflict where the server provides and the client expects two layers. The lowest layer, the level of resources, is a simple lock/unlock interface where it always seems as if the changes are in effect immediate. The layer above this resource-lock layer is the transaction layer where we can start a transaction, which we can either abort or commit. Committing means that all changes made to locked fields will be realized. Abort means that a rollback of all changes will be done.

The ``conflict'' here exists in the fact that the server offers a transaction interface, but the client simply doesn't want to use it. Adapting these is very easy: when the client requests an unlock operation the server is simply requested to commit the lock. The other way around on the other hand might be more difficult.

Table 6.16: Another typical transaction trasnition conflict

Server	Client	Variability
Squares	Squares	Granularity
Non-waiting	Non-waiting	Control Flow
Nested	Nested	Reentrancy
Immidiatelly	Immidiatelly	Transition
Field	Field	Granularity
Waiting	Waiting	Control Flow
Non Nested	Non Nested	Reentrancy
Immediatelly	Commit/Abort	Transition

In the conflict presented in table 6.16, the server offers solely a server lock that can be requested, but all changes are immediately effective. The client on the other hands want the possibility to roll back and commit. This seems to be a very difficult problem to solve because the adaptor needs to extract some knowledge from the server (what is the state of a resource) and needs to hold back changes to this state until a commit happens. Fortunately it isn't. The same technique as used with conflict 6.13 is appropriate here, as is a memory of all the locks obtained yet and released already.

6.4 One-Multi Conflicts

UNTIL NOW WE HAVE STAYED CLOSE to conflicts between two partners: a server that provides a certain concurrency interface and a client that expects a certain concurrency interface. In practice, there will be a server with a number of clients.

Figure 6.2: Non cooperating adaptors on all connections.

The problem we are now faced with is that every client connected to the same server might expect the server to offer another concurrency strategy. One might think that simply placing adaptors at all client-server connections would solve the problem (see figure 6.2). It is interesting to see that this is not necessarily the case. To illustrate this we have selected a number of interesting conflicts, for which a solution requires the cooperation between the different communication partners.

Figure 6.3: A set of adaptors on all connections that cooperate with each other.

To implement such a cooperating set of adaptors we resort to a more systematic view. The perfect solution would be as illustrated in figure 6.3, where all connections have an adaptor-drone whom behaviors are coordinated by one central adaptor-coordinator. The problem with this solution is that we not only need to create one adaptor, but a set of adaptor-filters, that all communicate with each other to cooperate and coordinate their global behavior. This requirement makes a solution substantially more difficult to implement. Therefore we will only generate a global adaptor that monitors all connections and coordinates the global behavior. This global adaptor will exhibit exactly the same behavior as is required from separate communicating adaptors. In practice one might be able to split up this one adaptor into smaller pieces and migrate those to better locations.

6.4.1 The Empty Server 1-x Conflict

Table 6.17: The empty server one-multi conflict.

Server	Client1	Client2	Variability
	Squares	Squares	Granularity
	Waiting	Waiting	Control Flow
	Nested	Nested	Reentrancy
	Immediately	Immediately	Transition

Imagine a server that does not offer any concurrency strategy, the most simple kind of server. The client on the other hand expects a certain locking strategy (see table 6.17). Interfacing these two conflicting concurrency strategies is easy in a one-one situation. The adaptor needs only to simulate all incoming synchronization calls in such a way that the client will continue working. E.g.: always return LockTrue. If we would place this dummy-adaptor at all the connections going from different clients to the same whiteboard, we will end up with concurrency problems because there is simply no overall concurrency strategy. To solve this problem all different clients will need to develop a certain concurrency strategy and adhere to that specification.

6.4.2 An Up-scale 1-x Granularity Conflict

Table 6.18: A granularity one-multi conflict.

Server	Client1	Client2	Variability
Field	Squares	Squares	Granularity
Waiting	Waiting	Waiting	Control Flow
Nested	Nested	Nested	Reentrancy
Immediately	Immediately	Immediately	Transition

A second illustration of these not-necessarily working generalized one-one adaptors can be found when the server offers a locking strategy with respect to the whole whiteboard and the client requires a locking strategy at the level of squares (see table 6.18). In this case an adaptor will simply translate every square-lock to a field-lock. The problem that can occur now is that in certain situations a client will always have a lock somewhere on the whiteboard. In this case, the adaptor will keep the whole server locked and no other client can do anything with the whiteboard. This is an illustration of a conflict that is hard to solve between different adaptors. It either requires substantial changes to the behavior of one client, or we need to override the full server locking semantics with a simulated more granular concurrency strategy.

6.4.3 A Down-scale 1-x Granularity Conflict

Table 6.19: A granularity one-multi conflict.

Server	Client1	Client2	Variability
Squares	Field	Field	Granularity
Waiting	Waiting	Waiting	Control Flow
Nested	Nested	Nested	Reentrancy
Immediately	Immediately	Immediately	Transition

A third problematic conflict occurs when the client wants to lock the whole whiteboard, but the server only supports locking of squares (see table 6.19). In such a situation, an adaptor will try to lock all the squares on the board, which will take a lot of messages but after all will work in a one-one situation. In a one-multi situation, this adaptor behavior could result in a livelock because two similar adaptors might want to lock the whole server in a non ordered way.

Solving this conflict requires the cooperation between the different adaptors. When a server lock should be obtained all adaptors could agree to lock only one reserved position on the board, which means that the whole server is locked. In this case all adaptors also agree to follow this convention. Another possibility would be agree to a certain order when starting to lock the whole whiteboard.

6.4.4 A Non Waiting Server 1-x Conflict

Table 6.20: A non-waiting server one-multi conflict.

Server	Client1	Client2	Variability
Squares	Squares	Squares	Granularity
Non-waiting	Waiting	Waiting	Control Flow
Nested	Nested	Nested	Reentrancy
Immediately	Immediately	Immediately	Transition

A fourth problematic conflict arises when a client expects a waiting locking strategy, but the server offers only a non-waiting locking strategy (see table 6.20). This requires the adaptor to actively poll the server constantly until the required lock is obtained. In a one-one situation this adaptor will always immediately get a lock, in a one-multi situation on the other hand this will result in a lot of unwanted network traffic and a non-fair scheduling behavior.

Therefore not only the interface conflicts between the client and the server should be solved, but also differences between the implicit interaction between the different clients.

6.5 Multi-Multi Conflicts

WITH MULTI-MULTI CONFLICTS we mainly aim at the situation where a number of components need a number of other components to reach a certain specific global behavior. We will again use the whiteboard example to illustrate this.

Suppose we have two board components and six actor components: a yellow moving dot, an orange moving dot, a red moving dot, a green moving line, a blue floodfill actor and a turquoise floodfill actor. The red moving dot together with the blue floodfill actor only move on the first board. The orange moving dot and turquoise floodfill actor work on the second board only. The last two actors: the yellow moving dot and the green moving line both work on both boards. (See figure 6.4).

Figure 6.4: Peer 2 peer concurrency problem

The actors that only work on one board follow the logic explained earlier. The actors that work on both boards move by checking whether the next target position is free on both boards. Only when this is the case can the actor continue with its movement. The locking logic to implement this is done very simply by locking the first board and afterward locking the second board. It is clear that in this situation deadlocks can arise. Let's assume that the yellow dot actor first needs to obtain a lock on the first board and afterward on the second board, while the moving line actor first tries to obtain a lock on the second board. In such a situation a deadlock can arise.

This is a problematic situation because:

• None of both servers can solve this problem, because none has the necessary knowledge. No server knows what an actor does with other servers.
• None of the actors on both boards can solve this problem because they do not know each other and certainly not in which order they should obtain the locks.

Table 6.21: A multi multi conflict that requires the development of a distributed transaction adaptor.

1st	Red	Yellow	Green	Blue	2nd
Server	Client	Client	Client	Client	Server	Variability
Squares	Squares	Squares	Squares	Squares	Squares	Granularity
Non-Wait	Non-Wait	Non-Wait	Non-Wait	Non-Wait	Non-Wait	Control Flow
Nested	Nested	Nested	Nested	Nested	Nested	Reentrancy
Imm.	Imm.	Imm.	Imm.	Imm.	Imm.	Transition
Field	Field	Field	Field	Field	Field	Granularity
Waiting	Waiting	Waiting	Waiting	Waiting	Waiting	Control Flow
No-Nest	No-Nest	No-Nest	No-Nest	No-Nest	No-Nest	Reentrancy
Imm.	Imm.	Imm.	Imm.	Imm.	Imm.	Transition

The conflict presented in table 6.21 illustrates this. Here all actors adhere to exactly the same interface, nevertheless there will occur deadlocks if we create such a situation. The reason has already been explained above. The solution requires the development of a distributed transaction server, within the adaptor. By doing so, we introduce a second concurrency layer, which will guard the access to a number of different components. Of course it is perfectly possible that such a layer is already present and that we need to adapt the differences between those layers.

Table 6.22: Another real world multi-multi interface conflict.

1st	Red	Yellow	Green	Blue	2nd
Server	Client	Client	Client	Client	Server	Variability
	Squares	Squares	Squares	Squares	Squares	Granularity
	Non-Wait	Non-Wait	Non-Wait	Non-Wait	Non-Wait	Control Flow
	Non-Nested	Non-Nested	Nested	Nested	Nested	Reentrancy
	Imm.	Imm.	Imm.	Imm.	Imm.	Transition
Field			Field		Field	Granularity
Waiting			Waiting		Waiting	Control Flow
Nested			No-Nest		No-Nest	Reentrancy
Imm.			Imm.		Commit/Rollback	Transition
			Components			Granularity
			Waiting			Control Flow
			No-Nest			Reentrancy
			Imm.			Transition

The conflict presented in table 6.22 is another multi-multi conflict, containing two servers. The first server offers a lock on the whole whiteboard and places clients in wait until it is their turn. All changes made are in effect immediately. The second server offers a commit rollback interface. This is done by offering a transaction interface through which the client can obtain a transaction id: when this is done the client can lock any square it wants. When all changes are made a commit can be issued, otherwise an abort. The clients are implemented in the same 'realistic' fashion. The yellow and red moving dot actors simply require a non-waiting locking strategy without nesting. This is logical since the moving dot actor doesn't need to nest locks, and a possible livelock is easily remedied by choosing a random delay. The green moving line is also realistic in its approach. It needs to access two servers, so it wants a locking manager to be present. When done it requires the possibility to start a transaction on one or more servers, and when this transaction is obtained it can finally move the line. The last actor, the blue floodfill actor, requires a nested locking strategy that doesn't wait. Changes are in effect immediately. We want to use this large multi multi conflict to verify whether the algorithms we will develop will be able to solve this real life problem.

6.6 Summary

IN THIS CHAPTER we have presented the properties of interface conflicts. We have explained that every interface conflict largely depends on the context in which the interfaces are used. We have also explained that not all conflicts can be solved. And finally we have discussed the necessity of cooperating adaptors. We not only need adaptors between two conflicting interfaces, in a lot of cases we need adaptors that regulate and communicate their behavior, otherwise creating a good concurrency strategy may be impossible.

Afterward we presented many one-one interface conflicts, with a description of the feasibility of writing an adaptor. The presentation of one-multi interface conflicts focuses especially on adaptors that cannot simply be generalized from a one-one conflict adaptor. And finally, the multi-multi interface conflict discussion covers even more interface conflict examples.

Table 6.24: Overview of conflicts

Conflict	Variability	Difficulty		Why
		1-1	1-x
6.1	Syntax	Eas	Eas
6.2	Syntax	Med	Eas	Mapping between structural
				different communication channels
6.3	Reentrancy	Eas	Eas
6.4	Reentrancy	Med	Eas	Requires busy-with flag
				and Q management
6.5	Control Flow	Eas	Eas
6.6	Control Flow	Eas	Eas
6.7	Control Flow	Eas	Imp	Unknown scheduling behavior
6.8	Granularity	Eas	Eas
6.9	Granularity	Med	Eas	Needs to develop a memory
6.10	Granularity	Eas	Coop	Solution for 1-1 wont work on 1-x
6.11	Layering	Eas	Eas
6.12	Layering	Med	Coop	Med: Needs to detect timeouts
				Coop: Can be better solved by cooperation
6.13	Transition	Eas	Eas
6.14	Transition	Med	Med	Adaptor needs stack/square
6.15	Transition	Eas	Eas
6.16	Transition	Med	Med	Adaptor needs stack/square and
				memory of acquired locks
6.17	Empty Server		Coop	Needs to implement a suitable locking strategy
6.18	Nasty client		Coop	Needs to neglect whole-time client lock
6.19	Livelock		Coop	Needs to cooperate to offer a server lock
				instead of square locks
6.20	Polling		Coop	Needs to develop token passing
6.21	Distributed		Med	Adaptor needs to develop
	Transactions		Coop	a distributed transaction server
6.22	Distributed		Hard	Needs to develop distributed transactions
	Transactions		Coop	and needs to mediate interface conflicts

In table 6.24 we present an overview of all the conflicts we have discussed. The first column refers to the summary-table of the conflict. The second column specifies which variabilities the conflict explores. The third and fourth column represent the difficulty to develop an adaptor to solve the conflict. The third column represents the difficulty to write an adaptor between 1 client and 1 server. The fourth column shows how difficult it is to get the one-one solution to work in cooperation with other (unknown) actors. Both columns use a number of abbreviations:

• Easy; The adaptor can be written in a trivial way.
• Med: medium; The adaptor can be written but is not trivial.
• Hard: it is hard to develop a correctly working adaptor. The reason why is explained in the last column.
• Coop: In the one-multi column, coop means that an adaptor can be written only if all participating components develop the same strategy and adhere to this strategy.
• Imp: Impossible. It is impossible to write an adaptor in this situation.

The table contains three parts. The first part are the one-one conflicts, the second part are the one-multi conflicts and the last part are the multi-multi conflicts.

In the next chapter we will discuss how we will describe interfaces and which interfaces we will use.

Footnotes

...^6.1

Some confusion can arise here. We assume that a non waiting server always returns either LockTrue or LockFalse. A waiting server will only return when the lock could be obtained, hence return a LockTrue.