<figure><img src="image_1.png" /></figure>

HAL
open science

# A Calculus of Interfaces for Distributed Collaborative Systems: The Guarded Attribute Grammar Approach

Eric Badouel, Rodrigue Aimé Djeumen Djatcha

► To cite this version:

Eric Badouel, Rodrigue Aimé Djeumen Djatcha. A Calculus of Interfaces for Distributed Collaborative Systems: The Guarded Attribute Grammar Approach. Revue Africaine de Recherche en Informatique et Mathématiques Appliquées, 2020, Special issue CARI 2018, Volume 31 - 2019 - CARI 2018, pp.1-16. 10.46298/arima.5540 . hal-02145920v3

HAL Id: hal-02145920

https://inria.hal.science/hal-02145920v3

Submitted on 5 Oct 2020

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Open licence - etalab
A Calculus of Interfaces For Distributed
Collaborative systems:

The Guarded Attribute Grammar Approach

Eric Badouel$^{(a,c)}$ and Rodrigue Aimé Djeumen Djatcha$^{(b,c)}$

(a) Inria Rennes-Bretagne Atlantique, Irisa, University of Rennes I,
Campus Universitaire de Beaulieu, 35042 Rennes Cedex, France

(b) Faculty of Sciences, University of Douala, BP 24157 Douala, Cameroon

(c) LIRIMA — FUCHSIA team lirima.inria.fr/ project.inria.fr/fuchsia/eric.badouel@inria.fr djeumenr@yahoo.fr

This work was partially supported by ANR Headwork.

**ABSTRACT.** We address the problem of component reuse in the context of service-oriented programming and more specifically for the design of user-centric distributed collaborative systems modelled by Guarded Attribute Grammars. Following the contract-based specification of components we develop an approach to an interface theory for the components of a collaborative system in three stages: we define a composition of interfaces that specifies how the component behaves with respect to its environnement, we introduce an implementation order on interfaces and finally a residual operation on interfaces characterizing the systems that, when composed with a given component, can complement it in order to realize a global specification.

**RESUME.** Nous abordons le problème de la réutilisation des composants dans le contexte de la programmation orientée services et plus spécifiquement pour la conception de systèmes collaboratifs distribués centrés sur l'utilisateur modélisés par des grammaires attribuées gardées. En suivant la démarche de la spécification contractuelle des composants, nous développons une approche de la théorie des interfaces pour les composants d'un système collaboratif en trois étapes: on définit une composition d'interfaces qui spécifie comment le composant se comporte par rapport à son environnement, on introduit un ordre d'implémentation sur les interfaces et enfin une opération de résidus sur les interfaces qui caractérise les systèmes qui, lorsqu'ils sont composés avec un composant donné, peuvent le compléter afin de réaliser une spécification du système global.

**KEYWORDS** : Component Based Design, Service Oriented Programming, Interface, Role, Collaborative System, Guarded Attribute Grammars

**MOTS-CLES** : Conception à base de composants, Programmation orientée services, Interface, rôle, systèmes collaboratif, grammaires attribuées gardées
# 1. Introduction

We address the problem of component reuse in the context of service-oriented programming and more specifically for the design of user-centric distributed collaborative systems. The role of a specific user is given by all the services he or she offers to the environment. A role can be encapsulated by a module whose interface specifies the provided services the module exports and the required external services that it imports. Usually the modules in a service-oriented design are organized hierarchically. In contrast, modules in a distributed collaborative systems would often depend on each other (even though cyclic dependencies between services should be avoided). Moreover services that are currently activated can operate as coroutines and a service call can activate new services in a way that may depend on the user's choice of how to provide the service. We thus need a richer notion of interface for roles in a distributed collaborative system. In this paper we consider a very simple extension of the concept of interface obtained by adding a binary relation on the set of services indicating for each of the provided services the list of services that are potentially required to carry it out. This relation gives only potential dependencies because a user can provide a service in various ways and relying on a variety of external services. We motivate our presentation in the context of systems modelled by Guarded Attribute Grammars [4]. Some extensions of the model are also introduced to take into account non-determinism or certain qualitative aspects related to uncertainty or time constraints. These extended models can provide finer descriptions of the behaviour of a module in a Guarded Attribute Grammar specification.

Even if the objectives differ (service-oriented design versus verification) as well as the models used (user-centric collaborative systems versus reactive systems) we are largely inspired by the works that have been carried out on behavioural interfaces of communicating processes. Three main ingredients have been put forward in these studies which will serve as our guideline.

First, an interface is mainly used to formalize a contract-based reasoning for components. The idea is that a component of a reactive system [5] is required to behave correctly only when its environment does. The correctness of composition is stated in terms of a contract given by *assume-guarantee* conditions: the component should guarantee some expected behaviour when plugged into an environment that satisfies some properties. The principle of composition is however made subtle by the fact that each component takes part in the others' environment [1]. Safety and liveness properties, which are not relevant in our case, are crucial issues in this context and largely contribute to the complexity of the resulting formalisms. The underlying models of a component range from process calculi [2] to I/O automata and games [3]. These interface theories have also been extended to take some qualitative aspects into account (time and/or probability).

Second, an interface is viewed as an abstraction of a component, a so-called *behavioural type*. Thus we must be able to state when a component satisfies an interface, viewed as an abstract specification of its behaviour. A relation of refinement, given by a pre-order $I_1 \le I_2$, indicates that any component that satisfies $I_2$ also satisfies $I_1$. In the context of service-oriented programming we would say that interface $I_2$ implements interface $I_1$.

Third, a notion of *residual specification* has also proved to be useful. The problem was first stated in [6] as a form of equation solving on specifications. Namely, given a specification *G* of the desired overall system and a specification *C* of a given component we seek for a specification *X* for those systems that when composed with the component
satisfies the global property. It takes the form of an equation $C \bowtie X \approx G$ where $\bowtie$ stands for the composition of specifications and $\approx$ is some equivalence relation. If $\approx$ is the equivalence induced by the refinement relation the above problem can better be formulated as a Galois connection [9] $G/C \leq X \iff G \leq C \bowtie X$ stating that the residual specification $G/C$ is the smallest (i.e. less specific or more general) specification that when composed with the local specification is a refinement of the global specification. Since $C \bowtie -$ is monotonous (due to Galois connection) it actually entails that a component is an implementation of the residual specification if and only if it provides an implementation of the global specification when composed with an implementation of the local specification.

## 2. Roles in Collaborative Systems

A collaborative system, as any complex system, combines various viewpoints including its organization and structure, its processes, and its interactions both internally and externally (behaviors). Therefore, the proper functioning of such a system requires an explicit framework for collaboration that clearly specify what the system expects from users, but also what a user can get from the system. It should also prevent users from being overwhelmed by information (or tasks) that are not directly useful. These information can be gathered to explicit the role of an agent in a collaborative system. In many respects the specification of roles can be viewed as a particular aspect of the system. And indeed a role-based approach can be reduced to techniques of separation of concerns [12, 21] in the context of business process design. Nonetheless role can be implemented in different manners. For instance starting from an analysis of system processes one can specify respectively its basic activities (the processes steps) and the control flow that includes the coordination of activities. It is this approach that one finds in business process orchestration [17, 20] or in UML(Unified Modeling Language) collaboration and activities diagrams. In these contexts a role is a named specific behavior of an entity in a particular context [18]. But from an interaction viewpoint, a role can also be a semantic construct forming the basis of a policy, as the access control policy in RBAC (Role Based Access Control) [13, 19]. Finally in an organizational viewpoint a role would be used to select suitable skills to perform a given task.

