The social stance advocated by institutional frameworks and most multi-agent system (MAS) methodologies has resulted in a wide catalogue of software abstractions to encapsulate multiagent interactions. This paper attempts to expose a possible semantic core underlying the wide spectrum of interaction types between autonomous, social and situated software components. In the realm of software architectures, this core has been formalised as an operational model of social connectors describing both the structure and dynamics of multi-agent interactions. This formal model is aimed as the first steps towards the abstract machine of a language to program multi-agent interactions.
From an architectural point of view, interactions between software components are represented
by means of connectors: first-class entities defined on the basis of the different roles displayed by
software components and the protocols that regulate the behaviour of these participating
components [
In the following, we describe the basic entities involved in social interactions. Each kind of entity T will be specified as a labeled record T , hl1 : T1, . . . ln : Tni, possibly followed by a number of invariants, definitions, and the social actions affecting their state. Instances or values v of a record type T will be represented as v = hv1, . . . , vni : T . The type Set[T ] represents a collection of values drawn from type T . The type Queue[T ] represent a queue of values v : T waiting to be processed. The value v in the expression [v| ] : Queue[T ] represents the head of the queue. The type Enumhv1, . . . , vni represents an enumeration type whose values are v1, . . . , vn. Given some value v : T , the term vl refers to the value of the field l of a record type T . Given some labels l1, l2, . . . , the expression vl1,l2,... is syntactic sugar for ((vl1 )l2 ) . . .. The special term nil will be used to represent the absence of proper value for an optional field, so that vl = nil will be true in those cases and false otherwise. The formal model will be illustrated with several examples drawn from the design of a virtual organization to aid in the management of university courses. 2.1
Social interactions shall be considered as composite connectors [
The organizational and communicative interaction types identified above clearly differ in many ways. However, we may identify four major components in all of them: the participating agents, the resources that agents manipulate, the social protocol regulating the agent activities and the sub-interaction space. Accordingly, we may specify the type I of social interactions, ranged over by the meta-variable i, as follows:
I , hstate : SI, ini : A, mem : Set[A], env : Set[R], sub : Set[I], prot : P, ch : CHi def . : (1) icontext = i1 ⇔ i ∈ is1ub inv. : (2) iini = nil ⇔ icontext = nil act. : setU p, join, leave, create, destroy, close 2In the context of this application, a one-to-one mapping between human users and software components attached to the community as agents would be a right choice.
where the member and environment fields represents the agents (A) and local resources (R) participating in the interaction; the sub-interaction field, its set of inner interactions; and the protocol field the rules that govern the interaction (P ). The event channel, to be described in the next section, allows the dispatching of local events to external interactions. The context of some interaction is defined as its super-interaction (def. 1), so that the context of the top-level interaction is nil .
The type SI , Enumhopen, closing , closed i represents the possible execution states of the interaction. Any interaction, but the top-level one, is set up within the context of another interaction by an initiator agent. The initiator is thus a mandatory feature for any interaction different to the community (inv. 2). The life-cycle of the interaction begins in the open state. Its sets of agent and resource participants, initially empty, varies as agents join and leave the interaction, and as they create and destroy resources from its local environment. Eventually, the interaction may come to an end (according to the protocol’s rules), or be explicitly closed by some agent, thus prematurely disabling the activity of its participants. The transient closing state will be described in the next section. 2.2
Components engage as agents in social interactions with the purpose of achieving something. The purpose declared by some agent when it joins an interaction shall be regarded as the institutional goal that it purports to satisfy within that context3. The types of agents participating in a given interaction are primarily identified from their purposes. For instance, students are those agents participating in a course who purport to obtain a certificate in the course’s subject. Other members of the course include lecturers and teaching assistants.
The type A of agents, ranged over by meta-variable a, is defined as follows: A , hstate : SA, player : A, purp : F, att : Queue[ACT ],
ev : Queue[E ], obl : Set[O]i def . : (3) acontext = i ⇔ a ∈ imem
(4) i ∈ apartIn ⇔ a1 ∈ imem ∧ a1player = a inv. : (5) aplayer = nil ⇔ acontext,context = nil act. : see where the purpose is represented as a well-formed boolean formula, of a generic type F , which evaluates to true if the purpose is satisfied and false otherwise. The context of some agent is defined as the interaction in which it participates (def. 3).
The type SA , Enumhplaying , leaving , succ, unsuci represents the execution state of the agent. Its life-cycle begins in the playing state when its player agent joins the interaction. Any agent who is not a member of the top-level interaction is played by another one (inv. 5)4. The derived partIn feature represents the interactions in which the agent is playing some member role (def. 4)5. An agent may play roles at interactions within or outside the scope of its context. For instance, students of a course are played by student agents belonging to the (undergraduate) degree, whereas lecturers may be played by teachers of a given department and the assistant role may be played by students of a Ph.D degree (both, the department and the Ph.D. degrees, are modelled as sub-interactions of the faculty).
Components will normally attempt to perform different social actions (e.g. to set up subinteractions) in order to satisfy their purposes within some interaction. Moreover, components needs to be aware of the current state of the interaction, so that they will also be capable of observing certain events from the interaction. Both, the visibility of the interaction and the attempts of members, are subject to the rules governing the interaction. The attempts and events fields of the agent structure represents the queues of attempts to execute some social actions (ACT ), and the events (E ) received by the agent which has not been observed yet. An agent may update its event 3Thus, it may or may not correspond to actual internal “goals” or “intentions” of the component. 4The player of a top-level agent role is actually its software component.
5Free variables in the antecedents/consequents of implications shall be understood as universally/existentially quantified. queue by seeing the state of some entity of the community. The last field of the structure represents the obligations (O) of agents, to be described later.
Eventually, the participation of some agent in the interaction will be over. This may either happen when certain conditions are met (specified by the protocol rules), or when the agent takes the explicit “decision” of leaving the interaction. In either case, the final state of the agent will be successful if its purpose was satisfied; unsuccessful otherwise. The transient leaving state will be described in the next section. 2.3
Resources are software components which may represent different types of non-autonomous informational or computational entities. For instance, objectives, topics, assignments, grades and exams are different kinds of informational resources created by lecturers and assistants in the context of the course interaction. Students may also create programs to satisfy the requirements of some assignment. Other types of computational resources put at the disposal of students by teachers include compilers and interpreters.
The type R of resources, ranged over by meta-variable r, can be specified by the following labeled record:
R , hcr : A, owners : Set[A], op : Set[OP]i def . : (6) rcontext = i ⇔ r ∈ ienv act. : take, share, give, invoke
Essentially, resources can be regarded as objects deployed in a social setting. At least, this means that resources are created, accessed and manipulated by agents in a social interaction context (def. 7), according to the rules specified by its protocol. The mandatory feature creator represents the agent who created this resource. Moreover, resources may have owners. The ownership relationship between members and resources is considered as a normative device aimed at the simplification of the protocol’s rules that govern the interaction of agents and the environment. Members may gain ownership of some resource by taking it, and grant ownership to other agents by giving or sharing their own properties. For instance, the ownership of programs may be shared by several students if the assignment can be performed by groups of two or more students.
The last operations feature represents the interface of the resource, consisting of a set of operations. A resource is structured around several public operations that participants may invoke, in accordance to the rules specified by the interaction’s protocol. The set of operations of a resource makes up its interface. Resources that own a thread of control are called active. 2.4
The protocol of some interaction is made up of the rules which govern its overall state. The present specification abstracts away the particular formalism used to specify these rules, and focuses instead in several requirements concerning the structure and interface of protocols. Accordingly, the type P of protocols, ranged over by meta-variable p, is defined as follows6:
P , hemp : A × ACT → Boolean, perm : A × ACT → Boolean, vis : A × E → Boolean, obl : A → Set[O] × Set[E ], over : A → Boolean, f inish : → Booleani def . : (7) pcontext = i ⇔ p = iprot inv. : (8) pfinish() ∧ s ∈ pcontext,sub ⇒ sprot,finish() (9) pfinish() ∧ a ∈ pcontext,mem ⇒ pover(a) (10) pover(a) ∧ aplayer = a ⇒ aicontext,prot,over(ai)
i 6Additional social actions, such as permit, forbid, empower, etc., to update the rules of protocols are yet to be identified in future work.
We demand from protocols four major kinds of functions. Firstly, protocols shall include rules to identify the empowerments and permissions of any agent attempting to alter the state of the interaction (e.g. its members, the environment, etc.) through the execution of some social action (e.g. join, create, etc.). Empowerments shall be regarded as the institutional capabilities which some agent possesses in order to satisfy its purpose. Corresponding rules, encapsulated by the empowered function field, shall allow to determine whether some agent is capable to perform a given action over the interaction7. Empowerments may only be exercised under certain circumstances – that permissions specify. Permission rules shall allow to determine whether the attempt of an empowered agent to perform some particular action is satisfied or not (cf. permitted field). For instance, the course’s protocol specifies that the agents empowered to join the interaction as students are those students of the degree who have payed the fee established for the course’s subject, and own the certificates corresponding to its prerequisite subjects. Permission rules, in turn, specifies that those students may only join the course in its admission stage. Hence, even if some student has paid the fee, the attempt to join the course will fail if the course has not entered the corresponding stage8.
Secondly, the protocol shall allow to specify monitoring rules which establishes the visibility of incoming events for each of its members. Corresponding rules shall establish whether some event must be notified to a specified agent. For instance, this functionality is exploited by teachers in order to monitor the enrollment of students to the course.
Thirdly, protocols shall allow to determine the obligations of its members. Obligations represent a normative device of social enforcement, fully compatible with the autonomy of agents, used to bias their behaviour in a certain direction. These kinds of rules shall allow to determine whether some agent must perform an action of a given type, as well as if some obligation was fulfilled, violated or needs to be revoked. The function obligations of the protocol structure thus updates the set of obligations of the specified member agent. Moreover, it returns a collection of events representing the changes in the obligation set. For instance, the course’s protocol establishes that teachers must create the course’s objectives and topics in the preparation stage.
Last, the protocol shall allow to control the state of the interaction as well as the states of its members. Corresponding rules identify the conditions under which some interaction will be automatically finished, and whether the participation of some agent in the interaction will be automatically over. Thus, the function field finish returns true if the regulated interaction must finish its execution. If so happens, a well-defined set of protocols must ensure that its sub-interactions and members are finished as well (inv. 8,9). Similarly, the function over returns true if the participation of the specified member must be over. Well-formed protocols must ensure the consistency between these functions across playing roles (inv. 10). For instance, the course’s protocol establishes that the participation of students is over when they gain ownership of the course’s certificate or the chances to get it are exhausted. It also establishes that the course must be finished when the admission stage has passed and all the students finished their participation. 3
The dynamics of the multi-agent community is influenced by the external actions executed by software components and the rules governing their interactions. This section focuses on the dynamics resulting from a particular kind of external action: the attempt of some component to execute a given (internal) social action, qua agent attached to the community. The description of other external actions concerning agents (e.g. observe the events from its event queue, enter or exit from the community) and resources (e.g. a timer resource may signal the pass of time) will be skipped.
The processing of some attempt may give raise to changes in the scope of the target interaction, such as the instantiation of new participants (agents or resources) or the setting up of new sub-interactions. These resulting events may cause further changes in the state of other interactions (the target one included), namely, in its execution state as well as in the execution state, obligations and visibility of their members. This section will also describe the way in which these 7Protocol’s functions may check the current and past state of different interactions to compute their results. 8The hasPaidFee relationship between (degree) students and subject resources is represented by an additional, application-dependent field of the agent structure for this kind of roles. Similarly, the course’s stage is an additional field of the structure for course interactions. The generic types I, A, R and P are thus extendable. events are processed. The resulting dynamics described bellow allows for social actions and events corresponding to different agents and interactions to be processed simultaneously. Due to lack of space, we only include some of the operational rules that formalise their execution semantics. An attempt is defined by the structure AT T , hperf : A, act : ACT i, where the performer represents the agent in charge of executing the specified action. This action is intended to alter the state of some target interaction (possibly, the performer’s context itself), and notify a collection of addressees of the changes resulting from a successful execution. Accordingly, the type ACT of (internal) social actions, ranged over by meta-variable α, is specified as follows: where: the performer is formally defined as the agent who stores the action in its queue of attempts; the event field represents the changes caused by a successful or unsuccessful execution of the action; and the stage field represents the current phase of processing. This process goes through four major phases, as specified by the enumeration type SACT , Enumhemp, perm, exec, dispi : empowerment checking, permission checking, action execution and addressee dispatching, described in the sequel. 3.1.1
The post-condition of an attempt consists of inserting the action in the queue of attempts of the specified performer. As rule 1 specifies, this will only be possible if the performer is empowered to execute that action according to the rules that govern the state of the target interaction. If this condition is not met, the attempt will simply be ignored. Moreover, the performer agent must be in the playing state (this pre-condition is also required for any rule concerning the processing of attempts). If these pre-conditions are satisfied the rule is fired and the processing of the action continues in the permission checking stage.
ǫ = ha, αi : AT T ∧ αtarget,prot,emp(a, α) a = hplaying , , , qACT , , i −→ǫ hplaying , , , qA′CT , , i
W here : (α′)state = perm
(qA′CT ) = push(α′, qACT ) 3.1.2
The processing of the action resumes when the possible preceding actions in the performer’s queue of attempts are fully processed and removed from the queue. Moreover, there should be no pending events to be processed in the interaction, for these events may cause the member or the interaction to be finished (as will be shortly explained in the next sub-section). If these conditions are met the permissions to execute the given action (and notify the specified addressees) are checked. If the protocol of the target interaction grants permission, the processing of the attempt moves to the action execution stage (rule 2). Otherwise, the action is discharged and removed from the queue. Unlike unempowered attempts, a forbidden one will cause an event to be generated and transfered to the event channel for further processing.
αstate = perm ∧ acontext,ch,in = ∅ ∧ αtarget,prot,perm(a, α) a = hplaying , , , [α| ], , i −→ hplaying , , , [α′| ], , i
W here : (α′)state = exec (1) (2) The transitions fired in this stage are classified according to the different types of actions to be executed. The intended effects of some actions may directly be achieved in a single step, while others will required an indirect approach and possibly several execution steps. Actions of the first kind are “constructive” ones such as set up and join. The second group of actions include those, such as close and leave, whose effects are indirectly achieved by updating the interaction protocol.
As an example of constructive action, let’s consider the execution of a set up action, whose type is defined as follows9:
, inv. : (12) αnew,mem = αnew,res = αnew,sub = ∅
(13) αnew,state = open where the new field represents the new interaction to be initiated. Its sets of participants (agents and resources) and sub-interactions must be empty (inv. 12) and its state must be open (inv. 13). The setting up of the new interaction may thus affect its protocol and possible application-dependent fields (e.g. the subject of a course interaction). According to rule 3, the outcome of the execution is threefold: firstly, the performer’s attempt queue is updated so that the executing action moves to the next addressee dispatching stage and an event is placed in its corresponding auxiliary field; secondly, the new interaction is added to the target’s set of sub-interactions (moreover, its initiator field is set to the performer agent); last, the event representing this change is inserted in the output port of the target’s event channel. (3) (4) Close ,
ACT hupd : (→ Bool) → (→ Bool)i inv. : (14) αtarget,state = open (15) αtarget,context 6= nil (16) αupd(αtarget,prot,finish)() where the inherited target field represents the interaction to be closed (which must be open and different to the top-interaction, according to invariants 14 and 15) and the new update field represents a proper higher-order function to update the target’s protocol (inv. 16). The transition which models the execution of this action, specified by rule 4, defines two effects in the target interaction: its protocol is updated and the event representing this change is inserted in its input channel. This event will actually trigger the closing process of the interaction as described in the next sub-section.
αstate = exec ∧ α : Close hplaying , , , [α| ], , i −→ hplaying , , , [α′| ], , i αtarget = hopen , , , , , p, ci −→ hopen , , , , , p′, c′i 9The resulting type consists of the fields of the labelled record ACT extended plus an additional field new. 10This strategy is also followed in the definition of leave and may also be used in the definition of other types of actions such as fire, permit, forbid, etc.
αstate = exec ∧ α : SetUp ∧ αsub = i hplaying , , , [α| ], , i −→ hplaying , , , [α′| ], , i αtarget = hopen , , , , , sI , ci −→ hopen , , , , , sI ∪ i′, c′i
Let’s consider now the case of a close action. This action represents an attempt by the performer to force some interaction to finish, thus bypassing its current protocol rules (those concerning the finish function). The way to achieve this effect is to cause an update on the protocol so that the finish function returns true afterwards10. Accordingly, we may specify this type of action as follows: disp f inish(αtarget) αupd(pfinish) insert(f inish(αtarget), cout) 3.1.4
In this last stage the specified addressees are notified of the changes caused by the action executed in the last phase (stored in the action’s ev field). Transition 5 simply iterate over the addressees field until no agent is left. Once the set is empty the action is removed from the queue and the processing of the attempt is finished.
αstate = disp ∧ a ∈ αadd hplaying , , , [α| ], , i −→ hplaying , , , [α′| ], , i a = hplaying , , , , qE , i −→ hplaying , , , , qE′ , i
W here : (α′)add qE′ = = αadd \ {a} insert(αev , qE ) (5) 3.2
Events generated in the scope of some interaction (e.g. due to the successful execution of a social action or a forbidden attempt) must first be dispatched to those interactions whose state may be affected by those changes in order to trigger the corresponding updates11. Then, each potentially affected interaction have to process the external events to check its execution state and members for possible updates. These activities are encapsulated in the event channels of interactions. Channels, ranged over by meta-variable c, are defined by two input and output ports, according to the following definition:
CH , hout : Queue[E ], disp : E → Set[I], int : Set[I],
in : Queue[E ], agents : Set[A]i inv. : (17) ccontext ∈ cdisp(f inish(ccontext)) (18) ccontext ∈ cdisp(over(a)) (19) ccontext,sub ⊆ cdisp(closing(ccontext)) (20) apartsIn ⊆ cdisp(leaving(a)) (21) ccontext ⊆ cdisp(closed(i)) (22) {ccontext, aplayer,context} ⊆ cdisp(lef t(a))
The output port of the channel is defined by the out, disp and int fields. This port stores the set of events originated within the interaction, and defines the function which determines the interactions to which these events will be dispatched. The constraints on the dispatching function will be explained bellow. The int auxiliary field represents those interactions identified by the dispatching function which have not being notified yet. The input port consists of the two last fields. It stores the incoming events dispatched to the interaction which has not been processed yet. The agents auxiliary field represents those agents whose state still needs to be checked for updates, given the current event been processed.
Accordingly, the processing of some event goes through three major stages: interaction dispatching, interaction state update and members update. The first one takes place in the interaction in which the event originated, whereas the second and third ones execute in separate control threads of the interactions to which the event was dispatched.
11Alternatively, we may have assumed that interactions are fully aware of any change in the multi-agent community. In this scenario, interactions would trigger themselves without requiring any explicit notification. On the contrary, we adhere to the more realistic assumption of limited awareness.
ccontext,state = isdtate = open ∧ id ∈ sI s cs = h[e| ], , sI , , i −→ h[e| ], , sI \ {id}, , i icdh = h , , , qi, i −→ h , , , insert(e, qi), i 3.2.2
Input port activity is triggered when a new event is received. Irrespective of the kind of incoming event, the first processing action is to check whether the channel’s interaction must be finished. Thus, the dispatching of the finish event resulting from a close action (inv. 17) serves as a trigger of the closing procedure. The kind of closing events to be described bellow is similarly used as a coordination device.
If the interaction has not to be finished, the part field is initialised to its members and the process enters the members update stage. Otherwise, we can consider two possible scenarios. In the first one, the interaction has no members and no sub-interactions. In this case, the interaction can be inmediately closed down. As rule 7 shows, the interaction is closed, removed from the context’s set of sub-interactions and a closed event is inserted in its output channel. According to invariant 21, this event is inserted in its input channel to allow for further treatment. The processing of some event stored in the output port is triggered when all its preceding events have been dispatched. As a first step, the auxiliary int field is initialised with the returned value of the dispatching function. This function shall identify the set of interactions (possibly, empty) whose state may be affected by the event12. This set may include the channel’s interaction itself. Then, additional rules simply iterate over this collection (rule 6) and re-set its value to nil when all interactions have been notified. (6) (7) (8) cin 6= ∅ ∧ cagents = nil ∧ i ∈ sI ∧ pfinish() i = h , , ∅, , ∅, p, ci −→ hclosed , , , , , , i h , , , , sI , , ci −→ h , , , , sI \ {i}, , c′i W here : (c′)out =
insert(closed(i), cout)
Eventually, every member will leave the interaction and every sub-interaction will be closed. Corresponding events will be received by the interaction (according to invariants 22 and 21) so that the conditions of the first scenario will hold.
12This is essentially determined by the protocol rules of these interactions. The way in which the dispatching function is initialised and updated is out of the scope of this paper.
In the second scenario, the interaction has some member or sub-interaction. In this case, cleanup is required prior to the disposal of the interaction. As rule 8 shows, the interaction is moved to the transient closing state and a corresponding event is inserted in the output port. According to invariant 19, the closing event will be dispatched to every sub-interaction in order to activate its closing procedure (guaranteed by invariant 8). Moreover, the agents field is initialised so that the process goes on in the next members update stage. This stage will further initiate the leaving process of the members (according to invariant 9).
cin 6= ∅ ∧ cagents = nil ∧ pfinish() ∧ (sA 6= ∅ ∨ sI 6= ∅) i = hopen , , sA, , sI , p, ci −→ hclosing , , sA, , sI , p, c′i
W here : (c′)out (c′)agents = = sA insert(closing(i), cout) The possible consequences in the overall state of members are three-fold: firstly, it may happen that the agent have to finished its participation in the interaction; secondly, the event may affect its normative state, causing the creation of some obligations or the satisfaction/violation/revoking of existing ones; last, the member may be one of those who must be notified of the given change (even if the event was the result of some action and the member was not part of the addressees).
If the member has to finish its participation in the interaction and it is not playing any role, it will be inmediately abandoned (successfully or unsuccessfully, according to the satisfaction of its purpose). The corresponding event will be forwarded to its interaction and to the interaction of its player role to account for further changes (inv. 22). Otherwise, the member enters the transient leaving state, thus preventing any action performance. Then, it waits for the completion of the leaving procedures of its played roles, triggered by proper dispatching of the leaving event (inv. 20).
If the conditions to finish its participation does not hold, the obligations and events queue will be updated accordingly. The member is removed from the agents auxiliary field and the event processing goes on with the next participant. When the agents set gets empty, the field is re-set to the nil value. 4
This paper has attempted to expose a possible semantic core underlying the wide spectrum of
interaction types between autonomous, social and situated software components. In the realm of
software architectures, this core has been formalised as an operational model of social connectors,
intended to describe both the basic structure and dynamics of multi-agent interactions, from the
largest (the agent society itself) down to the smallest ones (communicative actions). Thus,
toplevel interactions may represent the kind of agent-web pursued by large-scale initiatives such as
the Agentcities/openNet one [
The analysis of social interactions put forward in this paper draws upon current proposals of
the literature in several general respects, such as the institutional and organizational character of
multi-agent systems [
Besides the conceptual objective of analysing the structure and dynamics of multi-agent
interactions, the formal model of social interactions presented here is also aimed as a contribution
to the field of multi-agent system programming [