Distributive and Collective Readings in Group Protocols

1 Motivations

Group communication is common in collaborative applications of all kinds such as clustering, grid computing, transactions and database replication, distance learning, application sharing, distributed interactive simulations, on-line games and financial markets. In all these applications the emphasis shifts to distributed global collaboration rather then a centralized view of the problem. A protocol definition specifies how distributed elements interact with one another in order to achieve a specified behavior and therefore, protocols are critical for the interoperability of the various components. Most of the protocols presented in multi-agent systems propose bilateral interaction among agents, with few cases of protocols that try to capture cases involving groups of agents. These representations of bilateral interactions are very useful in describing isolated conversation between two agents, but fail when the structure of the conversation becomes complex or the number of agents involved within the conversation grows.

One of the most challenging examples in distributed interactions and group communication is represented by the third generation of grid computing systems [De Roure et al., 2003]. Grid computing enables geographically distributed systems to form dynamic virtual organizations [Foster et al., 2001] whose members use shared and private resources to collaborate in order to find a solution to a common problem. Given this situation, according to Jennings [Jennings, 2001], agentoriented approaches are well-suited to engineering complex, distributed software systems. In the case of distributed grid computing (i.e., when there is no single big computer for

Sanjeev Kumar and Philip R. Cohen

Oregon Health and Science University Beaverton, OR - USA {skumar, pcohen}@cse.ogi.edu

collecting results), it should be possible for each computer to send messages and results to groups of other components without knowing in advance who are the recipients and who actually need such results. In this sense, an agent communication language should support communication addressed to individuals as well as to groups, where a group may have a stable, known membership (i.e. it can be addressed by a referring name) or its membership may be unknown. For example, in a publish/subscribe system, senders label each message with the name of a topic ("publish"), rather than addressing it to specific recipients and the messaging system then sends the message to all eligible systems that have asked to receive messages on that topic ("subscribe").

But complex systems like grids not only require that collections of components be treated as a single conceptual unit when viewed from a different level of abstraction, they also involve the changing of relationships between their various components. Group communicative acts by themselves are not sufficient to model such situations. The group communication semantics of speech acts is sufficient to model oneshot one-to-many communicative interactions - the intended recipients can be multiple agents and/or groups of agents. However, we need group protocols in order to enable computational mechanisms for flexibly forming, maintaining, and disbanding organizations or teams. This is not just a matter of allowing new groups to appear and then disband, but also allowing different kinds of groups that have different types of commitments among the group members themselves. The use of communicative acts in different contexts and in different orders leads to the creation of different types of commitment among the agents. Different commitments imply different methods to form and disband teams of agents.

In this paper, starting from an attempt-based semantics of communicative acts [Cohen and Levesque, 1990] and the semantics of group communication [Kumar et al., 2000], we analyze the concept of distributive reading vs. collective reading [Clark and Carlson, 1982] in group protocols. These types of group communication will be evaluated with respect to the formation of different types of teams during interaction. In the case of a collective reading, we claim that joint commitments and mutual beliefs have to be established among all the members of the group. We will see that by means of group communication, one can obtain a joint commitment among the members of a group that has different properties from the one achieved by means of single utterances.

2 Formalism

Addressing an utterance to more than one recipient is more than a convenient way to refer to many people simultaneously. For example, it may be that we want to make other people aware of what is going on say, by using the Carbon Copy field in e-mails. Even if everybody in the "TO" and in the "CC" fields receives the e-mail, it is clear that the intended recipients of our utterance are just the people in the "TO" field, but, we also want the people in the "CC" field to be aware of it. So, the reader of an e-mail has to be able to make certain inferences about the mental state of others who the e-mail is addressed to or who will be reading the e-mail. Moreover, consider the utterance: "Can both of you help me in lifting this table?". The main effect of this utterance is not only that both the recipients are aware of the request, but also that both of them know that the request was made to all the recipients as a group and the requested action should be a joint action. An agent communication language should be able to properly convey these nuances of a requester's intentions about the performers of an action.