In this work we favor a more transversal notion of role, in the sense that it integrates the different viewpoints of a collaborative system. This approach is thus similar to the concept of role agent model [14, 15, 16], an extension of agent system where users resolve tasks by making decisions on the basis of their knowledge of the overall system. Then a role is viewed as a set of capabilities together with an expected behavior. It is treated as an independent concept of the considered collaborative system. The main difference between this approach and ours is that in the agent approach, work organization is purely hierarchical and statically defined, while our approach, based on GAGs, offers a more flexible organization as it is required e.g. in plateforms for crowdsourcing or coworking.

## 3. Collaborative System Modelled by a Guarded Attribute Grammar

Guarded Attribute Grammars (GAG) [4] is a user-centric model of collaborative work that puts emphasis on task decomposition and the notion of user's workspace. We assume
that a workspace contains, for each service offered by the user, a repository that contains one artifact for each occurrence of a service call (that initiates a so-called *case* in the system). An artifact is a tree that records all the information related to the treatment of the case. It contains open nodes corresponding to pending tasks that require user's attention. In this manner, the user has a global view of the activities in which he or she is involved, including all relevant information needed for the treatment of the pending tasks.

Each *role* (played by some users) is associated with a grammar that describes the dynamic evolution of a case. A production of the grammar is given by a left-hand side, indicating a non-terminal to expand, and a right-hand side, describing how to expand this non-terminal. We interpret a production as a way to decompose a task, the symbol on the left-hand side, into sub-tasks associated with the symbols on the right-hand side. The initial tasks are symbols that appear in some left-hand side (they are *defined*) but do not appear on right-hand side of rules (they are not *used*). They correspond to the *services* that are *provided* by the role. Conversely a symbol that is used but not defined (i.e it appears on some right-hand side but on no left-hand side) is interpreted as a call to an external service. It should appear as a service provided by another role. Symbols that are both used and defined are internal tasks and their names are bound to the role.

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /><figcaption>**Figure 1.** A grammar for a role that provides a service *A* and uses the external services *C* and *D*. *B* is an internal task, bound to the role, and whose name can henceforth be changed.</figcaption></figure>

In order to solve a task *A*, that appears as a pending task in his workspace, the user may choose to apply production $p_1$ (which corresponds to a certain action or activity) and this decision ends the performance of task *A* (since the right-hand side is empty). Alternatively production $p_2$ may be chosen. In that case, two new (residual) tasks of respective sort *B* and *C* are created and *A* will terminate as soon as *B* and *C* have terminated.

The GAG model also attach (inherited and synthesized) information to a task as well as a guard (condition bearing on the inherited information) that specifies when the production is enabled. In this paper we restrict our attention to the dynamic evolution of tasks (the grammar) and forget about extra information and guards.

**Definition 3.1.** A Grammar $G = (S, P)$ is given by a set of grammatical symbols and a set of productions $P \subseteq S \times S^*$. We let relation $\rightarrow \subseteq S^* \times S^*$ be given by $w \rightarrow w'$ iff exist $u_1, u_2 \in S^*$ and $(X, u) \in P$ such that $w = u_1 \cdot X \cdot u_2$ and $w' = u_1 \cdot u \cdot u_2$; and we let $\rightarrow^*$, the derivation relation, be its reflexive and transitive closure. A symbol is said to be used, respectively defined when it appears in the right-hand side, respectively left-hand side of some production. We let $\bullet G$ and $G\bullet$ denote respectively the set of used but not defined symbols, and the set of defined but not used symbols respectively.

Our purpose is to define some abstraction of the grammar, called its *interface*, whose aim is to specify what services are provided, which external services are required to carry them out and an over-approximation of the dependencies between required and provided services (the potential dependencies). In particular the interface disregards internal tasks.
As a first attempt one considers that the provided service A potentially relies on external service B if a derivation $A \to^* u$ exists where word u contains an occurrence of B.

