=Paper=
{{Paper
|id=Vol-494/paper-27
|storemode=property
|title=Detecting Exceptions in Commitment Protocols: Discovering Hidden States
|pdfUrl=https://ceur-ws.org/Vol-494/ladspaper1.pdf
|volume=Vol-494
|dblpUrl=https://dblp.org/rec/conf/mallow/KafaliY09
}}
==Detecting Exceptions in Commitment Protocols: Discovering Hidden States==
https://ceur-ws.org/Vol-494/ladspaper1.pdf
Detecting Exceptions in Commitment Protocols:
Discovering Hidden States
Özgür Kafalı Pınar Yolum
Department of Computer Engineering Department of Computer Engineering
Boğaziçi University Boğaziçi University
TR-34342, Bebek, İstanbul, Turkey TR-34342, Bebek, İstanbul, Turkey
e-mail: ozgurkafali@gmail.com e-mail: pinar.yolum@boun.edu.tr
Abstract—Open multiagent systems consist of autonomous correctly, then it is a forward step in the recovery process,
agents that are built by different vendors. In principle, open because the agent facing the exception has a means of proof
multiagent systems cannot provide any guarantees about the for the cause of it. This proof can then be used to consult
behaviors of their agents. This means that when agents are
working together, such as carrying out a business protocol, other authorities, which can resolve inconsistencies between
one agent’s misbehavior may potentially create an exception for parties.
another agent and obstruct its proper working. Faced with such Realistic business affairs consist of multiple parties that
an exception, an agent should be able to identify the problem by
carry out different tasks. Multiparty interactions have two
verifying the compliance of other agents.
Previous work on verification of protocols unrealistically inherent properties; (1) interactions between different parties
assume that participants have full knowledge of a protocol. are regulated by different contracts (i.e., a seller may exercise
However, when multiple agents enact a protocol, each agent different rules when dealing with an individual versus a cor-
has access to its part of the protocol and not more. This will poration), (2) rules of interaction between different parties are
require agents to check verification by querying others and private and not revealed to the outside world (i.e., a contract
more importantly by discovering the contracts between them.
Here, we propose a commitment-based framework for detecting between a seller and a carrier may never be revealed to buyers
exceptions in which an agent augments its part of the protocol publicly). While these properties are essential for multiparty
with its knowledge to construct states that are previously hidden protocols, they pose important challenges for verification,
to the agent by generating possible commitments between other which brings the question of how an agent can verify others’
agents. The agent then queries others to confirm those states. compliance when it has only partial information about their
Our framework is formalized using C+ and is tested using a
realistic business scenario. activities. We use the scenario in Example 1 throughout the
paper as our running example.
I. I NTRODUCTION
Example 1. Consider the simple purchase-and-delivery proto-
In open multiagent systems, it is possible for agents to col that includes three business roles. The roles in the protocol
interact with others that they have no previous knowledge of. are customer, bookstore, and deliverer. In a normal execution,
Carrying out interactions, such as business dealings, with such the customer buys a book from the bookstore and the deliverer
others is difficult since there is no guarantee about how the delivers the book to the customer. However, certain exceptions
other agents will act. If others do not follow their parts of may occur during the enactment of this protocol. For example,
the interactions, the entire business may be jeopardized. This consider the case where the customer pays for the book and
requires an agent participating in such a situation to be able expects delivery in three days. In addition, suppose that the
to verify that others are acting by the rules. bookstore sends books to be delivered to the deliverer in large
Verification is especially important in the face of exceptions. groups. If at the time the customer buys the book, the number
Here, we deal with high-level exceptions that pertain to of books pending for delivery at the bookstore is not enough,
the workings of the underlying protocol. For example, if a the book will not be delivered causing an exception for the
buyer does not receive a merchandise that was scheduled customer. However, since the customer does not know the
for delivery, it can conclude that there must have been an details of the contract between the bookstore and the deliverer,
exception in the workings of the entire protocol. When such the source of the exception is not immediately clear to the
an exception occurs, the agent facing the exception needs to customer. One option for the customer is to simply ask the
identify the problem behind it. This is a two-phase procedure; bookstore about the cause of exception. However, this may not
first detecting the exception, and then taking proper action be possible in some situations (i.e., the bookstore is not willing
recover from the exceptional situation. In this paper, we focus to share information regarding its contracts with other parties,
on the first phase. That is, we propose an algorithm for finding or the exception is caused by a party beyond the knowledge of
the source of exceptions (i.e., caused by which parties and the bookstore). Then, the customer has to use its knowledge
why). In addition, if the source of the exception is identified first to predict possible causes, and query corresponding agents
to determine which one is the actual cause of the exception. (2) A′ ⊆ A, (3) C′ ⊆ C, (4) R′ ⊆ R, (5)
∀s′ ∈ SI′ , ∃s ∈ SI : s′ ⊆ s, (6) ∀s′ ∈ SF
′
, ∃s ∈ SF : s′ ⊆ s.
In order to study verification rigorously, we capture agents’
interactions through commitments [1], and adopt C+ as a B. Commitments
language to formalize those interactions [2], [3]. In contrast to Commitments are formed between two agents and roughly
previous work on verification, we propose a realistic exception correspond to obligations [1]. The debtor of a commitment
discovery framework in which; (1) multiple roles exist in is the agent that is committed to bring about a condition.
the business, (2) business scenarios are distributed (each role The creditor benefits from the commitment. Commitments are
has its own view of the protocol), and (3) each agent deals created and discharged by the interactions of the agents. There
with an exception by discovering contracts of other agents. are two types of commitments:
With this proposed approach, an agent only finds out the c(x, y, p): This is a base-level commitment between debtor
necessary details to continue its operation in tracing down the x and creditor y with proposition p. When this commitment
incompliant agents. is in charge, debtor x becomes committed to creditor y for
The rest of this paper is organized as follows. Section II satisfying p.
gives necessary background on protocols, commitments and
C+. Section III describes the running example and defines cc(x, y, p, q): This is a conditional commitment between
the problem formally. Section IV introduces our solution to debtor x and creditor y with condition p and proposition q.
deal with exceptions in distributed scenarios, and Section V When this commitment is in charge, if p is satisfied (by y), x
explains its details. Section VI presents a discussion of our will become committed to y for satisfying q.
The following four operations describe how commitments
work with comparisons to the literature and provides directions
are manipulated throughout a protocol. We assume that each
for further research.
protocol action initiates a commitment operation (i.e., altering
II. T ECHNICAL BACKGROUND a contract between agents). Thus, commitment operations
describe the semantics of protocol actions.
In this section, we first describe formally what we mean
by a business protocol, then we review the necessary concepts create(x, c(x, y, p)): This operation initiates the creation
related to specifying commitments, and realizing them in a of the base-level commitment c. It is performed by x, the
formal description language. debtor of the commitment. Since this operation creates a new
commitment which does not hold previously, it causes a state
create(x,c(x,y,p))
A. Protocols & Runs transition (Si −−−−−−−−−−−→ Si ∪ {c(x, y, p)}).
Definition II.1. A protocol P is a 6-tuple ccreate(x, cc(x, y, p, q)): This operation initiates the creation
hS, A, C, R, SI , SF i, such that S is a finite set of states, A is of the conditional commitment cc. It is performed by x, the
a finite set of actions, C is a finite set of conditions, R is a debtor of the commitment. This operation also causes a state
finite set of roles, SI is the set of initial states (SI ⊂ S), and ccreate(x,cc(x,y,p,q))
transition (Si −−−−−−−−−−−−−−→ Si ∪ {cc(x, y, p, q)}).
SF is the set of final states (SF ⊂ S). Intermediate (middle)
discharge(x, c(x, y, p): This operation resolves the base-
states SM are states that are not in SI or in SF .
level commitment c. It is performed by x, the debtor of the
Definition II.2. A state is a set of conditions and commitments commitment, and the commitment c is terminated afterward.
that hold in it. A base-level commitment is resolved when the proposition p
of the commitment becomes true. This operation causes a state
Definition II.3. A run R of a protocol P is simply a sequence
transition since a previously holding commitment disappears
of states hS0 , ..., Sn i starting from an initial state (S0 ∈ SI ). discharge(x,c(x,y,p))
For now, we consider only finite runs. (Si −−−−−−−−−−−−−− → Si − {c(x, y, p)} ∪ {p}).
cdischarge(x, cc(x, y, p, q)): This operation resolves the
Definition II.4. A desirable run is the one that ends in a final
conditional commitment cc. It is performed by x, the debtor
state (Sn ∈ SF ).
of the commitment, and the conditional commitment cc is
Definition II.5. An exceptional run is the one that ends in an terminated afterward. If the proposition q of a conditional
intermediate state (Sn ∈ SM ), and thus does not reach a final commitment cc becomes true, then cc is discharged imme-
cdischarge(x,cc(x,y,p,q))
state. diately causing a state transition (Si −−−−−−−−−−−−−−−−→
Desirable runs are preferred by agents since they lead them Si − {cc(x, y, p, q)} ∪ {q}). If the condition p of cc is brought
to reach their goals, whereas exceptional runs are unexpected about, then cc is discharged, and a new base-level commitment
by agents and proper action (i.e., exception handling routines) is created with the proposition q of cc causing another state
cdischarge(x,cc(x,y,p,q))
has to be taken in order for the protocol to evolve from those transition (Si −−−−−−−−−−−−−−−−→ Si − {cc(x, y, p, q)} ∪
states. {c(x, y, q)} ∪ {p}).
Definition II.6. An agent-centric sub-protocol C. Commitment Protocols
P ′ hS′ , A′ , C′ , R′ , SI′ , SF
′
i is a subset of the main protocol In this section, we integrate commitments into protocols.
PhS, A, C, R, SI , SF i in which; (1) ∀s′ ∈ S′ , ∃s ∈ S : s′ ⊆ s, Definitions II.7, II.8, and II.9 provide useful properties re-
garding states with respect to commitments. are four states (S0 , S1 , S2 , and S3 ), three actions that enable
the transitions between the states (sendPayment, sellBook,
Definition II.7. A state is inconsistent if it is one of the
and deliverBook), and three conditions corresponding to the
following; (1) state Si = {cc(x, y, p, q), p} is inconsistent
outcomes of the actions in the protocol (payc, bookc, and
since the conditional commitment cannot coexist with its
deliverc). There is a single initial state (S0 ), a single final
condition, (2) state Sj = {p, ¬p} is inconsistent since a
state (S3 ), and two intermediate states (S1 and S2 ).
condition cannot coexist with its negation.
:− s o r t s 1
Definition II.8. Two states are equivalent with respect to an role ; 2
agent if they share the same conditions and commitments condition . 3
regarding that agent. :− v a r i a b l e s 5
x , y , z :: role ; 6
Example 2. Let Si = {cc(x, y, p, q), r} and Sj = p , q : : condition . 7
{cc(x, y, p, q), cc(y, z, v, w), r, u} be two states, and assume
r is a condition that agent x can bring about (but does not % D e c l a r a t i o n o f commitments 9
:− c o n s t a n t s 10
affect agent y’s working) and u is a condition that agent y can commitment ( r o l e , r o l e , c o n d i t i o n ) 11
bring about (but does not affect agent x’s working). Then, Si :: inertialFluent ; 12
and Sj are equivalent states for agent x (since the commitment ccommitment ( r o l e , r o l e , c o n d i t i o n , c o n d i t i o n ) 13
:: inertialFluent ; 14
cc(y, z, v, w) is irrelevant to agent x), but not equivalent states
for agent y (since the commitment cc(y, z, v, w) that is related % Commitment o p e r a t i o n s 16
to agent y does not hold in state Si , but holds in state Sj ). c r e a t e ( role , role , condition ) : : action ; 17
discharge ( role , role , condition ) : : action ; 18
Definition II.9. The distance between two states Si and Sj c c re a t e ( role , role , condition , condition ) 19
:: action ; 20
is the number of commitment operations that are required to cdischarge ( role , role , condition , condition ) 21
bring the protocol from state Si to state Sj . :: action ; 22
Example 3. Let Si = {cc(x, y, p, q)} and Sj = % Commitment r u l e s 24
{c(x, y, q), cc(y, z, q, r), p} be two states. Then, the distance c r e a t e ( x , y , p ) c a u s e s commitment ( x , y , p ) 25
where x<>y . 26
between states Si and Sj is 2 since it takes two commitment d i s c h a r g e ( x , y , p ) c a u s e s −commitment ( x , y , p ) 27
operations to go from state Si to Sj ; a ccreate operation to where x<>y . 28
create cc(y, z, q, r), and a cdischarge operation to resolve cc(x, c c r e a t e ( x , y , p , q ) c a u s e s ccommitment ( x , y , p , q ) 29
where x<>y & p<>q . 30
y, p , q) into c(x, y, q). c d i s c h a r g e ( x , y , p , q ) c a u s e s −ccommitment ( x , y , p , q ) 31
& commitment ( x , y , q ) where x<>y & p<>q . 32
D. The Action Description Language C+
We realize the business scenarios to be described using com- Listing 1. Commitment Operations in C+
mitment protocols specified in the action description language,
C+ [2], [3]. A protocol in C+ is composed of a set of states
{cc(bookstore,customer,payc,deliverc),
and transitions between states (i.e., a transition system). A cc(deliverer,bookstore,bookc,deliverc)}
state may contain several fluents that hold in that state (true {payc, c(bookstore,customer,deliverc),
propositions). A fluent’s value is changed as the consequence s0 cc(deliverer,bookstore,bookc,deliverc)}
sendPaym
of an action that is performed by an agent. An inertial fluent ent(cust
omer)
s1
is the one whose value is not changed until an action makes
it change. Our use of C+ for formalizing commitments and to
re
)
ks
their operations are based on that of Chopra and Singh [3]. b oo
o k(
Bo
Listing 1 shows how commitment operations are realized {payc, bookc, ll
c(bookstore,customer,deliverc), se
c(deliverer,bookstore,deliverc)}
in C+. This is a basis for other protocol specifications that
utilize commitments. Through lines 10-14, commitments and s2 {payc, bookc, deliverc}
conditional commitments are modeled as inertial fluents. Com- deliverB
ook(de
mitment operations shown through lines 17-22 are modeled as liverer) s3
auxiliary (i.e., simple) actions. An auxiliary action has to be
initiated by a protocol action and cannot be performed inde-
pendently. The causation rules associated with those operations
are shown through lines 25-32. Fig. 1. Purchase & Delivery Protocol
III. B USINESS S CENARIO No conditions initially hold in S0 , but two conditional
In order to show how commitments are utilized in real commitments are present. The first commitment cc(bookstore,
business environments, we describe in detail our running ex- customer, payc, deliverc) means that the bookstore is commit-
ample that represents concrete business interactions. Figure 1 ted to make sure that the book is delivered if the customer
describes the purchase protocol introduced in Section I. There pays for it. The second commitment cc(deliverer, bookstore,
bookc, deliverc) means that the deliverer is committed to lines 15-17. The initiate action is performed by the role super
deliver the book to the customer if the bookstore sends it. to initialize the conditional commitments between the parties
Since the customer’s goal is to get the book delivered, it (i.e., super can be considered as a protocol designer). Certain
performs the sendPayment action. This brings the protocol actions cannot be performed by some agents. As line 20
to state S1 where condition payc holds as the outcome of suggests, the sendPayment action cannot be performed by the
the sendPayment action. Also, the conditional commitment bookstore.
cc(bookstore, customer, payc, deliverc) is discharged to the
% I n c l u d e t h e commitment o p e r a t i o n s 1
base-level commitment c(bookstore, customer, deliverc). Next, :− i n c l u d e ’ com−s p ec ’ . 2
the bookstore performs the sellBook action which brings the
protocol to state S2 . Accordingly, condition bookc holds and :− o b j e c t s 4
super , customer , bookstore , d e l i v e r e r : : r o l e ; 5
the conditional commitment c(deliverer, bookstore, bookc, de- payc , bookc , d e l i v e r c : : c o n d i t i o n . 6
liverc) is discharged to the base-level commitment c(deliverer,
bookstore, deliverc). Finally, the deliverer performs the de- % F l u e n t s t h a t d e f i n e t h e s t a t e s o f t h e p r o t o c o l 8
:− c o n s t a n t s 9
liverBook action which brings the protocol to state S3 . Both i n i t ( r o l e ) , pay ( r o l e , r o l e ) , book ( r o l e , r o l e ) , 10
commitments in S2 are discharged and condition deliverc d e l i v e r ( role , rol e ) : : i n e r t i a l F l u e n t ; 11
holds in S3 . State S3 is the final state for the protocol since i n i t i a l , f i n a l : : sdFluent . 12
all three conditions hold at the same time. Thus, a desirable % P r o t o c o l a c t i o n s 14
run for the protocol is hS0 , S1 , S2 , S3 i. i n i t i a t e ( r o l e ) , s en d P ay m en t ( r o l e ) , 15
sellBook ( r ol e ) , deliverBook ( r ol e ) 16
: : exogenousAction ; 17
% C e r t a i n a c t i o n s a r e done by s p e c i f i c r o l e s o n l y 19
{cc(bookstore,customer,payc,deliverc)}
n o n e x e c u t a b l e s en d P ay m en t ( b o o k s t o r e ) . 20
... 21
s0
sen % P r o t o c o l a c t i o n s en d P ay m en t i s v i s i b l e t o t h e 23
dPa % customer agent 24
yme
nt( {payc,
s en d P ay m en t ( c u s t o m e r ) c a u s e s 25
cus c(bookstore,customer,deliverc)}
tom pay ( c u s t o m e r , b o o k s t o r e ) i f 26
er)
ccommitment ( b o o k s t o r e , c u s t o m e r , payc , d e l i v e r c ) . 27
s1 s en d P ay m en t ( c u s t o m e r ) c a u s e s 28
ore
) d i s c h a r g e ( c u s t o m e r , b o o k s t o r e , p ay c ) 29
t
{payc, deliverc} oks i f commitment ( c u s t o m e r , b o o k s t o r e , p ay c ) . 30
ok (bo
rBo s en d P ay m en t ( c u s t o m e r ) c a u s e s 31
ive
s3 del c d i s c h a r g e ( b o o k s t o r e , c u s t o m e r , payc , d e l i v e r c ) i f 32
ccommitment ( b o o k s t o r e , c u s t o m e r , payc , d e l i v e r c ) . 33
n o n e x e c u t a b l e s en d P ay m en t ( c u s t o m e r ) 34
i f pay ( c u s t o m e r , b o o k s t o r e ) ++ − i n i t ( s u p e r ) . 35
% Other p r o t o c o l a c t i o n s ar e not v i s i b l e to th e 37
% customer agent 38
Fig. 2. PCustomer Sub-Protocol ... 39
% Causation r e l a t i o n s f o r i n i t i a l and f i n a l s t a t e s 41
Note that states S1 and S2 are equivalent states for the cus- caused i n i t i a l i f i n i t i a l . 42
tomer, because condition payc and commitment c(bookstore, c a u s e d − i n i t i a l i f pay ( x , y ) . 43
customer, deliverc) hold in both states. In addition, condition ... 44
c a u s e d − i n i t i a l i f ccommitment ( x , y , p , q ) . 45
bookc and the discharged commitment cc(deliverer, bookstore, caused −f i n a l i f −f i n a l . 46
bookc, deliverc) are irrelevant to the customer. Thus, the
customer’s sub-protocol PCustomer includes states S0 , S1 , % I n f i n a l s t a t e , i f pay , book , and d e l i v e r h o l d s 48
c a u s e d f i n a l i f pay ( c u s t o m e r , b o o k s t o r e ) & 49
and S3 as shown in Figure 2. S0 is the initial state, S3 book ( b o o k s t o r e , d e l i v e r e r ) & 50
is the final state, and S1 is the only intermediate state for d e l i v e r ( d e l i v e r e r , customer ) . 51
this sub-protocol. There are two actions (sendPayment and . . .
52
deliverBook) and two conditions (payc and deliverc). Listing 2. Customer’s Protocol Described in C+
Listing 2 describes part of the customer’s protocol in C+.
Line 2 includes the commitment operations as introduced in The rules for the protocol action sendPayment are given
Listing 1. Lines 4-6 define the roles and conditions that are through lines 25-35. The first rule tells that the fluent
involved in the protocol. Lines 9-11 define the fluents repre- pay(customer, bookstore) will start to hold as a result of
senting the messages that hold in certain states of the protocol. the protocol action sendPayment(customer) if the conditional
For example, the message pay(customer,bookstore) has the commitment cc(bookstore, customer, payc, deliverc) exists
meaning that the customer has paid the bookstore for the book. prior to it (lines 25-27). The next two rules through lines 28-
The fluents in line 12 define the initial and final conditions 33 describe how existing commitments are resolved and new
for the protocol. The protocol actions are defined through commitments are created as a result of the same action. The
last rule ensures that the action sendPayment(customer) is not
performed if the payment is already made by the customer
or the protocol is not initialized yet by super (lines 34-35). Knowledge Base ( 1)
info
Since the scenario is distributed, other protocol actions, such r
rev matio
ea n
as sellBook or deliverBook, are not accessible (i.e., hidden) by l
the customer agent. The protocol starts with the state initial Agent
and is expected to terminate in state final (lines 42-46), if the Environment
(
ge 2) s
required fluents hold (lines 49-51). ne ta
ra te
tio
Now, let us study what can go wrong in a given protocol run n
Sj
and what exceptions can take place. If an expected action is not Si
Al
performed by an agent that is responsible for performing it, an ( 3) q
u
confi ery &
exception occurs. Two such exceptional runs for this protocol rma
Sk tion
Am
are hS0 , S1 i and hS0 , S1 , S2 i. The former run gets stuck at
state S1 , because the bookstore does not send the book to An
the deliverer. The latter run gets stuck at state S2 , because
the deliverer does not deliver the book to the customer. When
Fig. 3. General Approach
one of these exceptions occur, the customer agent cannot find
its cause immediately (i.e., in which of the main protocol
states the run gets stuck) since states S1 and S2 are equivalent agent has enough knowledge to generate other possible states
for it. However, in order for the customer to deal with the of the protocol. Once the states are generated, they need to be
exception, it is crucial that it learns about which agent is verified to find out whether they have caused the exception.
causing the exception. Next, we look at the general idea behind Accordingly, the agent directs the query about each generated
our proposed solution, and then explain the details of our state to one of the agents related to that state (i.e., involved in
approach. a commitment within that state).
IV. P ROPOSED S OLUTION V. I DENTIFYING E XCEPTION S OURCES
When faced with an exception, an agent tries to figure When an exception takes place, it is necessary for the agent
out what might have gone wrong. Figure 3 summarizes the to identify who caused the exception so that it can deal with
approach that agents utilize when detecting exceptions. First, the exception accordingly. As seen in the previous section,
the agent reasons using its own knowledge-base. In many this is not easy since an agent may view a number of states
cases, this would not be enough to identify the exception. identical when indeed they are different for other agents. The
However, in many settings, as time evolves, new information question then is how can an agent construct possible real states
about the environment becomes available (step 1). Based on of the world? If the agent can generate such possibilities, then
the new information, the agent again tries to predict possible it can query the involved agents and ask them to confirm one
contracts between other agents so that it can figure out what of these states. Next, we present such an algorithm. Without
has been violated to cause an exception (step 2). Once the loss of generality, we assume that the algorithm is used by the
agent has possible ideas about what might have gone wrong, customer agent.
it queries other agents that are related to the possible cause of
A. State Prediction Algorithm
the exception and asks them to confirm one of the possibilities
(step 3). In this section, we propose an algorithm for the agents to
For the above example, this would work as follows: At the use for constructing the hidden states (i.e., unknown states
beginning, note that the customer is not aware of the existence prior to exception) that might be the cause of exceptions. In
of a deliverer since its sub-protocol does not include such a order to construct a state, the agent has to generate the possible
role. Thus, its knowledge base includes only the bookstore conditions and commitments that hold in that state. Recall that
other than itself. In addition, the conditions initially known by each agent is only aware of the commitments it is involved in.
the agent are limited to payc and its goal condition deliverc. So, the agent has to predict the possible commitments among
With this information only, it is not possible to construct state other participants to fill the definition of a hidden state.
S2 since it involves a commitment between the bookstore Algorithm 1 describes how the agent predicts the hidden
and the deliverer. However, even if its knowledge base does states for detecting exceptions. The requirements for the
not contain that information, the customer agent may become algorithm to execute properly are; current state of the agent in
aware of other roles, and extend its sub-protocol with new its sub-protocol, its goal condition, commitments it is involved
information revealed by other agents. For example, if the in, conditions and roles it is aware of, and a maximum allowed
bookstore announces that the book is sent to the deliverer, then distance parameter for selecting states to query. The algorithm
the customer will be aware of the existence of a deliverer role consists of two stages; state generation and state selection, that
and the condition bookc. Information exposure is a simple task we describe next.
that is often performed in real-life delivery scenarios. Now, the State Generation Stage: This stage starts with creating a set
Algorithm 1 Predicting Hidden States process. Note that no inconsistent states are generated at this
Require: Sc {current state} stage of the algorithm, because this process resolves necessary
Require: Cgoal {goal condition} commitments with conditions whenever is possible. The state
Require: commitments {initial commitments} is then ready to be extended with the generated commitments
Require: C {conditions whose existence are known} and conditions (lines 10-11). Finally, the state is added to the
Require: R {roles whose existence are known} set of generated states (line 12). This stage continues until no
Require: dist {maximum allowed distance} new states are generated.
{I. State Generation Stage} State Selection Stage: This stage eliminates states generated
1: S ← {Sc } {add current state to the generated states}
by the first stage of the algorithm which are at a distance
2: for all commitmenti in commitments do
from the current state of the agent’s sub-protocol. We apply
3: S ← Sc {create a new state from current state} the state distance property to compute the distance value.
4: cc ← cc(GoalRole, CondRole, Cond, Goal) The maximum allowed distance for selection is a configurable
5: Goal ← Cgoal {replace goal condition} parameter of the algorithm controlled by the dist value in line
6: GoalRole ← select(R) {pick a role} 15. The number of states selected out of this stage is expected
7: generate Cond and CondRole using commitmenti to decrease if we select this parameter to be low. However, it
8: cond ← select(C) {pick a set of conditions} increases the chance that the actual exceptional state is also
9: apply commitment operations on cc assuming condi- eliminated by this process.
tions in cond holds
10: S ← S ∪ cc {add the commitments to the state} Example 4. Let us now depict the algorithm using our sce-
11: S ← S ∪ cond {add the set of conditions to the state} nario. Recall that we’ve considered two exceptional situations;
12: S ← S ∪ {S} {add the generated state to the result} one gets stuck at state S1 , and the other gets stuck at state S2 .
13: end for However, since S2 is a hidden state for the customer agent,
{II. State Selection Stage} both S1 and S2 converge to state S1 of the customer agent’s
14: for all Si in S do sub-protocol. At this point, the customer agent thinks that
15: if distance(Si ,Sc ) > dist then the exception is caused by the bookstore since the delivery
16: S ← S − {Si } {remove the state from the result} will be done by the bookstore according to its sub-protocol.
17: end if But, suppose that the bookstore agent informs the customer
18: end for agent on the delivery process. That is, it tells that the book is
19: return S given to the deliverer agent. Now, the customer agent has extra
knowledge with which it can extend its sub-protocol. Now, the
customer agent can initiate the state generation process. The
goal of the agent is to successfully generate state S2 and query
for storing generated states and the current state of the agent is agents related to that state (i.e., deliverer) to see whether the
added to this set (line 1). A generated state is not constructed main protocol is actually in that state. If so, the exception is
from scratch, but rather extended from the current state of the caused by the deliverer agent, otherwise the bookstore agent
agent (line 3). In order to fill the state definition, the agent gen- is the cause of the exception. Now, suppose the agent has
erates the hidden commitments between other parties starting generated several different states among which one of them
with a conditional commitment template with two roles and is the state S2 . To learn whether the main protocol is in state
two conditions (line 4). The goal condition for the commitment S2 , the customer agent queries the deliverer agent to confirm
(Goal) is the agent’s goal (line 5), and the business party that the existence of state S2 .
can bring about that condition (GoalRole) is picked from the
set of roles the agent is aware of (line 6). In order to fill the B. Implementation & Evaluation
middle parts of the commitment (Cond and CondRole), the
agent traces through its own commitments and finds which In order to implement our approach, we used C+ to describe
parties it has a commitment with. For each commitment the scenario formally as shown partly in Listings 1 and 2,
cc(x, Role, Cond, p) or cc(Role, x, p, Cond), where Role is then implemented the state prediction algorithm in Java. In
the agent’s role and Cond is one of the conditions that the the trivial cases where the initial commitments between the
agent can bring about, it replaces CondRole and Cond of parties are in force, the protocols terminate as desired for
the template commitment using all possible pairs of x and the customer agent. However, since our aim is to observe
p as line 7 suggests. The agent then searches for conditions exceptional situations, we disrupt the C+ descriptions of the
to put into the state definition (line 8). Those conditions are scenarios (i.e., remove certain commitments) to enable the
also used in applying commitment operations on the generated occurrence of such exceptions. Once certain parts of the
commitments. Since the generated commitments are the initial scenario descriptions are extracted, the prediction algorithm
versions of contracts between other parties, they might have is run to generate the possible missing states. Finally, one or
been changed during the execution of the protocol. Line more generations complete the scenario descriptions as they
9 of the algorithm provides this commitment manipulation should be, leading to a desirable run for the customer agent.
The algorithm can be extended to support sequential pro- commitment protocols in C+ form the basis of our work.
tocols that involve more than one agent between the initiator However, Chopra and Singh do not provide mechanisms for
(i.e., customer) and the terminator of the protocol (i.e., de- distributed verification as we have done here.
liverer). For example, consider an extension to our scenario Mallya and Singh divide exceptions into two categories
where books are packaged before they are sent for delivery. [6]; (1) expected exceptions which are handled at design-
This packaging process needs another role, the packager, to be time using preferences over protocol runs, and (2) unexpected
present in the protocol. Thus, the algorithm has to generate two exceptions which occur at run-time and are handled via
conditional commitments instead of one for each state it will splicing exception handlers with base protocols. Their work
generate, involving the contracts between; (1) the bookstore helps protocol designers for handling exceptions. However,
and the packager, and (2) the packager and the deliverer. Our handling unexpected exceptions with such generic handlers is
current system supports these extensions. costly. The work of Venkatraman and Singh resembles our
Correctness of the Algorithm: Here, we discuss the two work since each agent checks compliance on its own [7]. The
stages of the algorithm (state generation and state selection) process is distributed in a sense that each agent has access to
in order to argue on the correctness of our algorithm. That is, its own set of messages during execution, but their business
the state causing the exception has to be generated in the state scenario does not fully simulate a distributed environment. Our
generation stage, and it has to be selected as a candidate for work differs from theirs since an agent in our scenario needs
querying in the state selection stage. Next, we consider each extra information when resolving an exception.
stage separately: Our work can also be considered in the multiagent plan
execution context for identifying failures. Jonge et al. [8]
State Generation Stage: The number of states generated is classify the diagnosis of plan failures into two categories; (1)
limited to the knowledge of the agent about the protocol (i.e., primary plan diagnosis simply points out the failed action,
the roles and conditions). (2) secondary plan diagnosis identifies the actual cause of the
Lemma V.1. Let Se be a state in protocol P , and let c be failure as we also focus in our work. Although the agents
a customer agent executing in P . Assume c is currently in in their plan execution system have partial observations over
state Sc of its sub-protocol Pc (Pc ⊆ P ), and assume state Se the system, they still have a major knowledge about their
differs from state Sc in terms of the set of conditions Ecnd and environment. Thus, our work differs form theirs in terms of
the set of commitments Ecmm . Let the commitments in Ecmm the distributed protocol execution.
include the set of conditions Econ and the set of roles Erole , Expectations have also been used to formalize business
and let Econd = Ecnd ∪ Econ . Now, if c faces an exception protocols as described in the SCIFF framework [9]. SCIFF
caused at state Se , and if c knows about the conditions in is based on abductive logic, and it does not only specify a
Econd and the roles in Erole , then state Se will be generated business protocol, but also helps verify agent interactions in
by agent c. open systems. Compliance verification has been considered in
other domains; in composite Web services [10], or in agent
Proof: Recall that agent c generates a state by filling its communication languages (ACLs) [11]. An ACL is part of an
definition with conditions and commitments. Agent c tries all agent communication framework. The proposed verification
possible combinations of conditions and commitments it can process in Guerin and Pitt’s work [11] may require access
generate using its knowledge about Pc . Note that Se = Sc ∪ to agent’s internal process, whereas our idea of verification
Ecnd ∪ Ecmm , thus agent c needs to generate the conditions depends only on interaction.
in Ecnd and the commitments in Ecmm . Using its knowledge Our approach is based on constructing possible hidden
about Econd , agent c can generate the conditions in Ecnd , since states and querying other agents for confirming those states
Ecnd ⊆ Econd . Using its knowledge about Econd and Erole , (i.e., identifying which one of them caused the exception in
agent c can generate the commitments in Ecmm , since those the main protocol). Intuitively, it is reasonable for the agent
commitments are composed of the conditions in Econ and the to query other agents which are committed to it (i.e., the
roles in Erole which are known by agent c (Econ ⊆ Econd ). bookstore agent in our example). At this point, we assume
Thus, agent c generates state Se . that the agent receives honest responses from others. In a
State Selection Stage: The chance of the exceptional real-life scenario, this querying process will continue as a
state being selected is related to how distant it is from the delegation among the agents regarding their commitments
current state of the agent’s sub-protocol, and the choice of (i.e., the bookstore agent redirects the query of the customer
the maximum allowed distance parameter used for deciding agent to the deliverer agent for inspecting the exception
whether two states are distant. further). This delegation is also important in more complicated
scenarios since the exception facing agent may not be in
VI. D ISCUSSION contact with all other agents in the protocol. In addition, trust
Commitment protocols have been used before to formalize is another important issue when considering multiple agents
business scenarios [4], [5]. Chopra and Singh explain how that enact a distributed protocol. It is more probable that an
transformation specifications are used in order to extend agent will respond to the agents it is committed to rather than
protocols to cover new situations [3]. Their formalization of other agents that it has no previous contact with. We aim to
investigate the application of trust strategies when considering
such complicated scenarios.
ACKNOWLEDGEMENT
This research has been supported by Boğaziçi University
Research Fund under grant BAP09A106P, The Scientific and
Technological Research Council of Turkey by a CAREER
Award under grant 105E073, and the Turkish State Plan-
ning Organization (DPT) under the TAM Project, number
2007K120610. We thank the anonymous referees for their
comments on this paper.
R EFERENCES
[1] M. P. Singh, “An ontology for commitments in multiagent systems:
Toward a unification of normative concepts,” Artificial Intelligence and
Law, vol. 7, pp. 97–113, 1999.
[2] E. Giunchiglia, J. Lee, V. Lifschitz, N. McCain, and H. Turner, “Non-
monotonic causal theories,” Artificial Intelligence, vol. 153, no. 1-2, pp.
49–104, 2004.
[3] A. K. Chopra and M. P. Singh, “Contextualizing commitment protocols,”
in AAMAS ’06: Proceedings of the fifth international joint conference
on Autonomous Agents and Multiagent Systems. New York, NY, USA:
ACM, 2006, pp. 1345–1352.
[4] P. Yolum and M. P. Singh, “Flexible protocol specification and execution:
applying event calculus planning using commitments,” in AAMAS ’02:
Proceedings of the first international joint conference on Autonomous
Agents and Multiagent Systems. New York, NY, USA: ACM, 2002,
pp. 527–534.
[5] N. Desai, A. K. Chopra, M. Arrott, B. Specht, and M. P. Singh,
“Engineering foreign exchange processes via commitment protocols,”
in International Conference on Services Computing (IEEE SCC), 2007,
pp. 514–521.
[6] A. U. Mallya and M. P. Singh, “Modeling exceptions via commitment
protocols,” in AAMAS ’05: Proceedings of the fourth international joint
conference on Autonomous agents and multiagent systems. New York,
NY, USA: ACM, 2005, pp. 122–129.
[7] M. Venkatraman and M. P. Singh, “Verifying compliance with commit-
ment protocols,” Autonomous Agents and Multiagent Systems, vol. 2,
no. 3, pp. 217–236, 1999.
[8] F. D. Jonge, N. Roos, and C. Witteveen, “Diagnosis of multi-agent plan
execution,” in In Multiagent System Technologies: MATES 2006, LNCS
4196. Springer, 2006, pp. 86–97.
[9] M. Alberti, F. Chesani, M. Gavanelli, E. Lamma, P. Mello, and P. Tor-
roni, “Verifiable agent interaction in abductive logic programming: The
sciff framework,” ACM Transactions on Computational Logic, vol. 9,
no. 4, pp. 1–43, 2008.
[10] A. Lomuscio, H. Qu, and M. Solanki, “Towards verifying compliance
in agent-based web service compositions,” in Proceedings of 7th In-
ternational Conference on Autonomous Agents and Multiagent Systems
(AAMAS), 2008, pp. 265–272.
[11] F. Guerin and J. Pitt, “Agent communication frameworks and verifica-
tion,” in AAMAS 2002 Workshop on Agent Communication Languages,
2002.