In a previous paper [Kumar et al., 2000], we introduced a framework for semantics of group communicative acts and provided a semantics of the REQUEST communicative act within this framework. It was demonstrated that this group communicative act can be performed even when the requester does not know about the intended actor and when the requester does not know everyone who will get the message. Even though that paper emphasized the importance of distinguishing between a group doing an action as an entity (collective reading) and everybody in a list of individuals performing the action (distributive reading), it provided a clear semantics only for the latter. Furthermore, plurals and utterances addressed to groups can introduce semantic ambiguities. For example, there can be a potential ambiguity as to whether the aggregated entities are to act individually (distributive) or they are to act together as one (collective). This paper makes a clear distinction in the semantics of communicative acts to enable understanding whether an utterance requires a collective or a distributive reading. In particular, we want the agents that receive a communicative act to interpret its correct reading (distributive or collective) so that they can act accordingly. Moreover, group communicative acts have to be inserted and analyzed in the wider context of protocols, where distributive and collective reading of an utterance is important in order to generate the next communicative act of the protocol. However, in this paper we will not be concerned with how the action is done and how the agents coordinate in order to perform the action.

We regard a group as being defined by a characteristic function such as the membership property. This can be captured by a predicate consisting of a free variable that ranges over individuals. With Greek letters we will represent groups' names, and we use the same symbol in a functional notation to denote the associated membership predicate. For example, γ is a group having the membership predicate γ(x) where x is a free variable. We will underline the entities that represent groups (γ, for example) to indicate the distributive readings of that group. An entity without an underline can be either an individual or a group and indicates a collective reading. If ψ is a formula with term γ, and x does not appear in ψ, and γ(x) is the property predicate that corresponds to γ, and ψ(x) is a formula formed by replacing γ with x in ψ, then ψ(γ) = ∀x γ(x) ⊃ ψ(x). For example: (BEL γ p) = ∀x γ(x) ⊃ (BEL x p). In other words, everyone in group γ believes p. In case of ambiguity in the determination of the scope, we will mark the group term that it applies to and the starting bracket with the free variable in the superscript. (y BEL γ y (BEL x (z BEL γ z p))) = ∀y γ(y) ⊃ (BEL y (BEL x (∀z γ(z) ⊃ (BEL z p)))).

This paper will concentrate on group protocols in which the intended recipient of a message is a group of (possibly unknown) agents. The difference between a distributive reading and collective reading will be shown to depend upon whether the intended actors are separate individuals or groups. Here, we summarize the results from literature that this paper builds upon and redefine semantics for the communicative acts that we need for our example. The terms α, β, and γ in the following definitions can represent either groups or individuals. Here, α is the entity performing the communicative act, β is the recipient (including the "Over-hearers") of the message, and γ is the intended recipient (or intended actor). The semantics of the communicative acts as described below has the implicit requirement that the intended recipients of an utterance are a subset of all the recipients. Moreover, the sender of the utterance is always a single agent that may be an individual that acts on behalf of the group. The analysis of authorized representative of groups is left for future work.

A persistent weak achievement goal or PWAG represents the one-way commitment of one agent directed towards another and it is used to define the semantics of various communicative acts. A PWAG made public via performance of a communicative act represents a social commitment using mentalist notions. The definition of (PWAG α γ p q) states that an entity α has a PWAG towards another entity γ to achieve p with respect to q when the following holds: if α believes that p is not currently true then it will have a persistent goal to achieve p, and if it believes p to be either true, or to be impossible, or if it believes the relativizing condition q to be false, then it will have a persistent goal to bring about the corresponding mutual belief with γ. In the philosophy of language, it is argued that the illocutionary effect of a speech act consists of the hearers recognition of the speakers communicative intention. A communicative act succeeds when the hearer successfully recognizes the speakers intention and it is satisfied when the hearer successfully acts on the speakers intention. Communicative acts must be characterized as attempts because there is a possibility that the act may not succeed. Accordingly, attempt is defined as having a goal and an intention. An ATTEMPT to achieve p via q represented as (ATTEMPT γ e p q t) is a complex action expression in which the entity γ is the actor of the event e and just prior to e, the actor chooses that p should eventually became true, and intends that e should produce at least q relative to that choice. Mutual belief for groups is defined in terms of unilateral mutual belief, or BMB [Cohen and Levesque, 1990], that is treated as a semantic primitive [Kumar et al., 2000].

Definition 2.1 Mutual Belief