**Definition 3.2.** The interface of a grammar $G = (S, P)$ is $I(G) = (\bullet G, R(G), G\bullet)$ where $R(G) = \{(A, B) | \exists u \in S^* \ B \to^* u \wedge \#_B(u) \neq 0\}$ and $\#_B(u)$ denotes the number of occurrences of symbol B in word u.

<figure><img src="image_5.png" /><figcaption>**Figure 2.** An interface</figcaption></figure>

The interface of the role given in Figure 3 is relation $R = \{(C, A), (D, A)\}$. It is an over-approximation of the dependencies since it may happen that A uses none of the services C and D (using derivation $A \to^* \varepsilon$) or only C (using derivation $A \to^* C$). But an external user invoking service A does not know how the service will be carry out and therefore he must assume the availability of all external services that may potentially be used.

We shall nonetheless assume that the grammar is reduced.

**Definition 3.3.** A grammar is reduced if (i) every symbol is accessible:

$$ (\forall B \in S) (\exists A \to^* u) \quad A \in G^\bullet \wedge \#_B(u) \neq 0 $$

and (ii) for every symbol A exists a derivation $A \to^* u$ leading to a word u all of whose symbols are in $\bullet G$.

Recall that we interpret a production as an action that is performed in order to (partially) solve the task A in its left-hand side, and the symbols in its right-hand side represent the residual tasks that should in turn be solved in order to get a full completion of A. Thus a derivation $A \to^* u$ is interpreted as a process (a partially ordered set of actions) directed towards the resolution of task A, and this process is complete if u is the empty word. The process is conditionally complete if u contains only external services (symbols in $\bullet G$) since its completion is then conditioned by the complete execution of these services by its environment. If $\bullet G = \emptyset$, i.e. the grammar represent a standalone application that relies on no external services, and if the grammar is reduced then every partial resolution of a task can be extended in order to reach completion. This property is called soundness. One can define a relative notion of conditional soundness stating that any provided service can indeed be rendered using external services irrespective of the way the computation started. The soundness property that can easily be checked by a fixed point computation is nonetheless undecidable for guarded attribute grammars due to fact that data attached to services can dynamically restrict the set of potentially applicable productions [4]. Note moreover that the soundness of its underlying grammar is neither a sufficient nor a necessary condition for the soundness of a guarded attribute grammar due to the non-monotony of this property arising from the combination of a universal and an existential quantifier in its definition:

$$ \forall A \to^* u \quad \exists u \to^* \varepsilon $$

**Definition 3.4.** Let $\Omega$ denote a fixed set of services. An interface $(\bullet R, R, R\bullet)$ consists of a finite binary relation $R \subseteq \Omega \times \Omega$ and disjoint subsets $\bullet R$ and $R\bullet$ of $\Omega$, such that $\bullet R = R^{-1}(\Omega) = \{A \in \Omega | \exists B \in \Omega (A, B) \in R\}$ and $R\bullet \supseteq R(\Omega) = \{B \in \Omega | \exists A \in \Omega (A, B) \in R\}$. The set $R\bullet$ stands for the services provided (or defined) by the interface and $\bullet R$ for the required (or used) services. The relation $(A, B) \in R$ indicates that service B potentially
depends upon service A. Thus $A \in R^* \setminus R(\Omega)$ is a service provided by the interface that requires no external services. An interface is closed (or autonomous) if relation $R$ (and thus also $\bullet R$) is empty. Thus a closed interface is given by the set of services that it (autonomously) provides.

Note that since $\bullet R$ is the domain of relation $R$, the set of required services may be left implicit. The same is not true for the set of provided services since it can strictly encompass the codomain of the relation. Still, we shall by abuse of notation use the same symbol to denote an interface and its underlying relation.

# 4. Relations and Interfaces

The theory of interfaces that we consider is mainly a calculus of relations [8] even though we put stress on the (concurrent) composition rather than on the usual (sequential) composition of relations. As a result we shall introduce a residuation operation for the concurrent composition in place of the usual left and right residuals for sequential composition. Similarly our implementation order will mostly be given by the set-theoretical inclusion of relations.

In order to ease notations and computations we shall use the following conventions. First we shall identify a relation $R \subseteq \Omega \times \Omega$ such that $R(\Omega) \cap R^{-1}(\Omega) = \emptyset$ with the interface $(\bullet R, R, R^*)$ such that $\bullet R = R^{-1}(\Omega)$ and $R^* = R(\Omega)$. We also identify a set $X \subseteq \Omega$ with the restriction of the identity relation to set $X$, i.e., the diagonal $\{(A, A) \in \Omega^2 | A \in X\}$. By doing so, one can for instance express the condition $B \in Y \wedge (\exists C \in X (A, C) \in R \wedge (C, B) \in Y)$ for $R, S \subseteq \Omega \times \Omega$ and $X, Y \subseteq \Omega$ as $(A, B) \in R; X; S; Y$ where $R_1; R_2$ denote the usual (sequential) composition of relations: $R_1; R_2 = \{(A, C) \in \Omega^2 | \exists B \in \Omega (A, B) \in R_1 \wedge (B, C) \in R_2\}$. Note moreover that with this convention one has $X \cap Y = X; Y$ for $X$ and $Y$ subsets of $\Omega$.

We extend the following operations on binary relations to similar operations on interfaces:

**The empty interface** that renders no service at all is $\emptyset = (\emptyset, \emptyset, \emptyset)$.

**The sequential composition** $R_1; R_2$ of two interfaces $R_1$ and $R_2$ is defined when $\bullet R_1 \cap R_2^* = \emptyset$ and is then given by the composition of their underlying relations with $(R_1; R_2) = R_1^{-1}(R_2) \subseteq \bullet R_1$ and $(R_1; R_2)^* = R_2(R_1^*) \subseteq R_2^*$.

**The restriction** $R \upharpoonright O$ of interface $R$ to $O \subseteq \Omega$ is given by $R|O = \{(A, B) \in R | B \in O\}$, i.e. $R \upharpoonright O = R; 0$, and $(R|O)^* = O \cap R^*$ and $\bullet(R|O) = R^{-1}(O \cap R^*)$. Note that $\bullet(R|O)$ may be a strict superset of the image of the underlying relation of the restriction.

# 5. The Composition of Interfaces

The union of interfaces is an interface if none of the services defined by an interface is used by another one. In the general case $R = (\cup_i \bullet R_i, \cup_j R_j, \cup_i R_i^*)$ satisfies the conditions in Definition 3.4 but $\bullet R \cap R^* = \emptyset$. If relation $R$ is acyclic we say that it is a *quasi-interface* since it induces an interface given by the following definition.
**Definition 5.1.** If $R = (\bullet R, R, R^\bullet)$ is a quasi-interface, i.e. $R$ is an acyclic relation, $\bullet R = R^{-1}(\Omega)$ and $R^\bullet \supseteq R(\Omega)$, then we let $\langle R \rangle = R^* \cap (I \times O)$, where $I = \bullet R \setminus R^\bullet$ and $O = R^\bullet$. It is an interface with $\bullet \langle R \rangle = I$ and $\langle R \rangle^\bullet = O$.

<figure><img src="image_6.png" /><figcaption>**Figure 3.** *Interface induced by a quasi-interface*</figcaption></figure>

For instance if $R_1 = (\emptyset, \emptyset, \{A\})$ is the autonomous interface that provide service A and $R_2 = (\{A\}, \{(A, B)\}, \{B\})$ uses A to define another service B, then they jointly provide an autonomous interface $\langle R_1 \cup R_2 \rangle = (\emptyset, \emptyset, \{A, B\})$ that provides services A and B. Note that the information that B requires A is lost: the meaningful information is that the interface exports A and B and has no imports. If we assume that interface $R_1$ rather produces service A from B, namely $R_1 = (\{B\}, \{(B, A)\}, \{A\})$, then the computation of the composition would also give $\langle R_1 \cup R_2 \rangle = (\emptyset, \emptyset, \{A, B\})$ even though these two interfaces when combined together cannot render any service. This is the rationale for assuming that a quasi-interface must be acyclic. More specifically, what this later example shows is the (simplest) illustration of two grammars that are reduced but whose union is not. This is due to the cycle created when we put them together. It is immediate that the union of two reduced grammars whose union of interfaces is acyclic is also reduced. Our objective is to be able to present an autonomous grammar as the gathering of subgrammars. The global grammar will thus be reduced (and therefore sound) if each of the subgrammars is reduced and if the operation of union (whose associativity we will see below) preserves this property. Hence the importance of this acyclicity hypothesis, even though it is somewhat pessimistic. In a way, this assumption imposes a constraint on how to break down a system into sub-modules, i.e. how to structure our specification. In practice, as we have experienced in our previous studies [7], these constraints are reasonable. Nevertheless, if we give ourselves finer abstractions of grammars, which will be done further by introducing non-deterministic interfaces, we can end up with less constrained forms of composition.

**Definition 5.2.** Two interfaces $R_1$ and $R_2$ are said to be composable if their union $R_1 \cup R_2$ is an acyclic relation and $R_1^\bullet \cap R_2^\bullet = \emptyset$. Then we let $R_1 \bowtie R_2 = \langle R_1 \cup R_2 \rangle$ denote their composition.

<figure><img src="image_7.png" /><figcaption>**Figure 4.** *The composition of two interfaces.*</figcaption></figure>

Note that $(R_1 \bowtie R_2)^\bullet = R_1^\bullet \cup R_2^\bullet$. Moreover, since $\bullet R_i \cap R_i^\bullet = \emptyset$ for $i = 1, 2$ one gets
$$ \bullet (R_1 \bowtie R_2) = (\bullet R_1 \setminus R_2^\bullet) \cup (\bullet R_2 \setminus R_1^\bullet) $$

It follows also directly from the definition that the composition of interfaces is commutative and has the empty interface as neutral element. Note that we may have $\bullet R_1 \cap \bullet R_2 \neq \emptyset$, thus both interfaces may require some common external services. The following example shows that the composition is not associative if we do not require that composable interfaces have disjoints outputs. Of course choosing to have an associative composition operation of interfaces is a matter of choice. One could alternatively have chosen to drop the assumption that composable interfaces have disjoint sets of outputs and to deal with a non associative composition operation.
**Exemple 5.3.** Let $R_1, R_2$, and $R_3$ the three interfaces given in Figure 5. If $R_1 \bowtie (R_2 \bowtie R_3) = (R_1 \bowtie R_2) \bowtie R_3$ we would expect this interface to be given by $R = \langle R_1 \cup R_2 \cup R_3 \rangle$ hence $R = \{(A, D), (C, D), (A, E), (B, E), (C, E)\}$. Note that service D may be produced by either $R_1$ or $R_3$ so that we find both (A, D) and (C, D) as dependencies in R. It follows that E potentially depends on both A, B, and C. However if we compute $R_1 \bowtie (R_2 \bowtie R_3)$ we get $R_r = \{(A, D), (C, D), (B, E), (C, E)\}$ because in $R_2$ the required service D is no longer an input in $R_2 \bowtie R_3$. Symmetrically $R_l = (R_1 \bowtie R_2) \bowtie R_3 = \{(A, D), (C, D), (A, E), (C, E)\}$.

<figure><img src="image_8.png" /><figcaption>**Figure 5.** A counter-example showing that associativity of composition does not hold if interfaces shared some provided services.</figcaption></figure>

**Remark 5.4.** $\langle R \rangle = \{(A, B) \in R^* | \neg (\exists C \in \Omega. (C, A) \in R)\}$. Hence any $(A, B) \in \langle R \rangle$ is associated with a path in the graph of R that leads to $B \in R^*$ and cannot be extended on the left. Note that such a path is of the form $A = A_0 \to A_1 \to \dots \to A_n = B$, with $A \in \bullet R \setminus R^*$ and $\forall 1 \le i \le n (A_{i-1}, A_i) \in R$. Note that $\forall 1 \le i \le n A_i \in R^*$, i.e. all elements in this path but the first one, namely A, belongs to $R^*$.

**Proposition 5.5.** The composition of interfaces is associative. More precisely, if $R_1 \cdots R_n$ are pairwise composable interfaces, then $\bowtie_{i=1}^n R_i = \langle R_1 \cup \cdots \cup R_n \rangle$.

*Proof.* Using the commutativity of composition, the proposition follows by induction on $n$ as soon as it has been verified that $(R_1 \bowtie R_2) \bowtie R_3 = \langle R_1 \cup R_2 \cup R_3 \rangle$ for pairwise composable interfaces $R_1, R_2$ and $R_3$. Hence we have to show $\langle\langle R_1 \cup R_2 \rangle\rangle \cup \langle R_3 \rangle = \langle R_1 \cup R_2 \cup R_3 \rangle$ or, more generally, that $\langle\langle R \rangle\rangle \cup R' \rangle = \langle R \cup R' \rangle$ where $R \subseteq \Omega \times \Omega$ is a finite binary relation with possibly $\bullet R \cap R^* \neq \emptyset$, and $R'$ is an interface such that $(R \cup R')^*$ acyclic, and $R^* \cap (R')^* = \emptyset$. First, note that $\langle R \rangle^* = R^*$ and $(R \cup R')^* = R^* \cup (R')^*$ and thus $\langle\langle R \rangle\rangle \cup R' \rangle^* = \langle R \cup R' \rangle^*$. By condition $R^* \cap (R')^* = \emptyset$ we deduce $R \cap R' = \emptyset$. More precisely a transition $(A, B) \in R \cap R'$ belongs (exclusively) either to R or to $R'$ depending respectively on $B \in R^*$ or $B \in (R')^*$. According to Remark 5.4, let $\pi = A_0 \to A_1 \to \dots \to A_n$ be a path in $R \cup R'$ (i.e. $\forall 1 \le i \le n (A_{i-1}, A_i) \in R \cup R'$ and $A_0 \in \bullet (R \cup R') \setminus (R \cup R')^*$) witnessing that $(A_0, A_n) \in \langle R \cup R' \rangle$. Let $\pi' = A_i \to \dots \to A_j$ be a maximal sub-path of $\pi$ made of R transitions only (i.e., $\forall i \le k \le j A_k \in R^*$). Then either $A_i = A_0$ or $(A_{i-1}, A_i) \in R'$. In both cases $A_i \in \bullet R \setminus R^*$ and thus $\pi'$ is a path witnessing that $(A_i, A_j) \in \langle R \rangle$ from which it follows that $\pi$ is a path witnessing that $(A_0, A_n) \in \langle\langle R \rangle\rangle \cup R' \rangle$, showing $\langle R \cup R' \rangle \subseteq \langle\langle R \rangle\rangle \cup R'$ and hence $\langle\langle R \rangle\rangle \cup R' \rangle = \langle R \cup R' \rangle$ since the converse inclusion is immediate. $\square$
The following two cases of composition are noteworthy:

