Interagents offer the coordination level required by agents to
cooperate in non-trivial ways. An interagent allows
interdependencies between agents' communicative acts to be ordered.
These interdependencies can be defined declaratively inside each
interagent by means of a *conversation protocol*. A
conversation protocol represents the conventions adopted by agents
when interacting through the exchange of messages. A conversation
protocol can also be seen as a an agent's plan to achieve some
goal[6]. We model
and implement conversation protocols as a special type of pushdown
automaton. Pushdown automata, unlike finite state machines,
allow context to be stored and to be subsequently retrieved for an ongoing
conversation.

Conceptually, we have decomposed a conversation protocol into (see Figure 2):

**Figure:** Conversation protocol for the
foreign evaluation capability of *Plural*
[12]. The
conversation protocol followed by *Plural* agents during a
foreign evaluation is modelled and implemented in an
interagent as a pushdown automaton such that: . Messages followed by / stand for
performatives sent by the interagent's user, whilst
messages preceded by / stand for performatives received by the
interagent's user.

- A finite state control. Each state in the finite state control represents the situation of the interagent's user during an ongoing conversation.
- An input list continuously traversed in search of a performative which can produce a transition in the finite state control. If such message is found, it is dispatched and, thereby, removed from the input list. Note that the way of traversing the input list differs from the one employed by classic pushdown automata whose read only input tapes is traversed from left to right (or the other way around).
- A pushdown list where the context of an specific conversation can be stored and subsequently retrieved.
- A finite set of transitions. Each transition in a
conversation protocol indicates:
- what message has to be either sent or received to produce a move in the finite state control; and
- whether it is necessary to store (push) or retrieve (pop) the context using the pushdown list.

Formally, a conversation protocol, like a pushdown automaton [4], is a 7-tuple :

where

- is a finite set of state symbols that represent the states of the finite state control;
- is the finite input list alphabet composed of all possible performatives that an interagent can deal with;
- is the finite pushdown list alphabet composed of all possible performatives that an interagent can store;
- is a mapping from to the finite subsets of which indicates all possible transitions that can take place during a conversation.
- is the initial state of a conversation.
- is the start symbol of the pushdown list.
- is the set of final states representing possible final states of a conversation.

Messages queued by *interagents* can queue-jump only if
they produce a transition in the conversation protocol. Therefore,
in certain way interagents constrain what an agent
can utter and hear, and when. For instance, Figure 2
shows instantiation *c-87* of a conversation held by agents
*A* and *B*. The following transition:

indicates in such conversation protocol that when:

- such conversation is in state ; and
- the performative corresponding to the topmost message on the pushdown list is ; and
- a message with the performative is in
the input list, and its sender, receiver and the label in keyword
**:in-reply-to**match respectively the receiver, sender and label in keyword**:reply-with**of the topmost message on the pushdown list.

then the following move

takes place in the finite state control. As a result, conversation
*c-87* switches to state , the corresponding message
is extracted from
the input list and forwarded to the corresponding addressee, and the
message on the top of the pushdown list is popped out.

Wed Sep 9 13:33:33 MET DST 1998