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.
The suitability of agent-based computing to manage the complex patterns of interactions naturally occurring in the development of large scale, open systems, has become one of its major assets over the last few years [27,28]. Particularly, the organizational or social stance advocated in various degrees by most multi-agent system (MAS) methodologies, provides an excellent basis to deal with the complexity and dynamism of the interactions among system components [28]. This approach has resulted in a wide spectrum of organizational and communicative abstractions, such as institutions, organizations, groups, communicative interactions, etc., to effectively model the interaction space of MAS [11,13,26,28].
Still, software engineering has witnessed an increasing attention to component interactions from different research fields: coordination models and languages [7], and software architectures [1], amongst others, offer alternative analysis at different levels of abstractions. From an architectural perspective, for instance, component interactions are explicated in terms of software connectors: explicit semantic entities characterized in terms of the participant roles and protocol regulating the interaction. Component & Connector architectural styles, such as Pipe& Filter, Peer-to-Peer, or Client-Server, define different types of connectors and computational models in general.
The main hypothesis motivating this work is that the variety of organizational and communicative abstractions found in the current literature share a common semantic core. This paper attempts to elucidate this common core from an architectural point of view. Particularly, a connector-based semantics of social interactions among autonomous and situated agents is put forward, which attempts to identify the essential structure and dynamics underlying multi-agent interactions.
The paper is structured as follows: first, the major entities and relationships which constitute the structure of social interactions is introduced. Next, the dynamics of social interactions will show how these entities and relationships evolve. The model will be formalised using Structural Operational Semantics [23]. Then, the third section attempts to test the productivity of the proposed semantics by analyzing common organizational and communicative abstractions of MAS. Last, relevant work in the literature is discussed with respect to the proposal, limitations are addressed, and current and future work is described.
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 [1]. The analysis of social interactions introduced in this section refines this generic model in several respects, attending to the common features of software agents. Firstly, in accordance with the autonomy and sociality of agents, the specification of social interaction protocols will rely in normative concepts such as permissions, obligations and empowerments. Secondly, by considering situatedness, social interactions will take place in an environment consisting of resources which the participants create and manipulate. Unlike agents, resources are software components lacking autonomy, so that their state may be externally controlled by agents or other resources. Besides interactions, resources, agents and protocols, two other kinds of entities are of major relevance in our analysis: social actions, which represent the way in which agents alter the environmental and social state of the interaction; and events, which represent the changes in the social interaction resulting from the performance of social actions or the activity of the environmental resources.
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 l 1 : T 1 , . . . l n : T n , 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 = v 1 , . . . , v n : 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 Enum v 1 , . . . , v n represents an enumeration type whose values are v 1 , . . . , v n . Given some value v : T , the term v l refers to the value of the field l of a record type T . Given some labels l 1 , l 2 , . . . , the expression v l1,l2,... is syntactic sugar for ((v l1 ) l2 ) . . .. The special term nil will be used to represent the absence of proper value for an optional field, so that v l = 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.
Social interactions shall be considered as composite connectors [20], structured in terms of a tree of nested sub-interactions. Let's consider an interaction representing a university course (e.g. on data structures). On the one hand, this interaction is actually a complex one, made up of lower-level interactions. For instance, within the scope of the course agents will participate in programming assignment groups, lectures, tutoring meetings, examinations and so on. Assignment groups, in turn, may hold a number of assignment submissions and test requests interactions. A test request may also be regarded as a complex interaction, ultimately decomposed in the atomic, or bottomlevel interactions represented by communicative actions (CAs) (e.g. request, agree, refuse, . . . ). On the other hand, courses are run within the scope of a particular degree (e.g. computer science), a higher-level interaction. Traversing upwards from a degree to its ancestors, we find its faculty, the university and, finally, the multi-agent community or agent society. The community is thus the top-level interaction which subsumes any other kind of multi-agent interaction 2 .
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: 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 S I Enum open, closing , closed 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.
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: 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 S A Enum playing , leaving, succ, unsuc 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 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.
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:
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.
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 follows 6 :
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 interaction 7 . 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 stage 8 .
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.
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 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 perf : A, act : ACT , 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:
ACT state : SACT , target : I, ev : E , add :
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 S ACT Enum emp, perm, exec, disp : empowerment checking, permission checking, action execution and addressee dispatching, described in the sequel.
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. ǫ = a, α : AT T ∧ α target,prot,emp (a, α) a = playing , , , q ACT , ,
W here : (α ′ ) state = perm (q ′ ACT ) = push(α ′ , q ACT )
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.
W here : (α ′ ) state = exec
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 follows 9 :
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.
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 afterwards 10 . Accordingly, we may specify this type of action as follows:
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. , , , , p, c −→ open, , , , , p ′ , c ′ (4) 9 The resulting type consists of the fields of the labelled record ACT extended plus an additional field new.
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.
W here
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 updates 11 . 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:
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.
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 event 12 . 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.
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.
W here : (c ′ ) out = insert(closed(i), c out )
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).
W here : (c ′ ) out = insert(closing(i), c out ) (c ′ ) agents = s A 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.
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.
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 [12]. Large-scale interactions, modelling complex aggregates of agent interactions such as those represented by e-institutions or virtual organizations [2,28], are also amenable to be conceptualised as particular kinds of first-levels inner social interactions. The last levels of the interaction tree may represent small-scale multi-agent interactions such as those represented by interaction protocols [15], dialogue games [19], or scenes [2]. Finally, bottom-level interactions may represent communicative actions. From this perspective, the member types of a CA include the speaker and possibly many listeners. The purpose of the speaker coincides with the illocutionary purpose of the CA [24], whereas the purpose of any listener is to declare that it (actually, the software component) successfully processed the meaning of the CA.
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 [9,11,14,28] and the normative perspective on multi-agent protocols [16,25]. These proposals as well as others focusing in relevant abstractions such as power relationships [4], trust and reputation mechanisms in organizational settings [17], etc., could be further exploited in order to characterize more accurately the organizational character of some multi-agent interactions. Similarly, the informal and preliminary analysis of communicative actions introduced in the last section may similarly benefit from public semantics of communicative actions such as the one introduced in [3]. Last, the abstract model of protocols may be refined taking into account existing operational models of normativity [8,16]. These analyses shall result in new organizational and communicative abstractions obtained through a refinement and/or extension of the general model of social interactions.
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 [5]. Unlike the development of individual agents, which has greatly benefited from the design of several agent programming languages, non-individual features of multi-agent systems (i.e. those conforming the multi-agent organization or institution [9,11,28]) are mostly implemented through development platforms and infrastructures that must be programmed in a low-level language such as Java [18] or in terms of visual modelling [10,21]. We argue that the current field of multi-agent system programming may greatly benefit from multi-agent programming languages that incorporate as programming constructs the abstractions that have found currency in current organizational methodologies. The model of social interactions put forward in this paper is intended as the execution semantics or the abstract machine of a language of this type. This abstract machine would be independent of particular agent architectures and languages (i.e. the software components may be programmed in a BDI language such as Jason [6] or in a non-agent oriented language). On top of this execution semantics, current and future work aims at the specification of the type system [22] which allows to program the abstract machine, the specification of the corresponding surface syntaxes (both textual and visual) and the design and implementation of a virtual machine over existing middleware technologies such as FIPA platforms and Web services. We also plan to study particular refinements and limitations to the proposed model, particularly with respect to the dispatching of events, the dynamic updates of protocols and rule formalism. In this later aspect, we plan to investigate the use of Answer Set Programming to specify the rules of protocols, attending to the role that incompleteness (rules may only specify either necessary or sufficient conditions, for instance), explicit negation (e.g. on prohibitions) and defaults play in this application domain.