<figure><img src="image_9.png" /><figcaption>**Figure 6.** Cascade product and (direct) product</figcaption></figure>

**Cascade product** If $R_1^\bullet \cap \bullet R_2 = \emptyset$ we denote $R_1 \times R_2$ their composition (or $R_2 \times R_1$ since this operation as a particular case of $\bowtie$ is still commutative). Then $\bullet(R_1 \times R_2) = (\bullet R_1 \setminus R_2^\bullet) \cup \bullet R_2$, and $(R_1 \times R_2)^\bullet = R_1^\bullet \cup R_2^\bullet$.

**(Direct) product** If both $R_1^\bullet \cap \bullet R_2 = \emptyset$ and $R_2^\bullet \cap \bullet R_1 = \emptyset$ hold we say that the composition is the product of $R_1$ and $R_2$, denoted as $R_1 \times R_2$. Note that $R_1 \times R_2 = R_1 \cup R_2$ and thus $\bullet(R_1 \times R_2) = \bullet R_1 \cup \bullet R_2$ and $(R_1 \times R_2)^\bullet = R_1^\bullet \cup R_2^\bullet$.

**Remark 5.6.** The underlying relation of the wreath product is given by

$$R_1 \times R_2 = (I_1 \times R_2); (R_1 \times O_2)$$

where $I_1 = \bullet R_1 \setminus R_2^\bullet$ and $O_2 = R_2^\bullet \setminus \bullet R_1$.

**Definition 5.7.** $R_1$ is a component of $R$, in notation $R_1 \subseteq R$, if there exists an interface $R_2$ such that $R = R_1 \bowtie R_2$. $R_1$ is a strict component of $R$, in notation $R_1 \supseteq R$, if there exists an interface $R_2$ such that $R = R_1 \times R_2$.

# 6. Implementation Order

An environment for an interface is any component that provides all the services required by the interface and uses for that purpose only services that are provided by it.

**Definition 6.1.** An interface $E$ is an admissible environment for an interface $R$ if the two interfaces can be composed and the resulting composition is a closed interface, namely $\bullet(R \bowtie E) = \emptyset$. We let $\text{Env}(R)$ denote the set of admissible environments of interface $R$.

**Definition 6.2.** An interface $R_2$ is an implementation of interface $R_1$, in notation $R_1 \le R_2$, when $R_2^\bullet = R_1^\bullet$ and $R_2 \subseteq R_1$.

Thus $R_2$ is an implementation of $R_1$ if it renders the same services as $R_1$ using only services already used by $R_1$ and with less dependencies.<fnref n="1" /> The following proposition shows that $R_2$ is an implementation of interface $R_1$ if and only if it can be substituted to $R_1$ in any admissible environment for $R_1$.

<footnote n="1">1. In practice an interface used as an implementation may define additional services: $R_2$ is a weak implementation of interface $R_1$, in notation $R_1 \leq_w R_2$, if $R_2^\bullet \supseteq R_1^\bullet$ and $R_1 \leq R_2 \upharpoonright(R_1^\bullet)$. However the additional services provided by $R_2$ should be hidden so that they cannot conflict with services of any environment compatible with $R_1$.</footnote>
**Proposition 6.3.** $R_1 \leq R_2$ if and only if $\mathbf{Env}(R_1) \subseteq \mathbf{Env}(R_2)$.