MB between two groups (MB β γ) is defined similarly. In this article, we assume that mutual belief is established by default. Establishing mutual belief by default means that agents make certain defeasible assumptions if they have no information to the contrary. If at a later time, the agent having a defeasible belief discovers that its belief was incorrect than it needs to revise that belief 1 . But until that happens, an agent can assume the defeasible belief and make inferences based on that belief. The symbol ⊢d represents the deduction relation and ⊢d (ϕ ⇒ ψ) denotes that ψ can always be derived from ϕ using defeasible rules. In particular, we assume that the sender and the receivers of a communicative act use the same defeasible rules, like, for example, that i) the speaker does not change its mental state about the propositional content of the communicative act immediately after performing it; ii) the sender of a communicative act is sincere toward the recipients about its (i.e. sender's) mental attitude; iii) if a communicative act has been done successfully then the sender and the hearer mutually believe that it has been done [Kumar et al., 2002]. This enables us to define the other communicative acts that we require for our example.

Definition 2.2 Request

(REQUESTα β γ e a q t) ≡ (ATTEMPT α e φ ψ t) where φ = (zDONE γ z a)∧

The goal of the REQUEST is that the intended actor eventually does the action a and also has a PWAG with respect to the requester to do a. The intention of the REQUEST is that all the recipient β believe there is a mutual belief between the recipient and the requester that the requester α had a goal that he (the requester) will have a PWAG with respect to the intended actor γ about the goal φ of the REQUEST 2 . It was shown in [Kumar et al., 2000] that the recipient β and the intended actor γ never quantify into the beliefs of the requester α - meaning thereby that the requester a does not need to know who β and γ are. It was also shown how to construct a model in which a request can be performed even when the requester does not know the recipients as well as the intended actors of the request. Therefore, unlike the previous definitions in agent communication languages literature, this definition of REQUEST allows for the broadcasting of a request.

Theorem 2.1 Successful performance of the REQUEST communicative act establishes a mutual belief by default between the requester α and the intended recipient γ, about the requester's PWAG toward the intended recipient γ for doing the requested action. Formally,

(xMB γ x α (y PWAG α γ y φ q)) where, φ = (DONE γ a)∧ [PWAG γ α (DONE γ a)(PWAG α γ (DONE γ a) q)]

1 We do not discuss belief revision in this paper.

2 In accordance with the first defeasible rule, we have simplified the temporal aspects of communicative act definitions.

Proof Sketch. γ is a subset of β, so the intention part of the definition of the REQUEST speech act is also valid by substituting β with γ. After making these substitutions, the proof is the same as the one provided in [Kumar et al., 2002].

Definition 2.3 Inform

(INFORMα β γ e p t) ≡ (ATTEMPT α e φ ψ t) where φ = [BMB γ α p] and ψ = [BMB β α [GOAL α (BEL γ [BEL α p])]]

The goal of an INFORM is that the intended recipients γ come to believe that there is mutual belief between γ and the senders α that the proposition p is true. The intention of the INFORM is that the recipients (including the over-hearers) come to believe that there is mutual belief between the recipients and the senders that the senders had the goal that the intended recipients will believe that the senders belief p.

Theorem 2.2 Successful performance of the INFORM communicative act establishes a mutual belief by default between the sender α and the intended recipient γ, that the sender believes the informed proposition. Formally, ⊢d (DONE(INFORMαβ γ e p t)) ⇒ (MBαγ (BELαp))

Proof Sketch. Again, by substituting β with γ the proof of the theorem is the same as in [Kumar et al., 2002].

Starting from the definition of INFORM and REQUEST, we can define some other communicative acts, modifying the definitions in [Kumar et al., 2002]. One has to replace the sender x and the recipients y appropriately by the sender α, the recipients β, and the intended actors γ.

Definition 2.4 Agree

The agreeing entities α inform the intended recipients γ that they have a PWAG with respect to γ to perform action a with respect to γ's PWAG that α do a relative to q.

Definition 2.5 Refuse

The refusing entities α inform the intended recipients γ that they will never have the PWAG to perform action a with respect to γ's PWAG that α do a relative to q. As in the individual case, the effect of a REFUSE is opposite to that of the AGREE.

In the next section, we discuss how these group communicative acts fit together in a group protocol that is described using the Joint Intention Theory [Kumar et al., 2002]. In particular, we will see how to obtain the collective and distributive reading cases just by addressing the utterances to groups instead of single agents.

3 An Example: The Request for Action Protocol

For simplicity of exposition, let us consider the Request for Action protocol that establishes joint commitment(s) between the requester(s) and the requestee(s) to get an action done. One of the objectives of this protocol is to create a joint commitment (JPG) among the requester α and the group γ for doing a specific action a. The discussion that follows applies equally well to other protocols (such as Contract-Net) that use communicative acts to create and discharge joint commitments. The simplest (and the most well-studied) case involves an individual REQUEST from one agent to another who then responds with either an AGREE or a REFUSE. It has been established in multi-agent literature that this sequence of communicative actions is sufficient to establish a joint commitment between the two agents for doing the requested action. The resulting joint commitment constrains the mental state and future behavior of both agents such that they work cooperatively as a team that is robust to a wide range of failures. However, this simple one-to-one request/accept protocol is insufficient for many real life scenarios that involve joint commitment not only between two individuals but between and among individuals and groups that may possibly be unknown at the start of the protocol. Furthermore, there may be over-hearers in any group communication that may affect the team creation process.

Even ignoring the effects of over-hearers, there are at least four different cases of team formation when the request for action protocol is generalized to account for group communication as listed in the above table (see Fig. 1). In the first case (a), individual requests are sent to multiple entities (that may be groups or individuals) for doing the same task. The requester has to know all the agents to whom it wants to request. Some of the recipients of that request may agree to the request, some may reject the request, and others may not respond at all. As a result of this communication, the requester forms pair-wise joint commitment with every entity that responded with an AGREE. The second case (b) is similar in that it also results in pair-wise joint commitments between the requester and each entity that agreed. However, it achieves the same effect by using a single group REQUEST that does not require a requester to be aware of the intended recipients of the request. This is very common in broadcast communications, for example, consider a request for helping with a programming task that has been posted on a notice board. Both the above two cases can be used to create competing teams, and this is not restricted to the request protocol. For example, consider a call for proposal from a funding agency for a competitive project where multiple contracts are awarded to different universities - each university has a pair-wise joint commitment with the funding agency for doing the research but at the same time they compete with each other to produce the best results for ongoing funding.

In the third case (c), the requester sends a collective REQUEST to a group which then replies collectively to that request. It is essentially communication from one entity (individual or group) to a group treated and addressed as an entity (such as an organization). An interesting aspect of this communication is to what extent the members of the requested organization are jointly committed towards the requester for doing the requested task. We speculate that this has to do with how that group was created in the first place. For example, if the bylaws in the articles of incorporation of that group require that the group makes its decisions by a majority vote but once a decision has been made then all group members are committed to that decision then it may very well be the case that each member of that organization is individually committed to seeing the success of the joint commitment.

In this case, we have collective commitment among the members of the group. This kind of commitment is the same that we can achieve in the last case (d), where a requester sends a REQUEST to a number of agents treated as a group and they reply individually with an AGREE addressed to the group. The main difference between the cases c and d is that while in the first case the message is addressed to an existing group (i.e., it has rules for team creation decision even if we are not aware of and we do not now who are the members of the group), in the last case the collective REQUEST followed by individual replies addressed to the group has the effect that the members of the group are bound together by their commitment and so a team is formed (we have a collaboration).

In the next sections, we will analyze two of the above cases. In particular, we will discuss the case b for distributive commitment (Sec. 3.1) and the case d for collaborative commitment (Sec. 3.2). Notice that protocols may also require that teams be disbanded (i.e., they have to discharge their commitment) after the achievement of the goal. The complete study of the protocol is left for future work.

3.1 Distributive Reading of Request Protocol

The first step of the Request protocol consists of a REQUEST sent from α to the group γ that establishes a MB about α's PWAG towards each member of γ in a distributive way: (REQUESTα β γ e a q t). In this case the sender α may not be aware of who are the members of γ, as in the case of posting a message on a advice board or, in the case of Grids, the agents may not be aware of who are the other agents connected to the grid. Notice that in this case, the intended actor of this communicative act is a single (possibly unknown) agent x.

A subset of the participants that we represent by the group γagree may agree to do the requested action and another subset of the participants represented by the group γrefuse may refuse to the requested action. ∀x γagree(x) ⊃ (DONE(AGREE x β α e a ψ q t)), and ∀x γrefuse(x) ⊃ (DONE(REFUSE x β α e a ψ q t)). In this case the communication is overheard by all the members of β. If we want private agreements, then we have: ∀x γagree(x) ⊃ (DONE(AGREE x α α e a ψ q t)). For example, if we want to design an auction protocol, the first method (with public communication) describes in a better way what happens during the protocol. Note that with the semantics of the FIPA

speech acts, it is not possible to model the same effects. In fact during an auction, all members of the group have to overhear all other bids in order to bid again.

The group property for the group γagree specifies the agents who chose to agree from a rational choice between agreeing and refusal. The group γagree is specified by noting that it consists of those agents who performed an AGREE within the specified timeout period after the original request was performed. In either case, the group predicate is evaluated retrospectively i.e. by looking backwards from a future point in time to determine which agents 'agreed'. We will specify γagree using the predicate γagree(x) which is true if there exist events e′ and e1 such that the event sequence e; e′ ; e1 was done earlier where e is the original REQUEST event and e1 is an AGREE event performed by x.

Similarly, the group property for γrefuse specifies the agents who refused within the specified timeout period after the original REQUEST was performed.

According to these definitions of group predicates, an agent executing this protocol may not know all the agents who agree and all the agents who refuse until the deadline is reached, that is, when this protocol ends. In fact, the groups γagree and γrefuse are dynamic groups because evaluating the respective group predicates at any time before the deadline gives only those agents that have agreed or refused up to that time. Until the deadline is reached, the membership of these groups increases whenever an agent performs an AGREE or a REFUSE communicative act.

The goal associated with the protocol is to form teams for doing an action a relative to some condition q. In other words, the goal is to establish pair-wise joint commitments between the initiator α and whoever agreed (i.e. every agent x who belongs to the group γagree) that x does the action a relative to the initiator's original PWAG. The existence of a JPG between two agents is a sufficient condition for the formation of a team with respect to that JPG [Levesque et al., 1990]. Mutual beliefs in each other's PWAG toward the other to achieve a goal p is sufficient to establish a joint commitment to achieve p provided that there is a mutual belief that p has not already been achieved, and the PWAGs are interlocking (i.e., one PWAG is relative to the other) [Kumar et al., 2002].

Theorem 3.1 ⊢d (DONE (REQUEST α β γ e a q t);

Proof Sketch. Using the definitions of the group communicative acts REQUEST and AGREE (definitions 2.2 and 2.4) and applying Theorems 2.2 and 2.1 under the assumptions of mutual belief between about each other's sincerity and the reliability of the communication channel, we establish that there is a mutual belief in each other's PWAG: (xMB γ x α (y PWAG α γ y (DONE γ a)))∧ ∀z γagree(z) ⊃ (MB z α (PWAG z α (DONE z a))).

In distributive reading, the effect of multiple single utterances is the same as that of making group utterances. Notice that here we are just considering the effects of group communication on the intended actors and not on the overhearers.

We will see in the next section that when we are dealing with collective reading, the effects of group communication are different from the one obtained with the above utterances.

3.2 Collective Reading of Request Protocol

In the case of collective reading, we need JPG and MB to be established among all the members of the group. It may be possible to achieve this with the exchange of pair-wise communicative acts resulting in O(n2 ) messages. On the other hand, with messages addressed to groups via broadcast communication we would have just O(n) messages. Using the definition of group speech acts, it can be shown that the MB among the group is achieved. Notice that a collective request is more than sending individual requests to all the members of the group, i.e. a collective request implies mutual belief in the group that the intended actor of the request is the whole group, and so the action should be a joint action for the group. We claim that one cannot obtain a similar affect by just sending individual requests to the members.

In the case of collective reading, the team that is formed using group communication has different properties from the one discussed earlier. These different properties result from how the team is created. Note that one can also talk about groups in the case of distributive reading but in that case the requester and the agents who agree have pair-wise joint commitment (see Fig. 2 case a). However, in the case of a collective reading of the Request protocol, the following property holds in order to establish (JPG γ (DONE γ a)) for the group γ: ∀x γ(x) ⊃ (MB γ (PWAG x γ p)) ∧ (MB γ (PWAG γ x p)) where there is explicitly stated that the member of the team γ has beliefs about the others agents or about the team as an entity. This demonstrates that in the case of a collective reading, the effects of multiple single utterances are different from group utterances.

So in the case of collective REQUEST, the REQUEST is addressed to a group and not to a single agent: (REQUEST α β γ e a q t). Then, each member of the group will send an AGREE (or a REFUSE) to α plus the group itself (i.e., γagree+α): ∀x γagree(x) ⊃ (AGREE x β γagree+α e a ψ q t). Also, in this case each member of the group γagree may be not aware of who are the other members.

Theorem 3.2 Successful performance of a REQUEST addressed to the group for collective reading, followed by AGREEs addressed to the requester and the group establishes a JPG by default among the members of the agree group and the requester. Formally,

⊢d (DONE (REQUEST α β γ e a q t);

Proof Sketch. First, consider agent α who sends a REQUEST to γ as a group. Successful performance of the REQUEST communicative act establishes a mutual belief by default between α and γ about α's PWAG towards γ for doing the requested action: (xMB α γ x (y PWAG α γ y (yDONE γ y a) q))). Then, the agents in γagree reply with a AGREE to the group γagree+α. From the definition of the AGREE communicative act and Theorem 2.2 we have that successful performance of the AGREE communicative act establishes a mutual belief by default between α and γagree about γagree's PWAG toward α (i.e., ∀x γagree(x) ⊃ (MB x γagree+α (PWAG x γagree+α (DONE γagree a) q)) ≡ ∀x γagree(x) ⊃ (yMB γ y agree+α (PWAG x γagree+α (DONE γagree a) q)) ≡ (yMB γ y agree+α (xPWAG γ x agree α (DONE γagree a) q))). Using the definitions of the group communicative acts and the assumptions of mutual belief about each other's sincerity and the reliability of the communication channel, we establish that there is a mutual belief in each other's PWAG. Thereafter, the property for JPG for a collaborative reading is satisfied. We note that the key difference between a collective reading and distributive reading lies in the AGREEs sent to both the requester and the other agents as a group. What we argue is that one cannot achieve the same results sending individual utterances.

Theorem 3.3 Successful performance of a REQUEST addressed to each individual in the group, followed by an AGREE to each individual in the group establishes a JPG by default among the members of the AGREE group but does not constitute a collective reading. Formally,

Proof Sketch. In order to show this is not a theorem, we provide a counterexample. Consider three agents (namely the requester a, and b, c ∈ γ) in group γ. After the REQUEST communicative act has been performed, we have that ∀x γ(x) ⊃ (MB α x (PWAG α x p q)). So, for example, in this case we don't have that (MB a b (PWAG a c p q)) holds, because the REQUEST is addressed to individuals and b cannot see the message addressed to c.

4 Discussion

Group communication is common in collaborative applications of all kind. There are a variety of distributed applications that provides group communication. An infrastructure supporting group communication can be based on many different approaches and technologies, whose features vary significantly. Some of them rely on message passing systems and are implemented as webs of point-to-point links or through multicast IP. Another common approach for dealing with group communication is based on distributed event systems or message queue-based infrastructure for publish/subscribe systems. Publish/subscribe is a pattern often used in systems for human-to-human interaction, for example, bulletin boards, newsgroups and their more recent Internet incarnations such as blogs, group-chat rooms, and so on. While their technical characteristic vary among each other, they share the same objective of allowing direct conversations among any partners while simultaneously making exchanged message visible to a large number of destinations, normally unknown to the conversing parties. In whatever way group communication systems are implemented, what it is missing is a clear semantics for the communication. In this paper we have shown that by using group communicative acts in the context of group protocols we can obtain two different types of commitments among group members. In particular, just the fact that an agent addresses an utterance to the whole group instead of to each single member of the group may imply different properties for the group itself. In the future we would like to expand our work by reasoning about the effects that group communicative acts my have on the other recipients, for example overhearers, and their role in the behavior of the group.