Towa ds In e ac ion P o ocol Ope a ions o
La ge Mul i-agen Sys ems
Joaqu´ın Pe˜na, Ra ael Co chuelo, and Jos´eLuisA jona
Dp o. de Lenguajes y Sis emas In o m´a icos
A da. de la Reina Me cedes, s/n. Se illa 41.012 (Spain)
[email p o ec ed],www.lsi.us.es/˜ dg
Abs ac . I is widely accep ed ha ole-based modelling is qui e ade-
qua e in he con ex o mul i-agen sys ems (MAS) modelling echniques.
Un o una ely, e y li le wo k has been epo ed on how o desc ibe
he ela ionships be ween se e al ole models. Fu he mo e, many au-
ho s ag ee on ha p o ocols need o be encapsula ed in o high-le el
abs ac ions. The syn hesis o ole models is an ope a ion p esen ed in
he OORAM me hodology ha allows us o build new ole models om
o he s in o de o ep esen he in e ela ions hey ha e. To he bes o
ou knowledge his ope a ion has o be pe o med manually a p o ocol
le el and wo ks wi h p o ocols exp essed by means o messages. In his
pape , we p esen wo algo i hms o ex ac he p o ocol o a ole om
he p o ocol o a ole model and ice e sa ha au oma e he syn hesis
o ole models a he p o ocol le el. Fu he mo e, in o de o deal wi h
p o ocol desc ip ions in a op down app oach bo h ope a ions wo k wi h
p o ocols exp essed by means o an abs ac ion call mul i- ole in e ac ion
(mRI).
1 In oduc ion
When a la ge sys em is modelled, complexi y becomes a c i ical ac o ha has
o be deal wi h p ope ly. In o de o ackle complexi y G. Booch ecommended
se e al powe ul ools such as: Decomposi ion, Abs ac ion, and Hie a chy [5].
In addi ion, hese ools we e also p esen ed as app op ia e o Agen -O ien ed
So wa e Enginee ing (AOSE) o complex MAS, and we e adap ed o his field
in [18] as ollows:
–Decomposi ion: I is based on he p inciple di ide and conque .I smain
ad an age is ha i helps o limi he designe s scope o a po ion o he
p oblem.
–Abs ac ion: I is based on defining simplified models o he sys em ha
emphasises some de ails and a oid o he s. I is in e es ing since i limi s
he designe scope o in e es and he a en ion can be ocused on he mos
impo an de ails.
–O ganisa ion/Hie a chy: I elies on iden i ying and managing he ela ion-
ships be ween he a ious subsys ems in he p oblem. I makes i possible o
g oup oge he a ious basic componen s and deal wi h hem as highe -le el
uni s o analysis, and, p o ides means o desc ibing he high-le el ela ion-
ships be ween se e al uni s.
Un o una ely, we hink ha hese ools ha e no been ca e ully applied in he
app oaches ha a e appea ing in his field. We ha e iden ified se e al p oblems
in cu en me hodologies ha ou app oach ies o sol e.
On he one hand, he e exis s a huge seman ic gap in MAS p o ocol desc ip-
ion me hodologies because mos o hem fi s iden i y which asks ha e o be
pe o med, and hen use low le el desc ip ions such as sequences o messages
o de ail hem. Al hough hese messages may ep esen a high le el iew o a
p o ocol, which shall be efined la e , he asks ha a e pe o med a e o mu-
la ed as a se o messages. This ep esen a ion implies ha he abs ac ion le el
alls d ama ically since a ask equi es se e al messages o be ep esen ed. Fo
ins ance, an in o ma ion eques be ween wo agen s mus be ep esen ed wi h
wo messages a leas (one o ask, and ano he o eply). This in oduces a se-
man ic gap be ween asks and hei in e nal design since i is difficul o iden i y
he asks ep esen ed in a sequence o messages. This ep esen a ion becomes an
impo an p oblem ega ding eadabili y and manageabili y o la ge MAS and
can be pallia ed using he abs ac ion ool p esen ed abo e.
On he o he hand, in AOSE is widely accep ed ha desc ibing he sys em
as a se o ole models ha a e mapped on o agen s is qui e adequa e since
i applies he decomposi ion ool [6,12,21,19,22,23,34]. Un o una ely, we ha e
ailed o find me hodologies o MAS ha use some in e es ing ideas abou ole
modelling p esen ed by Reenskaug and Ande sen in he OORAM me hodology
[1,27]. Ob iously, when we deal wi h a complex and la ge sys ems se e al ole
models may appea , and usually, hey a e in e ela ed. The ole model syn hesis
ope a ion [2], a emp s o de ail how ole models a e ela ed, hus applying
he o ganisa ion ool. This ope a ion consis s o desc ibing new syn hesised ole
models in e ms o o he s. In a syn hesised ole model, new oles may appea
and syn hesised oles may also appea as agg ega ion o o he s. Un o una ely,
OORAM also suffe s om he fi s p oblem we ha e shown abo e since i deals
wi h beha iou specifica ion in e ms o messages.
In his pape , we p o ide he fi s s ep owa ds he solu ion o hese p ob-
lems enume a ed abo e using he ools p oposed by Booch: i) In o de o apply
he abs ac ion ool, we ha e defined an abs ac ion called mul i- ole in e ac ion
(mRI) which encapsula es he in e ac ion p o ocol (he ea e p o ocol) co e-
sponding o a ask ha is pe o med by an a bi a y numbe o oles. mRIs a e
used as fi s modelling class elemen s o ep esen an abs ac iew o he p o-
ocol o a ole model which can be efined wi h he echniques p oposed in [25].
ii) In o de o apply he o ganisa ional ool, we ha e also defined wo ope a ions
on p o ocols (desc ibed in e ms o mRIs) o au oma e and ease he syn hesis
ope a ion since i ope a es on in e ac ion p o ocols o a ole ins ead o wi h he
whole in e ac ion p o ocol o a ole model: he fi s one, called decomposi ion,
in e s a ole p o ocol om a ole model p o ocol au oma ically; and he second
one, ha we called composi ion, in e s a ole model p o ocol om a se o ole
p o ocols au oma ically.
This pape is o ganized as ollows: in Sec ion 2, we p esen he ela ed wo k
and he ad an ages o ou app oach o e o he s; in Sec ion 3, we p esen he ex-
ample we use; in Sec ion 4, we p esen he p o ocol abs ac ion we ha e defined;
in Sec ion 5, we show how o desc ibe he p o ocol o a ole model; in Sec ion 6,
we p esen he algo i hms o compose and decompose p o ocols, and, in Sec ion
7, we p esen ou main conclusions.
2 Rela ed Wo k
In he con ex o dis ibu ed sys ems many au ho s ha e iden ified he need
o ad anced in e ac ion models and ha e p oposed mul i-objec in e ac ions
ha encapsula es a piece o p o ocol be ween se e al obje cs [24]. Fu he mo e,
mos objec -o ien ed analysis and design me hods also ecognise he need o
coo dina ing se e al objec s and p o ide designe s wi h ools o model such
mul i-objec collabo a ions. Diffe en e ms a e used o e e o hem: objec
diag ams [4], p ocess models [7], message connec ions [8], da a-flow diag ams
[28], collabo a ion g aphs [32], scena io diag ams [27], collabo a ions [13,29]. In
MAS me hodologies many au ho s ha e also p oposed abs ac ion o model co-
o dina ed ac ions such as nes ed p o ocols [3], in e ac ions [6] o mic o-p o ocols
[22], and so on. Un o una ely, he abs ac ions p esen ed abo e a e usually used
o hide unnecessa y de ails a some le el o abs ac ion, euse he p o ocol de-
sc ip ions in new sys ems, and imp o e modula i y and eadabili y; howe e ,
mos designe s use message–based desc ip ions.
We hink ha mos AOSE app oaches model p o ocols a low le el o abs ac-
ion since hey equi e he designe o model complex coope a ions as message-
based p o ocols om he beginning. This issue has been iden ified in he GAIA
Me hodology [33], and also in he wo k o Cai e e . al. [6], whe e he p o o-
col desc ip ion p ocess s a s wi h a high le el iew based on desc ibing asks
as complex communica ion p imi i es (he ea e in e ac ions). We hink ha
he ideas p esen ed in bo h pape s a e adequa e o his kind o sys ems whe e
in e ac ions a e mo e impo an han in objec -o ien ed p og amming. As he
me hodologies GAIA and Cai e’s Me hodology, we also use in e ac ions (mRIs)
o deal wi h he fi s s age o p o ocol modelling.
In he GAIA me hodology, p o ocols a e modelled using abs ac ex ual em-
pla es. Each empla e ep esen s an in e ac ion o ask o be pe o med be ween
an a bi a y numbe o pa icipan s. In [6], Cai e e al. p opose a me hodology
in which he fi s p o ocol iew is a s a ic iew o he in e ac ions in a sys em.
La e , he in e nals o hese in e ac ions a e desc ibed using AUML [3].
Un o una ely, he ope a ions we p opose a e difficul o be in eg a ed wi h
hese me hodologies. The eason why his happens is ha we ha e ound nei he
an in e ac ion model o MAS able o desc ibe o mally a sequence p o ocol ab-
s ac ions, no ope a ions on hese high le el p o ocol defini ions. GAIA p o ocol
desc ip ions, o example, a e based on ex ual desc ip ion hus i is difficul o
eason o mally on hem. In Cai e’s me hodology, i is no shown how o se-
quence in e ac ions. Al hough Koning e al. desc ibe he sequence o execu ion
o hei abs ac ion using a logic-based o mulae (CPDL), which consis s o an
ex ension o ansi ion unc ion o Fini e S a e Au oma a (he ea e FSA), hey
do no define ope a ions o ope a e wi h p o ocols. In ou app oach, we also de-
fine he sequence o mRI by means o Fini e S a e Au oma on (FSA) which has
been also used by o he s au ho s a message le el. We ha e chosen FSAs because
his echnique has been p o ed o be adequa e o ep esen ing he beha iou o
eac i e agen s [11,14,16,22].
Rega ding he ope a ions we p esen o he bes o ou knowledge he decom-
posi ion ope a ion has no been defined be o e in his con ex . This ope a ion
can be use ul o euse, pe o ming syn hesis o ole models since i ope a es wi h
he p o ocol o a ole ins ead o wi h he whole p o ocol and o map se e al p o-
ocol on o he same agen class. Un o una ely, in OORAM me hodology such
ope a ion has o be applied manually o UML sequence diag ams.
The in e se ope a ion, ha we call composi ion, has been al eady defined by
o he au ho s, bu , o he bes o ou knowledge, hey do no use in e ac ion
wi h an a bi a y numbe o pa icipan s as we do [9,16,30,31]. This ope a ion
can be use ul o building new ole models eusing al eady defined ole p o ocols
s o ed in a beha iou eposi o y, pe o ming es s o adap i e beha iou s [16],
deadlock de ec ion o o unde s and easily he p o ocol o a new ole model [25].
Un o una ely, in OORAM his ope a ion has o be also pe o med manually.
3 The Example
To illus a e ou app oach, we p esen an example in which a MAS deli e s
sa elli e images on a pay pe use basis. We ha e di ide he p oblem in o wo
ole models: one whose goal is ob aining he images (images ole model)and he
o he o paying hem (pu chase ole model). This decomposi ion o he p oblem
allow us o deal wi h bo h cases sepa a ely.
In he Images ole model he use ( ole Clien ) has o speci y he images
ea u es ha he o she needs ( esolu ion, a ge , o ma , e ce e a). Fu he mo e,
we need a e es ial cen e ( ole Buffe ) o s o e he images in a buffe because
he h oughpu o a sa elli e ( ole Sa elli e) is highe han he a e age use can
p ocess and we need o analyse images ea u es in o de o de e mine hei o al
p ice which is he goal o ole Coun e .
In he Pu chase ole model we need o con ac he paymen sys em o con-
clude he pu chase. I in ol es h ee diffe en oles: a cus ome ole (Cus ome ),
a cus ome accoun manage ole (Cus ome ’s Bank), and a e es ial cen e
accoun manage ole (Buffe ’s Bank). When a cus ome acqui es a se o im-
ages he uses his o he debi –ca d o pay hem, he agen playing ole Cus ome
ag ees wi h a Cus ome ’s Bank agen and Buffe ’s Bank agen on pe o ming a
sequence o asks o ans e he money om he cus ome accoun o he buffe
accoun . I he Cus ome ’s Bank canno affo d he pu chase because i has no
enough money, he Cus ome ’s Bank agen hen pays on hi e–pu chase.
4 Ou P o ocol Abs ac ion: Mul i- ole In e ac ions
The desc ip ion o he p o ocol o a ole model is made by means o mRIs. This
p o ides an abs ac iew o he p o ocol ha makes i easie o ace he p oblem
a he fi s s ages o sys em modelling. Thus, we do no ha e o ake in o accoun
all he messages ha a e exchanged in a ole model in s ages whe e hese de ails
ha e no been iden ified clea ly.
A mul i- ole in e ac ion (mRI) is an abs ac ion ha we p opose o encap-
sula e a se o messages o an a bi a y numbe o oles. A concep ual le el,
an mRI encapsula es each ask ha a ole model should execu e o pe o m i s
goal. These asks can be in e ed in a hie a chical diag am [20] whe e we can
iden i y which asks shall execu e each ole model.
mRIs a e based on he ideas p esen ed in wo in e ac ion models o dis-
ibu edsys ems[15,10].Weha emade ha choicebecausebo hmodelsha e
a se o o mal ools ha may be used o MAS sys ems imp o ing he powe o
ou app oach, his allows, o pe o m deadlock es ing and au oma ic in e ac ion
efinemen s [25] o efficien dis ibu ed implemen a ions [26]. The defini ion o
an mRI is:
{(G(β)}&mRI name[ 1,
2,...,
N]
Whe e mRI name is an unified iden ifie o he in e ac ion and 1,
2,...,
N
a e he oles ha execu e hemRImRI name.βis he se o belie s o agen s
playing he oles implied in he mRI and G(β) is a boolean condi ion o e β.
This gua d is pa i ioned in a se o subcondi ions, one o each ole. G(β)holds
iff he conjunc ion o all subcondi ions o each ole is ue.
The idea behind gua ded in e ac ions has been adap ed om he in e ac ion
model in which ou p oposal is based; u he mo e, Koning e al. also adop
a simila idea. I p omo es he p oac i i y o agen s as we can see in [10,22]
because agen s a e able o decide whe he execu ing an mRI o no .
Thus, an mRI xshall be execu ed i he gua d o he mRI holds and all oles
ha pa icipa e on i a e in a s a e whe e he xis one o mRIs ha can be
execu ed. Fu he mo e, all o hem mus no be execu ing o he mRIs since he
in e ac ion execu ion is made a omically and each ole can execu e only one mRI
a hesame ime.Fo example,i weconside FSAsinFigu e3a e execu ing
an mRI sequence ha makes he he Sa elli e o be in s a e 1, he Buffe in s a e
4, he Clien in s a e 8 and he Coun e in s a e 11, i all he gua ds holds, we
can execu e Recei e,Send o Las Sa . In his case Las Buffe canno be execu ed
because i equi es he Buffe o be in s a e 5.
Finally, o each in e ac ion we should desc ibe some de ails ha we enume -
a e oughly below since i is no he pu pose o his pape . To desc ibe an mRI
in e nally, we should include he sequence o messages using AUML. Fu he -
mo e, we may use coo dina ion o nego ia ion pa e ns om a eposi o y i i s
possible (FIPA has define a eposi o y o in e ac ion pa e ns 1) and an objec i e
1h p://www.fipa.o g/specs/fipa00025/XC00025E.h ml

Clien
Clien
Sa elli e
Sa elli e Bu e
Bu e
Coun e
Coun e
Recei e
Send
Las _Bu e
Las _Sa
Ask
Fig. 1. Collabo a ion diag am o Images ole model
unc ion ha de e mines which o a ailable mRIs shall be be e o execu e i
se e al o hem can do so a he same momen .
Rega ding he example, he desc ip ion o one o he mRIs o he Images ole
model which i is used o ask o images (see Figu e 3) is:
{Coun e .Connec ed(Bu e .ID())&Coun e .enable()}&
ask[Clien ,Bu e ,Coun e ]
The es o hemRIsin heImages ole model a e: ask, which is used o
ask o images, send, which sends an image om he Sa elli e o he Buffe ,
ecei e, which sends an image om Buffe o Clien ,Las Sa , which indica es
he las image o ans e ing om Sa elli e o Buffe and s o es in o ma ion
abou images in a log file, and, Las Bu e , which indica es he las image
o ans e ing om Buffe o Clien and makes he Coun e o calcula e he
bill. The s a ic ela ion be ween hese mRIs and he oles ha pe o m hem is
ep esen ed in he collabo a ion diag am in Figu e 1.
5 Modelling he P o ocol o a Role Model
Once he oles and i s mRIs ha e been iden ified we mus desc ibe how o se-
quence hem. Thus, he p o ocol o a ole model is defined as he se o sequences
o mRIs execu ion i may pe o ms. We can use wo equi alen ep esen a ions
o desc ibe he p o ocol o a ole model (see Figu e 2):
–Rep esen ing he p o ocol o he ole model as a se o FSAs, one o each
ole (see Figu e 3). Thus, in a ole model wi h N olesweha eNFSAs
Coun e
Sa alli e Bu e
Sa elli e
Images Role Model Images Role Model
Composi ion/
Decomposi ion
Clien
1,3,7,10
1,4,8,11
2,5,8,11
2,5,9,12
1,3,7,10
1,4,8,11
2,5,8,11
2,5,9,122,5,9,12
1
2
1
22
Coun e Clien
Bu e
10
11
12
10
11
1212
7
8
6
7
8
66
3
4
5
6
3
4
5
66
Role Reposi o y
Fig. 2. Composi ion/Decomposi ion o p o ocol o he Images ole model
Aiwhe e each Ai=(Si,Σ
i,δ
i,s
0
i,F
i), whe e Siis a se o s a es, Σiis a
ocabula y whe e each symbol σ∈Σi ep esen s an mRI, δi:Si×Σi→Si
is he ansi ion unc ion ha ep esen s an mRI execu ion, s0
i∈Siis a
ini ial s a e and Fi⊆Siis he se o final s a es. Thus, he se o wo ds
p oduced by his se o FSAs is se o possible aces o execu ion o mRIs.
All hisFSAsexecu esi s ansi ionscoo dina elyasi isshowninSec ion4.
Roughly speaking, when an mRI is execu ed by mo e han one ole we mus
pe o m a ansi ion in all o i s pa icipan oles. Each o hese ansi ions
ep esen s he pa o he mRIs ha each o hem pe o ms. Whe eby, o
execu e an mRI we mus ansi om one s a e o ano he in all he oles
ha pa icipa e in i .
–Rep esen ing he p o ocol o he ole model as a whole using a single FSA
o all he oles (see Figu e 4). This FSAs is o he o m B=(S, Σ, δ, s0,F)
whe e Sis a se o s a es ha ep esen s one s a e o each FSA o oles, Σ
is a ocabula y whe e each symbol σ∈Σ ep esen s an mRI, δi:S×Σ→S
is he ansi ion unc ion ha ep esen s an mRI execu ion, s0
i∈Siis he
ini ial s a e and F⊆Sis he se o final s a es. Thus, he se o wo ds
p oduced by his FSA is se o possible aces o execu ion o mRIs.
I we a e dealing wi h a new ole model, i may be mo e adequa e o use
a single FSA han one o each ole since we see he p oblem in a cen alised
manne . The p o ocol o he Images ole model by means o a single FSA is
showninFigu e4.
Once he p o ocol o all ole models in ou sys em ha e been desc ibed we
can syn hesise hose ole models ha a e in e ela ed. In ou example, bo h ole
models a e in e ela ed since he images ob ained in he Images ole model ha e
o be paid using he Pu chase ole model.
In o de o syn hesise ole models, we ha e o iden i y which oles a e ela ed
and we ha e o me ge hei p o ocols o c ea e he new syn hesised ole model. In
ou example, he syn hesised ole model Pu chase-Images ole model in Figu e
5 is build by c ea ing a new ole whe e he p o ocol o he Cus ome and he
Clien is me ged.
3
4
5
66
Ask
Send
Recei e
Las Sa
Las Bu e
Send
7
8
66
Ask Send
Las Bu e
10
11
1212
Ask Send
Las Bu e
1
22
Recei e
Las Sa
Sa elli e Bu e Clien Coun e
Recei e* · Las Sa Ask · (Send+Recei e)*·
· Las Sa · Send* · Las Bu e
Ask · Send*·
· Las Bu e
Ask · Send* · Las Bu e
Fig. 3. FSAs o oles o Images ole model
1,3,7,10
1,4,8,11
2,5,8,11
2,5,9,122,5,9,12
Ask
Send
Recei e
Las Sa
Las Bu e
Send
Fig. 4. FSA o Images ole model
Thus, we ha e o know he p o ocol o bo h he Cus ome and he Clien in
o de o build he new ole model. This can be done using he decomposi ion
ope a ion.
Once we ha e buil he p o ocol o he Clien /Cus ome ole, i is difficul
o in e men ally which shall be he p o ocol o he new syn hesised ole model.
Then, we can use he composi ion ope a ion o in e i . In addi ion, we can
pe o m deadlock es ing in o de o assu e he co ec ness o he new p o ocol
[25].
6 Composi ion and Decomposi ion o In e ac ion
P o ocols
These ope a ions pe o m a ans o ma ion om one ep esen a ion o p o ocol
o ano he . As i is shown in he ollowings sec ions, hese ope a ions do no
ake gua ds in o accoun . As we ha e shown abo e, a gua d allows agen s o
decide i hey wan o execu e an mRI o no . Thus, gua ds can make some
execu ion aces o he p o ocol impossible. Un o una ely, we canno de e mine
his a design ime. E en, i we a e dealing wi h adap i e agen s hese decision
can change a un ime. Thus, in bo h ope a ions, we wo k wi h he se o all
possible aces lea ing p oac i i y as a un ime ea u e.
6.1 Composi ion
The composi ion ope a ion is an algo i hm ha builds a ole model FSA om
a se o FSA o oles ob ained om a beha iou eposi o y o om syn hesis o
ole models.
To ep esen he ole p o ocol o each ole in a ole model we use he FSAs
Ai=(Si,Σ
i,δ
i,s
0
i,F
i)(i=1,2,...,N). Thus, he composi ion algo i hm is
defined as a new FSA o he o m B=(S, Σ, δ, s0,F), whe e:
–S=S1×...×SN,
–Σ=n
i=1 Σi,
–δ(a, (s1,...,s
n)) = (s
1,...,s

N)iff∀i∈[1..N]·(a∈ Σi∧si=s
i)∨
∨(a∈Σi∧δ(a, si)=s
i),
–s0=(s0
1,...,s
0
N), and
–F=F1×...×FN.
This algo i hm builds he new FSA explo ing all he easible execu ions o
mRIs. Thei s a es a e compu ed as he ca esian p oduc o all s a es. Each
s a e o his FSA is o med by a N- uple ha s o esas a eo each ole.To
execu e an mRI, we ha e o p e o m i om a uple-s a e whe e he mRI can
be execu e o change o a new uple-s a e whe e he s a es o oles implied in
he mRI shall only change. Thus, o each new uple-s a e we check i an mRI
may be execu ed (all hei oles can do i om i s co esponding s a e in he
uple-s a e); i so, we add i o he esul . Finally, he final s a e o he ole
model FSA is o med o all possible combina ions o final s a es o each Aiand
he ini ial s a e is a uple wi h he ini ial s a e o each Ai.
In ui i ely, i is easie o comp ehend a p o ocol i i is desc ibed by means
o a single FSA han i we use a se o hem. Fu he mo e, we can pe o m
deadlock es ingoni oassu e ha hesyn hesisweha emadeisdeadlock ee
and esul s in wha we ha e hough when we syn hesised hem. Fu he mo e,
his ep esen a ion is easie o unde s and han se e al sepa a ed FSAs. Wi h
his ope a ion, we can ob ain au oma ically he FSA in Figu e 4 ha ep esen s
he p o ocol execu ed by he FSAs in Figu e 3 o Images ole model.
6.2 Decomposi ion
To ob ain he p o ocol o a ole we mus ake in o accoun he mRIs a ole execu e
only. Tha is o say, we can ake all he possible aces ha he FSA o he ole
model p oduces and igno e he mRIs ha he ole does no execu e. Fo ins ance,
i we ake he a ace (Ask, Recei e, Recei e, Send, Las Sa , Send, Las Buffe )
om he FSA o he Images ole model, he ace ha he ole Sa elli e execu es
is (Recei e, Recei e, Las Sa ) since i pa icipa es only in mRIs Recei e and