*Proof.* We first show that the condition is necessary. For that purpose let us assume $R_1 \leq R_2$ (which means that $R_2^\bullet = R_1^\bullet$ and $R_2 \subseteq R_1$) and prove that any admissible environment $E$ for $R_1$ is an admissible environment for $R_2$. Since $E$ can be composed with $R_1$ we get $R_1^\bullet \cap E^\bullet = \emptyset$ and $E \cup R_1$ is acyclic. Then we also have $R_2^\bullet \cap E^\bullet = \emptyset$ and $E \cup R_2$ is acyclic since $R_2^\bullet = R_1^\bullet$ and $R_2 \subseteq R_1$. Hence $E$ can be composed with $R_2$. Moreover, for the same reasons, $\bullet(E \bowtie R_2) = (\bullet E \setminus R_2^\bullet) \cup (\bullet R_2 \setminus E^\bullet) \subseteq (\bullet E \setminus R_1^\bullet) \cup (\bullet R_1 \setminus E^\bullet) = \bullet(E \bowtie R_2) = \emptyset$. Henceforth $E \in \mathbf{Env}(R_2)$. We show that the condition is sufficient by contradiction. Since $R_1 \leq R_2$ implies $R_2^\bullet = R_1^\bullet$ one has to construct $\mathcal{E} \in \mathbf{Env}(R_1) \setminus \mathbf{Env}(R_2)$ under the assumption that $R_1 \not\subseteq R_2$. Let $(A, B) \in R_2 \setminus R_1$ then the interface we are looking for is $E$ such that $\bullet E = \{B\}$, $E^\bullet = \bullet R_2$, and $E = \{(B, A)\}$. Indeed, $E$ can be composed with $R_1$ but not with $R_2$ because of the cycle $B \to A \to B$ in $(R_1 \cup \{(B, A)\})^*$. Moreover the composition of $E$ with $R_1$ gives a closed interface. $\square$

# 7. Residual Specification

**Proposition 7.1.** If $R_1 \subseteq R$ then $R = R_1 \times (R_\vee/R_1)$ where $R_\vee/R_1$, called the strict residual of $R$ by $R_1$, is given as the restriction of $R$ to $R^\bullet \setminus R_1^\bullet$. If $R = R_1 \times R_2$ then $R \upharpoonright R_2^\bullet = R_\vee/R_1 = R_2$ and $R = (R_\vee/R_2) \times (R_\vee/R_1)$.

*Proof.* One has to show that if $R_1$ and $R_2$ can be composed and $R = R_1 \bowtie R_2$ then $R = R_1 \times R_\vee/R_1$ and $R = (R_\vee/R_1) \times (R_\vee/R_1)$ where $R_\vee/R_i = R \upharpoonright R_j^\bullet$ for $\{i, j\} = \{1, 2\}$. By remark 5.4 $R_1 \bowtie R_2$ is the (unique)<fnref n="2" /> solution of the system of equations

$$R_1 \bowtie R_2 = (A \cup I_1); R_1 \cup (B \cup I_2); R_2$$

where $I_1 = \bullet R_1 \setminus R_2^\bullet$

$I_2 = \bullet R_2 \setminus R_1^\bullet$

$O_1 = R_1^\bullet \cap \bullet R_2$

$O_2 = R_2^\bullet \cap R_1$

$A = (B \cup I_2); R_2; O_2$

$B = A \cup I_1); R_1; O_1$

Then it is immediate (see Figure 7) that $R_1 \times (R_1 \bowtie R_2) \upharpoonright R_2^\bullet$ is solution of the same system of equations and thus the two relations coincide. The same system of equations is associated with $(R_\vee/R_2) \times (R_\vee/R_1)$ as shown in Figure 8.

It remains to show that if $R = R_1 \times R_2$ then $R_\vee/R_1 = R \upharpoonright R_2^\bullet$ coincides with $R_2$, and indeed $R \upharpoonright R_2^\bullet = ((\bullet R_1 \setminus R_2^\bullet) \cup R_2); (R_1 \cup R_2^\bullet) \upharpoonright R_2^\bullet = ((\bullet R_1 \setminus R_2^\bullet) \cup R_2) \upharpoonright R_2^\bullet = R_2$ by Remark 5.6 and because $R_1^\bullet \cap R_2^\bullet = \emptyset$. $\square$

**Corollary 7.2.** If $R^\bullet = O_1 \cup O_2$ with $O_1 \cap O_2 = \emptyset$ then $R = (R \upharpoonright O_1) \times (R \upharpoonright O_2)$ and $R \upharpoonright O_i = R_\vee/(R \upharpoonright O_j)$ for $\{i, j\} = \{1, 2\}$ and the following conditions are equivalent:

1) $R_1$ is a strict component of $R: \exists R_2 \cdot R = R_1 \times R_2,$

2) $R_1$ is a left component in a cascade decomposition of $R: \exists R' \cdot R = R' \times R_2,$

<footnote n="2">2. Uniqueness comes from the fact that only finite paths are considered due to acyclicity.</footnote>
<figure><img src="image_10.png" /><figcaption>**Figure 7.** $R = R_1 \times (R_\vee/R_1)$ when $R = R_1 \bowtie R_2$</figcaption></figure>

<caption>**Figure 8.** $(R_\vee/R_2) \times (R_\vee/R_1)$</caption>

3) $R_1$ is a restriction of $R$: $R_1 = R|(R_1^\bullet)$, and

4) $R_1$ is a strict residual of $R$: $\exists R_2 \cdot R_1 = R_\vee/R_2$.

Now we state the residual property that relies on the two following lemmas.

**Lemma 7.3.** $R_1 \le R_2$ implies $R \bowtie R_1 \le R \bowtie R_2$ whenever $R_1$ and $R_2$ are both components of $R$.

*Proof.* By Remark 5.4 $(A, B) \in R \bowtie R_i$ if and only if there exists a finite sequence $A_0, \dots, A_n$ such that $A = A_0 \in \bullet R \setminus R_i^\bullet \cup \bullet R_i \setminus R^\bullet$, $(A_{k-1}, A_k) \in R \cup R_i$ for all $1 \le k \le n$, and $B = A_n \in R^\bullet \cup R_i^\bullet$. Monotony of $R \bowtie -$ then follows from the fact that $R_1^\bullet = R_2^\bullet$. $\square$

**Lemma 7.4.** $R_1 \le R_2$ implies $R_1 \vee R \le R_2 \vee R$ whenever $R$ is a component of both $R_1$ and $R_2$.

*Proof.* $R_1 \le R_2$ means that $R_1^\bullet = R_2^\bullet$ and $R_2 \subseteq R_1$. Then $R_1 \vee R = R_1|(R_1^\bullet \setminus R^\bullet) \le R_2|(R_2^\bullet \setminus R^\bullet)$ because $R_1^\bullet \setminus R^\bullet = R_2^\bullet \setminus R^\bullet$ and $R_2 \subseteq R_1$. $\square$

**Proposition 7.5.** If $R_1$ is a component of $R$ and $R'$ is an interface then

$$R_\vee R_1 \le R' \iff R \le R_1 \bowtie R'$$

*Proof.* By Proposition 7.1 and Lemma 7.3 we get $R_\vee R_1 \le R' \implies R = R_1 \bowtie (R_\vee/R_1) \le R \bowtie R'$. The converse direction follows by Lemma 7.4 and Proposition 7.1: $R \le R_1 \bowtie R' \implies R_\vee R_1 \le (R \bowtie R')\vee R_1 = R'$. $\square$

By Corollary 7.2 the above proposition implies that an implementation of a strict residual $R_\vee/R_1$ is a strict component of $R$ and therefore it cannot capture all the components of an implementation of $R$, i.e. all interfaces $R'$ such that $R \le R_1 \bowtie R'$. For that purpose we need to add in the residual all the dependencies between the respective outputs of the component and of the residual that do not contradict dependencies in $R$:

**Definition 7.6.** If $R_1 \subseteq R$ the residual $R/R_1$ of $R$ by $R_1$ is given by $(R/R_1)^\bullet = R^\bullet \setminus R_1^\bullet$ and $R/R_1 = R_\vee R_1 \cup R_\vee R_1$ where

