Towards Interaction Protocol Operations for Large Multi-agent Systems

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