$$R \nparallel R_1 = \{(A, B) \in R_1^\bullet \times (R^\bullet \setminus R_1^\bullet) \mid R^{-1}(\{A\}) \subseteq R^{-1}(\{B\})\}.$$
**Lemma 7.7.** If $R_1$ is a component of $R$ then $R_1 \bowtie (R/R_1) = R$

*Proof.* Since $(R/R_1)^\bullet = R^\bullet \setminus R_1^\bullet = (R_1^\vee/R_1)^\bullet$ and $R/R_1 \supseteq R_1^\vee/R_1$ one has $R/R_1 \le R_1^\vee/R_1$ and by Lemma 7.3 $R_1 \bowtie (R/R_1) \le R_1 \bowtie (R_1^\vee/R_1) = R_1 \times (R_1^\vee/R_1) = R$. We are left to prove that $R_1 \bowtie (R/R_1) \subseteq R$. Let $(A, B) \in R_1 \bowtie (R/R_1)$ then by Remark 5.4 there exists a sequence $A_0, \dots, A_n$ such that $A = A_0 \in \bullet (R_1 \bowtie (R/R_1))$, $B = A_n \in (R_1 \bowtie (R/R_1))^\bullet = R^\bullet$, and $(A_{i-1}, A_i) \in R_1 \cup (R/R_1)$ for all $1 \le i \le n$. One has $\bullet (R_1 \bowtie (R/R_1)) = \bullet R_1 \setminus (R^\bullet \setminus R_1^\bullet) \cup \bullet (R/R_1) \setminus R_1^\bullet$. Thus $A \in \bullet R$ because $\bullet R_1$ and $\bullet (R/R_1)$ are subsets of $\bullet R$. There are three possibilities for each transition $(A_{i-1}, A_i)$: (i) $(A_{i-1}, A_i) \in R_1$ if $A_i \in R_1^\bullet$, (ii) $(A_{i-1}, A_i) \in R_1^\vee/R_1$ if $A_i \in R^\bullet \setminus R_1^\bullet$ and $A_{i-1} \in \bullet R \setminus R_1^\bullet$, or (iii) $(A_{i-1}, A_i) \in R_1^\vee/R_1$ if $A_i \in R^\bullet \setminus R_1^\bullet$ and $A_{i-1} \in R_1^\bullet$. Note that if the sequence contains no transition of the latter category then it witnesses that $(A, B) \in R$ due to the fact that $R_1 \bowtie (R_1^\vee/R_1) = R_1 \times (R_1^\vee/R_1) = R$. We're going to gradually eliminate all transitions of type (iii). For doing so let us consider the leftmost transition of this latter category if it exists. Thus $i$ is the smallest index such that $(A_{i-1}, A_i) \in R_1^\vee/R_1$. Since $R_1^\bullet$ is a subset of $R^\bullet$ and thus is disjoint of $\bullet R$ we deduce that $A_{i-1} \ne A$ and thus $i-1 \ge 1$. Now the sequence $\sigma: A = A_0 \to \dots \to A_{i-1}$, which contains only transitions of types (i) or (ii), witnesses that $A \in R^{-1}(\{A_{i-1}\})$. Since $(A_{i-1}, A_i) \in R_1^\vee/R_1$ we deduce that $A \in R^{-1}(\{A_i\})$. Thus by replacing sequence $\sigma$ by transition $(A, A_i)$ we get a sequence with one less transition in $R_1^\vee/R_1$ and thus we end up with a sequence with no transition in $R_1^\vee/R_1$ witnessing that $(A, B) \in R$. $\square$

**Lemma 7.8.** If $R_1$ and $R_2$ can be composed then $(R_1 \bowtie R_2)/R_1 \le R_2$.

*Proof.* Let $R_1$ and $R_2$ interfaces that can be composed, in particular $R_1^\bullet \cap R_2^\bullet = \emptyset$, and $R = R_1 \bowtie R_2$. Then $(R/R_1)^\bullet = (R_1^\bullet \cup R_2^\bullet) \setminus R_1^\bullet = R_2^\bullet$. $(A, B) \in R_2 \setminus (R_1^\vee/R_1) = R_2 \setminus (R_1^\vee R_2)$ if and only if $(A, B) \in R_2$ (hence $B \in R_2^\bullet$, and $A \in \bullet R_2 \cap R_1^\bullet$. Then necessarily $R^{-1}(\{A\}) \subseteq R^{-1}(\{B\})$ and therefore $(A, B) \in R_1^\vee/R_1$. It follows that $R/R_1 = R_1^\vee/R_1 \cup R_1^\vee/R_1 \supseteq R_2$ and thus $R/R_1 \le R_2$. $\square$

**Lemma 7.9.** $R_1 \le R_2$ implies $R_1/R \le R_2/R$ whenever $R$ is a component of both $R_1$ and $R_2$.

*Proof.* Recall that $R_i^\vee/R = \{(A, B) \in R^\bullet \times (R_i^\bullet \setminus R^\bullet) \mid R^{-1}(\{A\}) \subseteq R^{-1}(\{B\})\}$ and $R_i/R = R_i^\vee/R \cup R_i^\vee/R$. $R_1 \le R_2$ means that $R_1^\bullet = R_2^\bullet$ and $R_2 \subseteq R_1$ from which it follows that $R^\bullet \times (R_1^\bullet \setminus R^\bullet) = R^\bullet \times (R_2^\bullet \setminus R^\bullet)$ and thus $R_2^\vee/R \subseteq R_1^\vee/R$. The result then follows from Lemma 7.4 and $(R_1/R)^\bullet = R_1^\bullet \setminus R^\bullet = R_2^\bullet \setminus R^\bullet = (R_2/R)^\bullet$. $\square$

**Proposition 7.10.** If $R_1$ is a component of $R$ and $R'$ is an interface then

$$R/R_1 \le R' \iff R \le R_1 \bowtie R'$$

*Proof.* By Lemma 7.7 and Lemma 7.3 we get $R/R_1 \le R' \implies R = R_1 \bowtie (R/R_1) \le R \bowtie R'$. The converse direction follows by Lemma 7.9 and Lemma 7.8: $R \le R_1 \bowtie R' \implies R/R_1 \le (R \bowtie R')/R_1 \le R'$. $\square$

Hence the residual $R/R_1$ characterizes those interfaces that, when composed with $R_1$, produce an implementation of $R$.
# 8. Non-deterministic Interfaces

The notion of interface presented so far is still a somewhat rough abstraction of the roles described by a GAG specification. In particular, we would like to be able to take into account the non-determinism that results from the choices offered to the user on how to solve a task. For that purpose we replace relation $R \subseteq \Omega \times \Omega$ by a map $R : \Omega \to \wp(\wp(\Omega))$ that associates each service $A \in \Omega$ with a finite number of alternative ways to carry it out, and each of these with the set of external services that it requires.

**Definition 8.1.** A non-deterministic quasi interface on a set $\Omega$ of services is a map $R : \Omega \to \wp(\wp(\Omega))$. We let $R^* = \{A \in \Omega \mid R(A) \neq \emptyset\}$ and $\bullet R = \cup \{R(A) \mid A \in \Omega\}$. It is a non-deterministic interface when $\bullet R \cap R^* = \emptyset$.

**Definition 8.2.** The non-deterministic interface of a grammar $G = (S, P)$ is the function $R = NI(G) : \Omega \to \wp(\wp(\Omega))$ where $\Omega = \bullet G \cup G^*$ (i.e. grammatical symbols that correspond to internal tasks are abstracted) and $R(A) = \{\pi(u) \subseteq \bullet G \mid A \to^* u\}$ where $\pi(u) = \{A \in S \mid \vdash_A(u) \neq 0\}$ is the set of grammatical symbols that occur in word $u$. Thus a set of symbols is in $R(A)$ if and only if it is the set of symbols of a word in $(\bullet G)^*$ that derives from $A$. Note that if the grammar is reduced one has $\bullet R = \bullet G$ and $R^* = G^*$.

This new representation of interfaces is richer than its deterministic counterpart. It is more precise and might indeed been considered too much precise in some situations since it requires to handle more information. Nonetheless non-deterministic interfaces are in many respect more easy to handle than deterministic interfaces and they lead to simplified definitions and easier proofs as shown next. In particular, and by contrast with deterministic interfaces, both sets $\bullet R$ and $R^*$ can be left implicit. This is due to the fact that services $A$ provided by a non-deterministic interface that requires no external services are now explicitly given as those such that $R(A) = \{\emptyset\}$ (which should not be confused with $R(A) = \emptyset$ which corresponds to $A \notin R^*$). Thus the following operations can straightforwardly be defined for non-deterministic quasi-interfaces.

- **Sequential composition:** $R_1; R_2(A) = \{\cup_i X_i \mid \{A_1, \dots, A_n\} \in R_2(A) \text{ and } X_i \in A_i\}$.

- **Restriction:** $R \upharpoonright O(A) = R(A)$ if $A \in O$ and $R \upharpoonright O(A) = \emptyset$ otherwise.

- **Union:** $(\cup_i R_i)(A) = \cup_i R_i(A)$.

- **Transitive closure:** $R^*(A) = \cup_{i=1}^\infty R^i(A)$ where $R^{n+1} = R^n$; $R$. Note that $R^* = R$ if $R$ is an interface.

- **Composition:** $R_1 \bowtie R_2 = \langle R_1 \cup R_2 \rangle$ where $\langle R \rangle(A) = R^*(A) \cap \wp(\wp(\Omega \setminus R^*))$ is the non-deterministic interface induced by the non-deterministic quasi-interface $R$. Note that $(R_1 \bowtie R_2)^* \subseteq R_1^* \cup R_2^*$ and $\bullet (R_1 \bowtie R_2) \subseteq (\bullet R_1 \setminus R_2^*) \cup (\bullet R_2 \setminus R_1^*)$. A quasi-interface $R$ is said to be reduced when $\bullet \langle R \rangle = \bullet R$ and $\bullet \langle R \rangle = \bullet R$. We say that two interfaces $R_1$ and $R_2$ are safely composable$^3$ when their union (the quasi-interface $R_1 \cup R_2$) is reduced. Two interfaces $R_1$ and $R_2$ are safely composable if and only if $(R_1 \bowtie R_2)^* = R_1^* \cup R_2^*$ and $\bullet (R_1 \bowtie R_2) = (\bullet R_1 \setminus R_2^*) \cup (\bullet R_2 \setminus R_1^*)$.

It is readily shown that the composition of non-deterministic quasi-interfaces is associative and one does not need to require that the individual components have disjoint output

<footnote n="3">3. Safely composability is the natural extension to the non-deterministic case of the composability of deterministic interfaces. However since we here first defined the operation of composition of non-deterministic (quasi-) interfaces we felt obliged to add this qualifying term.</footnote>
sets to ensure that property. Thus non-deterministic quasi-interfaces equipped with this composition operation is a commutative monoid (whose neutral element is the empty interface). Moreover $R \bowtie R = \langle R \rangle$ and since $\langle R \rangle = R$ when $R$ is an interface, we deduce that the composition of interfaces is idempotent.

The natural extension of the implementation order in the non-deterministic case is to let

$$R_1 \leq R_2 \iff (\forall A \in \Omega) (\forall X \in R_1(A)) (\exists Y \in R_2(A)) \cdot Y \subseteq X$$

expressing that anything that $R_1$ can do $R_2$ can do better (namely, it can do the same using fewer external services). This is a pre-order (reflexive and transitive relation) where two non-deterministic interfaces are equivalent when their images for each $A$ have the same sets of minimal elements (for set inclusion) or equivalently have identical upward closures. Say that an interface is *saturated* if $R(A)$ is upward-closed for every $A \in \Omega$. And it is *reduced* when for every $A \in \Omega$ any two elements of $R(A)$ are incomparable. Thus any non-deterministic interface is equivalent to its upward-closure (a saturated interface) and to its restriction to its set of minimal elements (a reduced interface). The order relation on saturated interfaces is simply given by the pointwise set-theoretic inclusion:

$$R_1 \leq R_2 \iff (\forall A \in \Omega) R_1(A) \subseteq R_2(A)$$

Thus their least upper bounds are given by pointwise set-theoretic union: $(\bigvee_i R_i)(A) = \bigcup_i R_i(A)$ and their greatest lower bounds by pointwise set-theoretic intersection: $(\bigwedge_i R_i)(A) = \bigcap_i R_i(A)$. The following properties then immediately follow:

- **distributivity:** $\bigvee_i \bigwedge_j R_{i,j} = \bigwedge_j \bigvee_i R_{i,j}$.

- $(\bigvee_i R_i)^\bullet = \bigcup_i R_i^\bullet$ but also $(\bigwedge_i R_i)^\bullet = \bigcap_i R_i^\bullet$ because the sets $R_i(A)$ are upper closed sets and thus all those which are not empty contain $\Omega$ and thus have non empty intersection.

Note that the greatest lower bound of an arbitrary set of (saturated and non-deterministic) interfaces is also given by $(\bigwedge_i R_i)(A) = \{\bigcup_i X_i \mid \forall i \ X_i \in R_i(A)\}$.

**Lemma 8.3.** *The composition commutes with joins: $R \bowtie (\bigwedge_i R_i) = \bigwedge_i (R \bowtie R_i)$.*

*Proof.* The operation $\bowtie$ is monotonic in each of its argument and thus $R \bowtie (\bigwedge_i R_i) \leq \bigwedge_i (R \bowtie R_i)$. We are left to prove the converse relation. By definition of the sequential composition of relations and the greatest lower bound of interfaces it follows that $R; (\bigwedge_i R_i) = \bigwedge_i (R; R_i)$, and thus $\bigwedge_i R_i^n = (\bigwedge_i R_i)^n$ by induction on $n$. Hence $\bigwedge_i R_i^* = \bigwedge_i (\bigvee_n R_i^n) = \bigvee_n (\bigwedge_i R_i^n) = \bigvee_n (\bigwedge_i R_i)^n = (\bigwedge_i R_i)^*$. It follows that $\langle \bigwedge_i R_i \rangle (A) = (\bigwedge_i R_i)^*(A) \cap \wp(\wp(\Omega \setminus (\bigwedge_i R_i)^*)) = (\bigcap_i R_i^*(A)) \cap \wp(\wp(\Omega \setminus \bigcap_i R_i^*)) = (\bigcap_i R_i^*(A)) \cap \wp(\wp(\bigcup_i (\Omega \setminus R_i^*)) \supseteq (\bigcap_i R_i^*(A)) \cap (\bigcap_i \wp(\wp(\Omega \setminus R_i^*)) = \bigcap_i \langle R_i \rangle (A) \text{ i.e. } \langle \bigwedge_i R_i \rangle \geq \bigwedge_i \langle R_i \rangle. \text{ Thus } R \bowtie (\bigwedge_i R_i) = \langle R \vee (\bigwedge_i R_i) \rangle = \langle \bigwedge_i (R \vee R_i) \rangle \geq \bigwedge_i \langle R \vee R_i \rangle = \bigwedge_i (R \bowtie R_i). \square$

Since we can compute the least upper bound of an arbitrary family of (saturated and non-deterministic) interfaces, one can directly define the residual operation as:

**Definition 8.4.** *The residual of two interfaces is given by: $R/R_1 = \bigwedge \{R' \mid R \leq R_1 \bowtie R'\}$*

which satisfies (almost by definition!) the required property of residuals:
**Proposition 8.5.** $R/R_1 \leq R' \iff R \leq R_1 \bowtie R'$.

*Proof.* $R \leq R_1 \bowtie R' \Rightarrow R/R_1 \leq R'$ by definition of the residual. Conversely let us assume that $R/R_1 \leq R'$ then by monotony $R_1 \bowtie R/R_1 \leq R_1 \bowtie R'$. By lemma 8.3 $R_1 \bowtie R/R_1 = R_1 \bowtie \wedge \{R'' | R \leq R_1 \bowtie R''\} = \wedge \{R_1 \bowtie R'' | R \leq R_1 \bowtie R''\} \geq R$ (since R is a lower bound of the given set). Hence $R \leq R_1 \bowtie R'$. $\square$

# 9. Conclusion

This work is a first attempt to develop an interface theory for distributed collaborative systems in the context of service-oriented programming. We defined a notion of interface in order to explicit how a module can be used in a given environment using an assume/guarantee approach: we describe the set of services that can be provided by the module under the assumption that some other services are available in its environment. We have then defined a residual operation on interfaces characterizing the systems that, when composed with a given component, can complement it in order to realize a global specification. We intend to use residuation to define and structure the activities of crowdsourcing system actors. The residual operation can be used to identify the skills to be sought in the context of existing services in order to achieve a desired overall behaviour. Such a system can be implemented by Guarded Attribute Grammars and interfaces can be used to type applications.

We have mainly worked with basic (deterministic) interfaces. We have nonethe-
less shown how to extend the approach to non-deterministic interfaces. In the non-
deterministic case it becomes possible to define an additional operation, namely an opera-
tion that gives the co-restriction $R|I$ of an interface $R$ to a set of services $I \subseteq \Omega$ by letting
$(R|I)(A) = \{X \subseteq I | X \in R(A)\}$. That operation states how a role can be used when
the set of services actually provided by the environment is known (to be $I$). This opera-
tion can be used to identify the usefulness of a component given by its interface knowing
which services are actually available in the environment. Note that one can define the
corresponding operation on grammars with $NI(G|I) = NI(G)|I: G|I$ by deleting all
productions whose right-hand side contains a grammatical symbol in $\bullet G \setminus I$.

On that basis one can enrich the information to take qualitative information into ac-
count to cope with uncertainty or time constraints. Actually it might be possible that we
have only a partial knowledge of the set of available services in the environement in the
form of a believe function [10] or a possibilistic distribution [11]. The interface should
then allow us to quantify the possibility of realizing a service given this information on
the environment. Similarly information can also be added on time execution, for instance
by limiting behaviour to ensure that services are delivered within certain time constraints..

# 10. References

[1] MARTÍN ABADI, LESLI LAMPORT, "Composing Specifications", *ACM Transactions on Programming Languages and Systems*, vol. 15, 1993:73-132.

[2] MARTÍN ABADI, GORDON D. PLOTKIN, "A logical view of composition", *Theoretical Computer Science*, vol. 114, 1993:3-30.

[3] LUCA DE ALFARO, THOMAS A. HENZINGER, "Interface Automata", *Foundation of Software Engineering (ESEC/FES-9)*, 2001: 109-120.
[4] ERIC BADOUEL, LOÏC HÉLOUËT, GEORGES-EDOUARD KOUAMOU, CHRISTOPHE MORVAN, ROBERT FONDZE JR. NSAIBIRNI, "Active Workspaces; Distributed Collaborative Systems based on Guarded Attribute Grammars", ACM SIGAPP Applied Computing Review, vol. 15, num. 3, 2015:6-34.

[5] DAVID HAREL, AMIR PNUELI, "On the development of reactive systems", Logics Models of Concurrent Systems, NATO ASI Series, vol. F13, Springer Berlin, 1984: 477-498.

[6] PHILIP M. MERLIN, GREGOR VON BOCHMANN, "On the construction of submodule specifications and communication protocols", ACM Transactions on Programming Languages and Systems, vol. 5, 1983:1-25.

[7] ROBERT FONDZE JR NSAIBIRNI, ERIC BADOUEL, GAËTAN TEXIER, GEORGES-EDOUARD KOUAMOU, "Active Workspace: A Dynamic Collaborative Business Process Model for Disease Surveillance Systems", Health Informatics and Medical Systems, Las Vegas, USA, 2016: 58-64.

[8] VAUGHAN R. PRATT, "Origins of the Calculus of Binary Relations", IEEE Logic in Computer Science (LICS'92), Santa Cruz, California, USA, 1992: 248-254.

[9] JEAN-BAPTISTE RACLET, "Residual for Component Specifications", Electronic Notes in Theoretical Computer Science, vol. 215, 2008:93-110.

[10] GLENN SHAFER, A mathematical theory of evidence, Princeton University Press, 1976.

[11] LOFTI ZADEH, "Fuzzy Sets as the Basis for a Theory of Possibility", Fuzzy Sets and Systems, vol. 1, 1978:3-28.

[12] ARTUR CAETANO, ANTONIO RITO SILVA, JOSÉ TRIBOLET, "Business Process Decomposition - An Approach Based on the Principle of Separation of Concerns", Enterprise Modelling and Information Systems Architectures, Vol 5, num 1, 2010: 44-57.

[13] DAVID FERRAIOLO, RICHARD KUHN, "Role-Based Access Control", In 15th NIST-NCSC National Computer Security Conference, 1992: 554-563.

[14] O. KAZIK, "Role-based Approaches to Development of Multi-Agent Systems: A Survey", WDS'10 Proceedings of Contributed Papers, 2010: 19-24.

[15] H. ZHU, "Role mechanisms in collaborative systems", International Journal of Production Research, Vol 44, Num 1, 2006: 181-193.

[16] HAIBIN ZHU, "A role agent model for collaborative systems", In International Conference on Information and Knowledge Engineering, Las Vegas, Vol 2, 2003:438-444

[17] MIKE WINTERS, "BPMN and Microservices Orchestration, Part 1 of 2: Flow Languages, Engines, and Timeless Patterns", https://zeebe.io/blog/2018/08/bpmn-for-microservices-orchestration-a-primer-part-1/, 2018.

[18] ALAIN WEGMANN, GUY GENILLOUD, "The Role of "Roles" in Use Case Diagrams", EPFL-DSC CH-1015 Lausanne, Tech. Report num DSC/2000/024, 2000.

[19] RAVI S. SANDHU, EDWARD J. COYNE, HAL L. FEINSTEIN, CHARLES E. YOUMAN, "Role-Based Access Control Models", Computer, Vol 29, Num 2, 1996: 38-47.

[20] BERND R"UCKER, "The Microservices Workflow Automation Cheat Sheet", https://blog.bernd-ruecker.com/the-microservice-workflow-automation-cheat-sheet-fc0a80dc25aa, 2018.

[21] KRZYSZTOF CZARNECKI, ULRICH W. EISENECKER, "Generative programming-methods, tools and applications", Addison-Wesley, 2000.