Controller synthesis of service contracts with variability

Contents lists available atScienceDirect

Science

of

Computer

Programming

www.elsevier.com/locate/scico

Controller

synthesis

of

service

contracts

with

variability

Davide Basile

a

,

c

,

∗

, Maurice

H. ter Beek

a

, Pierpaolo Degano

b

,

Axel Legay

d

,

Gian-Luigi Ferrari

b

,

Stefania Gnesi

a

, Felicita Di Giandomenico

a

a_{ISTI–CNR,Pisa,Italy} b_{UniversitàdiPisa,Italy} c_{UniversitàdiFirenze,Italy}

d_{UniversitéCatholiquedeLouvain,Belgium}

a

r

t

i

c

l

e

i

n

f

o

a

b

s

t

r

a

c

t

Articlehistory:

Received8June2018

Receivedinrevisedform18July2019 Accepted29October2019

Availableonline4November2019

Keywords:

Supervisorycontroltheory Contractautomata Serviceorchestrations Variability

Behaviouralvariability

Service contracts characterise the desired behavioural compliance of a composition of services. Compliance is typically defined by the fulfilment of all service requests through service offers, as dictated by a given Service-Level Agreement (SLA). Contract automata are a recently introduced formalism for specifying and composing service contracts. Based on the notion of synthesis of the most permissive controller from Supervisory Control Theory, a safe orchestration of contract automata can be computed that refines a composition into a compliant one.

To model more fine-grained SLA and more adaptive service orchestrations, in this paper we endow contract automata with two orthogonal layers of variability: (i) at the structural level, constraints over service requests and offers define different configurations of a contract automaton, depending on which requests and offers are selected or discarded, and (ii) at the behavioural level, service requests of different levels of criticality can be declared, which induces the novel notion of semi-controllability. The synthesis of orchestrations is thus extended to respect both the structural and the behavioural variability constraints. Finally, we show how to efficiently compute the orchestration of all configurations from only a subset of these configurations. A prototypical tool supports the developed theory.

©2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).

1. Introduction

Servicecomputingisawell-knownparadigmforthecreation,publication,discoveryandorchestrationofservices,which are autonomous,platform-independentandreusable piecesof softwarethat are looselycoupled intonetworksof collab-orating end-user applications [1,2]. Servicesare usuallyprogrammed withlittleorno knowledgeaboutclients andother services.Theyarecreatedandpublishedbypossiblymutuallydistrustedorganisations,andmayhaveconflictinggoals. Ser-viceshavetocooperate toachieveoverallgoalsandatthesametimecompete toperformspecifictasksoftheirorganisation. Ensuringreliabilityofacompositeserviceisimportant,e.g.toavoideconomicloss.Therefore,understandingandfulfillinga minimalnumberofbehaviouralobligationsofservicesiscrucialtodeterminewhethertheinteractivebehaviouris consis-tentwiththerequirements.Suchobligationsareusually dictatedbyaService-LevelAgreement(SLA).Recently,theService

*

Correspondingauthorat:UniversitàdiFirenze,Italy.

E-mailaddress:davide.basile@isti.cnr.it(D. Basile).

https://doi.org/10.1016/j.scico.2019.102344

0167-6423/©2019TheAuthors.PublishedbyElsevierB.V.ThisisanopenaccessarticleundertheCCBYlicense (http://creativecommons.org/licenses/by/4.0/).

Fig. 1. Two automata (left and middle) and a possible composition of them (right).

ComputingManifesto [3] considers servicedesign asoneofthefouremerging researchchallengesinservicecomputingfor thenext10 years,andcallsforformalmodelssupportingit:

“Service systems have so farbeen built without an adequate rigorous foundation that would enable reasoning about them.[. . . ]Thedesignofservicesystemsshouldbuilduponaformalmodelofservices.”

Servicecontractsoffermeanstoformalisetheexternallyobservablebehaviourofservicesintermsofoffers oftheservice andrequests bytheservicetobematched.Thenotionofagreement characterisescomplianceof(acompositionof)contracts and it isbased on thefulfilment ofall service requests through corresponding serviceoffers. Behaviourin agreement is implemented by an orchestration of services.Orchestrations mustdynamically adapt tothe discovery of newservices,to serviceupdatesandtoservicesthatarenolongeravailable.Moreover,aprecisesemanticsofservicecontractsallowsusto mechanicallyverifythatanorchestrationenjoys certainpropertiesandtoassesswhetheritsatisfiesagivenSLA. Werefer thereaderto [4,5] forsurveysonformalmodelsofservicecontracts.

Contractautomata [6] areonesuch formal modelforservicecontracts. Acontractautomatonrepresentseitherasingle service(inwhichcaseitiscalledaprincipal)oramulti-partycompositionofservices.Eachprincipal’s goalistoreachan acceptingstatebymatchingitsrequestactions(oftheforma,b,. . . )withcorrespondingofferactions(oftheforma,b,. . . ) ofother principals.Serviceinteractionsare implicitlycontrolled byan orchestratorsynthesisedfromtheprincipals,which directs theminsuch awaythatonly finiteexecutionsinagreementactually occur,i.e.such thateach requestactiona is

fulfilledbyanofferactiona.Technically,suchanorchestrationissynthesisedasthemostpermissivecontroller (mpc)known fromSupervisoryControlTheory(SCT) [7,8].The goalofthispaperistopresentaricherframeworkofcontractautomata, whichallowstheusertomodelmorefine-grainedSLAandmoreadaptiveserviceorchestrations.

Considertwoautomatainteractingonaserviceactiona,depictedinFig.1(leftandmiddleparts),andacompositionof theseautomatainFig.1(rightpart)thatmodelstwopossibilitiesoffulfillingservicerequesta fromtheleftmostautomaton by matchingit witha serviceoffera ofthemiddleone(i.e.

(

a

,

a

)

).Assumethat a mustbe matchedwitha toobtainan agreement, andthat forsome reasonstate is to beavoided in favourofstate



.Inmost automata-basedformalisms, includingthecontractautomataof [6,9],thisistypicallynotallowedbythedefinitionofcompositionandtheresultingmpc isempty.Indeed,wewouldliketobeabletoexpressthata musteventuallybematched,ratherthanalways.Inthispaper, we introduce atype ofcontract automata inwhichit ispossible toorchestratethe composition ofthetwo automataon theleftinsuchawaythattheresultistheautomatonontherightwithoutstate ,i.e.a isonlymatchedwitha after the

occurrenceofanunmatchedserviceofferb ofthemiddleautomaton(i.e.

(

•,

b

)

).

Technically,weextendcontractautomatawithactionmodalitiestodistinguishnecessary frompermitted servicerequests (borrowedfrom [9])andwithtwonovelorthogonalvariability mechanisms.Necessaryandpermittedrequestactionsdiffer inthatthefirstmust befulfilled,whilethesecondmay alsobeomitted.Thenotionsofnecessaryandpermittedmodalities stem frommodalanddeonticlogic,which traceback toseminalwork byVonWright [10,11]. Asin [9], weassume offer actionstoalwaysbepermittedbecauseaservicecontractmayalways withdrawitsoffersnotneededtoreachanagreement. The first variability mechanism is defined inside service contracts, i.e. at the behavioural level, to declare necessary request actionstobe eitherurgent orlazy. Thesemodalitiesdrivetheorchestratortofulfil alltheoccurrences ofan urgent action,whileitisrequiredtofulfil atleastoneoccurrence oflazyactions.Thesimpleexampleabovehasnourgent action; theonlynecessaryoneisthelazyrequesta.Intuitively,thematchingofalazyrequestmaybedelayedwhereasthisisnot thecaseforurgentrequests.

Thesecondvariabilitymechanismconcernsconstraintsthatoperateontheentireservicecontractandthataredefinedat thestructural level.Theyareusedtodefinedifferentconfigurations,whichisimportantbecauseservicesaretypicallyreused inconfigurationsthatvaryovertimeandtoadaptthemtochangingenvironments [3].Configurationsarecharacterisedby which serviceactions are mandatory and whichforbidden. The valid configurations are those respecting allthe structural constraints.Wefollowthewell-establishedparadigmofSoftwareProductLineEngineering(SPLE),whichaimsatefficiently managing a familyof highly (re)configurable systemsto allow for mass customisation [12,13]. Tocompactly represent a

productline, i.e. the set of valid product configurations, we use a so-called featureconstraint, a propositional formula

ϕ

whoseatomsarefeatures [14–16] andweidentifyfeaturesasserviceactions(offersaswellasrequests).

Toeffectivelyusethesetwovariabilitymechanisms,we refinetheclassicalsynthesis algorithmfromSCT.Wecompute orchestrations,intheformofanmpc,ofasinglevalid configuration,i.e.suchthatitincludesallmandatoryactionsandnone oftheforbidden,besidesfulfillingallnecessaryrequestsandthemaximal numberofpermittedrequests.Heremaximalis tobeunderstoodinthesensethatiftheorchestrationweretofulfil anotherpermittedrequest,thenthiswouldcauseone of the other requirements to no longer be fulfilled. An importanttechnical resultof thispaper is that we can compute the orchestration ofa product linewithout computingthe mpcfor eachof its validproduct configurations;it suffices to

computeasmallselectedsubsetofvalidconfigurations.Thisguaranteesefficiencyandscalabilityofournovelframeworkof contractautomata.

Summarising,themaincontributionsofthispaperareasfollows:

1. Anovelformalismforservicecontracts,calledFeaturedModalContractAutomata (FMCA),whichofferssupportfor struc-turalandbehaviouralvariabilitynotavailableintheliterature.

2. The newnotionof semi-controllability (relatedto lazy actions), whichrefines both those ofcontrollability (relatedto permittedactions)andofuncontrollability(relatedtourgent actions)usedinclassicalsynthesisalgorithms fromSCT. ThisnotionisfundamentaltohandledifferentservicerequestsintheorchestrationsynthesisforFMCA.

3. Arevisedalgorithmforsynthesisinganorchestrationofservicesforasinglevalidproduct.

4. An algorithm for computingthe orchestration of an entireproduct line by joining the orchestrationsof a small se-lected subsetofvalidproducts.It isworth notingthat thenumberofvalidproductsis exponentialinthenumberof features [17],thusonlyusingfewofthemgreatlyimprovesperformance.

5. Theopen-sourceprototypicaltoolFMCATimplementingourproposal.1

Outline In Section 2, we introduce our running example, a Hotelservice product line, and briefly survey and evaluate ourtoolFMCAT.Weformally defineFMCAinSection 3,includingcomposition,projection andcontrollability.InSection 4, we define the synthesis algorithms for FMCA. Twonotions neededto efficiently compute the orchestration of an entire productlinefollowinSection5,introducingso-calledautomatarefinement,andSection6,providingameansto(partially) order the products of a product line. In Section 7, we discuss related work, followed by our conclusions in Section 8. All proofs of the results presented in this paper are in AppendixA.

2. Motivatingexample:hotelreservationsystemsproductline

A(software)productline isa setof(software-intensive)products in aportfolio ofamanufacturer (or softwarehouse) that share common features andthat are, ideally, built froma set of reusable (software) components by means of well documented variability [12,13].A feature representsan abstractdescription offunctionalityandafeature modeltypically providesadescriptionofproductsintermsoffeatures:eachproduct isthusuniquelycharacterisedbyasetoffeatures.Itis wellknownthataproductcanberepresentedbyaBooleanassignmenttothefeatures(i.e.selected

=

trueanddiscarded

=

false)andafeaturemodelcanthusberepresentedbywhatwecallafeatureconstraint inthispaper(i.e.aBooleanformula overthefeatures).Asamatteroffact,checkingifaproductrespectstheconstraintsexpressedbyafeaturemodel,i.e.ifit isvalid,reducestoaBooleansatisfiabilityproblemthathasefficientsolutions [14–16].

2.1. Thehotelreservationsystemsproductlineanditsfeatureconstraint

Weillustrateourapproachwithaproductlineofabasicfranchiseofhotelreservationsystems.Weconsiderthreetypes ofservicecontracts:a Hotel andtwo clients,called BusinessClient and EconomyClient,each withdifferentservicerequests andoffers,andwithitsownfeatureconstraint.Asystemisacompositionofthesecontracts,e.g. BusinessClient

⊗

Hotel

⊗

EconomyClient, andthe feature constraint ofthe Hotel service product lineis the conjunction ofthe feature constraints of the individual contracts. The 10 features concern requesting/offering a singleRoom or sharedRoom, privateBathroom or sharedBathroom, paymentby card or cash,its confirmation by invoice or receipt, andthepossibility of freeCancellation or noFreeCancellation.Furthermore, card and cash arealternative featuresandtherearetwoadditionalconstraints: invoice is selectedincase cash isselectedand sharedBathroom incase sharedRoom is.Theresultingfeatureconstraint

ϕ

oftheHotel serviceproductlineisasfollows,where

⊕

denotesexclusiveor and

F

thesetoffeatures:

ϕ

= (

card

⊕

cash

)

∧ (



f∈F,f∈{/card,cash}

f

)

∧ (

cash

→

invoice

)

∧ (

sharedRoom

→

sharedBathroom

)

2.2. Thevalidproductsofthehotelreservationsystemsproductline

Asalreadysaid,aproduct p assignsaBooleanvaluetoeachfeature,andtheatomsofafeatureconstraint

ϕ

mappedby

p totrue(false,resp.)arecalledmandatory (forbidden,resp.).

Usually,inSoftwareProductLineEngineering(SPLE),eachfeatureiseitherselectedordiscardedtoconfigureaproduct. Inotherwords,allvariabilityisresolvedandtheinterpretationoftheatomsof

ϕ

istotal.Here,instead,weconsiderasvalid productsalsoso-calledsub-families (inSPLEterms),whicharedefinedbyapartial assignmentsatisfying

ϕ

(seethecomment afterthe4products below).Thisenablesustosynthesisetheorchestrationofanentireproductlineby consideringafew validproductsonly,ratherthancomputingall validones.Thisisoneofthemainresultsofourpaper,presentedinSection6.

Table 1

ClassificationofbasicactionsofFMCA distin-guishingamong offers/requests (||), permit-ted/necessary ( )andlazy/urgent (|).

offers requests

permitted necessary

lazy urgent a a3 a2 a2u

Fig. 2. The automaton for BusinessClient. (For interpretation of the colours in the figure(s), the reader is referred to the web version of this article.) Togive an ideaoftheimpact ofourimprovement,itsufficesto notethat whenno variabilityisleft,the feature con-straint

ϕ

characterises288 productconfigurations,eachrepresentinga differentinstantiationofall itsfeatures.When the assignment isinsteadpartial, asin ourcase,there are4860 validproducts, butwewill showbelowthat only4 ofthem suffice tocharacterise the orchestration ofthe entireHotelserviceproduct line. It iseasy to imagine that forreal-world featuremodelsofuptomillionsofconfigurationsthegainisconsiderable,confirmingthescalabilityofourapproach.

We partiallyordervalidproducts bystipulating p1



p2 ifandonlyifthesetsofmandatoryandforbiddenfeatures of

p2areincludedinthoseof p1.Accordingly,themaximalproducts arethevalidproductsmaximalin



(cf.Definition17in

Section6).The4maximalproductsof

ϕ

(outof4860)havethefollowingsetsofmandatory(R)andforbidden(F)features.

R

: [

cash

,

invoice

,

sharedBathroom

];

F

: [

card

]

(product P4854)

R

: [

cash

,

invoice

];

F

: [

card

,

sharedRoom

]

(product P4857)

R

: [

card

,

sharedBathroom

];

F

: [

cash

]

(product P4858)

R

: [

card

];

F

: [

cash

,

sharedRoom

]

(product P4859)

Apartialassignmentthatinterpretstheelementsof R astrue,thoseof F asfalseandalltheothersas“don’tcare”satisfies

ϕ

(cf.Definition11inSection4).Indeed,whicheverBooleanvaluereplaces“don’tcare”leavestheformulasatisfied.

2.3. FMCA:behaviouralrepresentationsofthehotelreservationsystems

Asmentionedabove,afeatureconstraint

ϕ

describesallthevalidproductsofaproductline.However,ithasno imme-diate operationalinterpretation,intermsoftheactionsthattheprincipalsinvolvedinacontracthavetoperforminorder to achievetheir goals.Weaddressthisoperationalaspectby usingtheaforementionedformalism ofFMCA,whichextend the modelin [9]. The composition oftwo FMCA isitself an FMCA (see below)andit representsthe composition oftwo servicecontracts.

Each FMCA

A

isa pairmade of a specialfinite state automatonand a feature constraint

ϕ

, whichis related to the automaton in the following way. The labels on the arcs of the automaton identify the actions for requests and offers, a subset of whichcorresponds to all features in

ϕ

.We say that

A

respects a product p whenever all features declared

mandatory (forbidden, resp.)by p correspondtoactions thatare reachable(unreachable,resp.)fromtheinitial state of

A

(cf.Definition18inSection6).

Moreover, each automaton describesa contract where the actions corresponding to offers are overlined and those to requests arenot.Offers areallconsidered permitted, whilerequestsareeitherpermitted ornecessary atdifferentdegrees, namelyurgent or lazy (cf.Table 1andDefinition2inSection 3).In thisway,besides expressingthata requesthastobe matched(byanoffer),onecanalsospecifytowhatextentthismustoccur,i.e.whethertherequestmustalways (anurgent

request)oreventually (alazy request)bematchedinacontract.Thebehaviourof

A

isthelanguageitaccepts.

Wenowspecifytheautomataofthethreeservicecontractsintroducedinthebeginningofthissection.Actually,wewill illustrate differentbehavioural descriptions.Notationally, permitted actionslabel dottedarcs,suffixed by

3

,while urgent and lazyrequests label(red andgreenin thepdf)full arcs andare suffixedby

2

u and

2

,respectively (cf.Table 1and Fig.2).

The automaton in Fig. 2 provides the behavioural description of service contract BusinessClient, in which a business clientclassifiestherequestforaroomasurgentandtherequestfortheinvoice aslazy;allother actionshavean obvious meaningandarepermitted.

The automatonin Fig. 3 describesthe Hotel behaviour. It hasseveral points of non-determinism to complywith the requests of a BusinessClient as well asthose of an EconomyClient. It also has cyclic behaviour enabling it to start new interactionswithdifferentclients.Finally,thehoteloffersfreebreakfast(actionfreebrk

3

)orrequirestofillacaptcha(action

captcha

3

) toclients that payby cardandrequestan invoice (for thesake ofexample), althoughnot all oftheseactions havecorrespondingfeatures.

Fig. 3. The automaton for Hotel.

Fig. 4. The automaton for EconomyClient.

Fig. 5. Orchestration of composition BusinessClient⊗Hotel⊗EconomyClientof the three automata in Figs.2,3and4for the product P4858.

The EconomyClient contract,depictedinFig.4,issimilartoitsbusinesscounterpart,butthesingleroomrequestislazy.

Optionallyasharedroomisrequestedinsteadofasingleroom,andasharedbathroomisrequested.

Composition oftwo FMCA is similar to standard automata composition, except that one’s request actions have to be matchedby the other’scorresponding offers, ifavailable.Inspecting thecomposition, wecan determinewhetherservices are compliant, inthe sense that all requestsare fulfilled(i.e., matchedby offers). Additionally, we can furtherrefine the compositionsothatonlycompliantbehavioursarepossible,asillustratedinSection2.4.

2.4. Orchestrationsofthehotelreservationsystemsproductline

We intuitively show how tosynthesise the orchestrationsof the products of a product line, again inthe form of an FMCA.Theorchestrationofaproduct p isdefinedasthelargestsub-portionof

A

inagreement,i.e.allrequestsarematched bycorrespondingoffers,andrespecting p.Below,wediscusssomeexamplesofstructuralandbehaviouralvariability.

Consideringmandatoryandforbiddenfeatureconstraints We firstillustratestructuralvariability. Westart bycomputingthe orchestrationofthecomposition

A

=

BusinessClient

⊗

Hotel

⊗

EconomyClientforproduct P4858,i.e.themandatoryfeatures cardand sharedBathroom are selectedwhilst theforbiddenfeature cash isdiscarded. Theorchestration isinFig.5,where all requestsarematched bycorresponding offers.No interleavingofactionsfromeithercomponentcanoccur (except for

Theorchestrationof

A

forproduct P4859 isthesameasinFig.5,butwithstate

qB3

,

qH8

,

qE8

anditsincident transi-tionsremoved.Indeed,inthisproductthefeature sharedRoom isdiscarded,andhencesoisthetransitionlabelledbyaction

sharedRoom leadingto

qB3

,

qH8

,

qE8

.

TheHotelserviceproductlinehasonlytwomaximalproductsin



thathavenon-empty orchestrations,namely P4858 and P4859.Instead,products P4854 and P4857 haveempty orchestrations.Indeed,nocashpaymentiseverperformedby eitherclient(recallthatforboth cash and invoice aremandatory,while card isforbidden).Inaddition, invoice isunreachable (intheclients’contracts),because card isforbidden.

Notethatmandatoryandforbiddenfeatureconstraintsaremoredemandingthanimposingarequestactiontobe neces-sary:thefeatureconstraintsofaproductareglobaltoawholeFMCA,whilenecessaryrequestsarelocaltoitstransitions. More indetail,ifan actioncorresponding toa mandatoryfeature isunreachable, thenagreementis violated(see above). Instead,unreachablenecessaryrequestsdonotspoilcontractagreement.

Theorchestrationofaproductlineistheunion(inautomatatheoryterms)oftheorchestrationsofitsproducts.Amain resultofthispaperisbasedonthenotionofcanonical product,requiringittohavenon-emptyorchestrationandtosatisfy a furthermild condition ofits forbiddenactions (cf.Definition 19in Section6). Wecan compute theorchestration

O

of a product lineas the unionof those of its canonical products, only, because all the orchestrations ofthe non-canonical products aresub-automataof

O

.Inourexample,theorchestration

O

oftheHotelserviceproductlineistheunionofthe orchestrationsofthetwocanonicalproducts P4858 and P4859.

Consideringnecessaryactionrequests Wenowcontinuebyillustratingbehaviouralvariability.Wefirstdiscusswhyoffersare alwayspermitted.Iffreebreakfastwereanecessaryofferin Hotel,thenwewouldhavetheunrealisticscenarioinwhichthe hotelcontractrejectsallclients’contracts.Indeed,noagreementwouldbereachedbecauseintheclients’contractsthereis nofreebreakfastrequesttomatchtheoffer.

Nextweconsideracompositionofthe Hotel servicewithbothtypesofclientsandweshowhowurgentrequestscanbe usedforenforcingprioritiesamongservicerequests.Tothebestofourknowledge,thisisnotpresentinanyautomata-based formalisms.

In the following, orchestrations always refer to product P4858. If EconomyClient is served before BusinessClient, i.e.

(

EconomyClient

⊗

Hotel

)

⊗

BusinessClient(wewillseelaterthat

⊗

isnon-associative),thenbothlazymatches

ta

= (

qE0,H0,B0

, (

singleRoom

,

singleRoom

,

•)2



,



qE7,H6,B0

)

tb

= (

qE0,H0,B0

, (

sharedRoom

,

sharedRoom

,

•)2



,



qE8,H8,B0

)

arepresentinthecomposition,sopreventingtheurgentmatch

tc

= (

qE0,H0,B0

, (

•,

singleRoom

,

singleRoom

)

2

u

,



qE0,H6,B6

)

Theabsenceoftheurgentmatchcausestheresultingorchestrationtobeempty.Intuitively,itshouldbetheconverse:the business clientshould beserved before theeconomyclient (i.e.tc instead ofta ortb). Inthat case,i.e.

(

BusinessClient

⊗

Hotel

)

⊗

EconomyClient,theredoesexistanon-emptyorchestrationrespectingabusinessclient’spriority(cf.Fig.5).

2.5. ModellingandanalysingwiththeFMCATtool

We implemented inJavaa prototypicaltool calledFMCA Tool(FMCAT) that supports thedefinitionof FMCAandthat synthesisesitsorchestrationintermsofitsmpc.Itisopen source,andavailableathttps://github.com/davidebasile/FMCAT, including themodels usedin thispaper.FMCAT buildson CAT [18],a tool forcontract automata,andit offersthe func-tionalities described below. Our tool exploits FeatureIDE [19], an open-source framework for feature-oriented software developmentbasedonEclipse,offeringdifferentfeaturemodeleditingandmanagementtools.

ModellingwithFMCAdecouplestasksofsoftwareengineersfromtasksofexpertsinformalmethods.Indeed,the syn-tacticdescriptionofaproductlineasafeaturemodel(interpretedasfeatureconstraint)andthedescriptionofitssemantics asanautomatonareseparateconcerns.Byseparatingthem,asoftwareengineercanfocusondesigningafeaturemodeland its validproducts,leavingthetaskofspecifyingtheoperationalsemanticstoanexpertinformalmodelling.Subsequently, thesetwoaspectscanbeseamlesslyintegratedinthesameFMCA,makingitpossibletodetectinconsistenciesbetweenthe syntactic andsemanticlevels ofthesame formalism.Ingeneral, a softwaredesigner wouldliketominimise thenumber of productconfigurationsthat donot admitsafebehaviour (i.e.empty orchestrations).Indeed,validproducts withempty orchestrationsare such thatthesyntactic constraintsprovided bythefeature modelarenot fulfilledby theirbehavioural descriptions.Byinspectingtheorchestrationoftheproductline,onecandetectallproductswithnosafebehaviour(inthe formofcompliantservices).Ifthereareany,oneeitheramendsthefeaturemodelortheirbehaviouraldescriptionsoasto obtainnon-emptyorchestrations.

Consider oncemoretheaboveexample.Thefeature constraint

ϕ

ofthe Hotelserviceproductlineforcesaninvoice to be emitted in caseofcash payments,andidentifies cash andcard paymentsastwo alternative features. Whenthe cash featureisselected,itrequiresalsotheinvoicefeaturetobeimplementedwhileatthesametimethecardfeaturemustnot beimplemented.However,inthebehaviouraldescriptionofthe Hotel serviceinFig.3,aninvoiceisemittedonlyforcredit

Table 2

Resultsabouttheexpressivenessoflazytransitions. Num. states Num.lazy transitions Num.states ofencoding

BusinessClient⊗Hotel⊗EconomyClient 343 143 343× (2143

)+1

BusinessClient⊗Hotel 54 9 54× (29₎₊₁

EconomyClient⊗Hotel 47 10 47× (210₎₊₁

(BusinessClient⊗Hotel)⊗EconomyClient 340 144 340× (2144₎₊₁

(EconomyClient⊗Hotel)⊗BusinessClient 278 106 278× (2106₎₊₁

cardpayments,whereasamerereceiptisprovidedincaseofcashpayments.Asaresult,themaximalproducts P4854 and P4857arenot canonicalbecausethey requirethe cash featuretobeimplemented.Onecanfixthisinconsistencybetween

ϕ

andthe behaviouraldescriptionby eitherremoving theconstraintcash

→

invoicefrom

ϕ

orby swappingreceipt with invoice inthe Hotel automaton.

Notethatfordetectingpossibleinconsistenciesofthiskinditsufficestoonlyinspectthemaximalproducts(hereonly 4), insteadofallproductconfigurations(here288)withatotalBooleanassignment.

2.6. Evaluation

To further corroborate our proposal, we provide an evaluation of the two main innovations proposed by FMCA: be-haviouralandstructuralvariability.

Set-upoftheevaluation We briefly evaluate FMCA usingFMCAT (build June 2019). The evaluationwas carried out on a machinewithProcessorIntel(R)Core(TM)i7-8700CPUat3.20 GHz,3192 MHz,6 Core(s),12 LogicalProcessor(s)with16 GB ofRAM,running64-bitWindowsVersion 10.0.17134build 17134.

Evaluatingbehaviouralvariability Firstweevaluatebehaviouralvariability,andinparticularthegaininexpressivenessdueto thenovelnotionofsemi-controllability.WewillinformallysketchanencodingofanFMCAintoonewithoutlazytransitions andestimatethedifferencesinthestatespacesofthetwomodels.

AsstatedinSection1,whilepermittedandurgentactionsarerelatedtothenotionsofcontrollabilityand uncontrollabil-ityofSCT [7,8],respectively,lazyactionsarerelatedtoanovelnotioncalledsemi-controllability.Werecallthatalazyrequest musteventuallybematched,ratherthanalways,asisthecaseforurgentrequests.Indeed,alazyrequestallowstomodela frequentscenarioincontractswherethesatisfactionofanecessaryrequestcanbedelayed,asincaseoftheroomrequest of EconomyClient.Whilethesynthesis algorithmcannotprune“bad”urgenttransitions,itcanprune“bad”lazytransitions aslongasthereexistsanotherlazytransitionwherethesamerequestismatched(cf.Section4).Notethat ingeneralitis notpossibletoknowaprioriwhetheratransitionisbadornot,becausethisdependsonthegivenrequirementstoenforce (e.g.agreement,forbiddenandrequiredactions).

Hence,the encoding

A

ofan FMCA

A

containing n lazytransitionsistheunionof2n automatathat areobtainedby allpossiblecombinationsofpruningasubsetofthen lazytransitionsof

A

andturningtheremaininglazytransitionsinto urgent.One ofsuchcombinationswill pruneexactlythesametransitionspruned bythesynthesis andthustheresulting orchestrationof

A

 willcontaintheorchestration oftheoriginal automaton

A

,amongothersthat arenotmaximally per-missive.Inthe worst-casescenario,thenumberofstatesoftheencoding

A

 willbe thenumberofstatesoftheoriginal automaton

A

multipliedby2n,plusanadditionalnewinitialstate.

FMCAThasbeenequippedwithafunctionalitythatestimatestheworst-casenumberofstatesoftheencodingdiscussed above.Table2reportstheresultsofthetoolforthecompositionsdiscussedinthissection.Foreachautomatonwedisplay thenumberofstates,thenumberoflazytransitionsandanestimationofthenumberofstatesoftheencoding.Asexpected, the resultsshow that in the worst casethere isan exponentialgrowth in thenumber ofstates ofthe automata,which quicklymakestheiranalysisandusagenon-tractable.

Concluding,thepossibilityoffered byFMCA ofprimitivelyexpressingnecessaryrequests thatmusteventually be satis-fied allows to reduce the numberofstates by an exponential factor withrespect toother formalismsthat only support controllableanduncontrollableactions.

Evaluatingstructuralvariability WenowevaluatethestructuralvariabilityofFMCA,andinparticulartheintroductionofa partialorderofproductstoreducethenumberofconfigurationsusedtocomputetheorchestration(i.e.themostpermissive controller) ofthefamily. Whilethe literature containsother attempts atsynthesisingthemostpermissivecontroller ofa productline [20,21] (cf.Section7),theserequiretocompute themostpermissivecontrollerforeachproduct(inwhichall variabilityhasbeenresolved)withoutordering theproducts.Ontheotherhand,FMCAonlyconsiders canonicalproducts. Asshownintheremaining partofthissection, orderingtheproducts allowstoimprovetheperformance andreducethe statespace.ToevaluatethebenefitsintroducedbyFMCA,FMCATwasequippedwithafunctionalityforcomputingthemost permissivecontrollerofafamilywithorwithouttakingadvantageofsuchpartialorderofproducts.

The resultsaredisplayed in Table3.The table reportsforeachautomaton thenumberofstates andthetime needed by FMCAT to compute it. It also reportsthe number of configurations for which an orchestration has been synthesised

Table 3

ResultsoftheevaluationperformedwithFMCAT.

Num. states Time (ms) Num. configurations Used configurations

BusinessClient⊗Hotel⊗EconomyClient 343 71 – –

BusinessClient⊗Hotel 54 9 – –

EconomyClient⊗Hotel 47 6 – –

(BusinessClient⊗Hotel)⊗EconomyClient 340 55 – –

(EconomyClient⊗Hotel)⊗BusinessClient 278 22 – –

KBusinessClient⊗Hotel⊗EconomyClientP4858 14 875 1 P4858

KBusinessClient⊗Hotel⊗EconomyClientP4859 13 580 1 P4859

K(EconomyClient⊗Hotel)⊗BusinessClientP4858 0 337 1 P4858

K(BusinessClient⊗Hotel)⊗EconomyClientP4858 14 598 1 P4858

OBusinessClient⊗Hotel⊗EconomyClient 28 3220 4 P4858, P4859

O(EconomyClient⊗Hotel)⊗BusinessClient 0 950 4 –

O(BusinessClient⊗Hotel)⊗EconomyClient 28 2796 4 P4858, P4859

OBusinessClient⊗Hotel⊗EconomyClient without PO 55 129600 288 P86, P94, P182, P190

O(EconomyClient⊗Hotel)⊗BusinessClient without PO 0 60186 288 –

O(BusinessClient⊗Hotel)⊗EconomyClient without PO 55 130994 288 P86, P94, P182, P190

andtheconfigurationsforwhichtheorchestrationisnon-empty.Theselasttwocolumnsarerelevantwhencomputingthe orchestrationofthefamily.Thefirstsixrowsreportthevariouscompositionsusedinthissection.Thenextfourrowsreport theorchestration ofthesecompositionsfora specificproduct(denotedas

K

_Ap,where

A

isthecompositionand p isthe product).ThesearetheorchestrationsdiscussedinSection2.4.Thenextthreerowsreporttheorchestrationofthefamilyfor thevariouscompositions,byexploitingthepartialorderofproducts.Inthiscase,thecomputationonlyrequirestoanalyse thefourcanonicalproducts.Aspreviously discussed,products P4858 and P4859 aretheonlytwocanonicalproducts used intheorchestrationofthefamily.Finally,theremainingthreerowsdisplayonceagaintheorchestrationofthewholefamily, butthistimewithoutexploitingthepartialorder.Inthislastcase,computingtheorchestrationrequirestoanalysethe288 productsoriginallygeneratedbyFeatureIDE,wherethosewithnon-emptyorchestrationsare:

R

:

F

\

F

;

F

: [

cash

,

receipt

,

sharedRoom

,

freeCancellation

]

(product P86)

R

:

F

\

F

;

F

: [

cash

,

receipt

,

freeCancellation

]

(product P94)

R

:

F

\

F

;

F

: [

cash

,

sharedRoom

,

freeCancellation

]

(product P182)

R

:

F

\

F

;

F

: [

cash

,

freeCancellation

]

(product P190)

These four products are indeed those generating the orchestration of the familywithout exploiting the partial order. In particular, the orchestrationsfor products P182 and P190 areidentical tothose of products P4858 and P4859.However, theorchestrationofthefamilyalsoincludestwonon-relevantproducts,namely P86 and P94.Indeed,theorchestrationsof products P86 and P94 areincludedinthoseofproducts P182 and P190,andthusarenotsignificantforcharacterisingthe orchestrationofthefamily.

Concluding,theexperimentsempiricallyshowthatFMCA,andinparticulartheirpartialorderofproducts,reducesboth thestatespaceoftheorchestrationofthefamilyandthetimeneededtocomputeitsorchestration.

3. Featuredmodalcontractautomata

WenowformallydefineFeaturedModalContractAutomata(FMCA),borrowingthefollowingnotationfrom [6,22].Inour framework, wedistinguishbasicactionsbelongingtothesetsofrequests R

= {

a

,

b

,

c

,

. . .

}

andoffers O

= {

a

,

b

,

c

,

. . .

}

where R

∩

O

= ∅

.Thealphabetofbasicactions isdefinedas



=

R

∪

O

∪{•}

where

•

∈

/

R

∪

Oisadistinguishedelementrepresenting theidle move.Wedefinetheinvolutionco

: 

→ 

suchthat(abusingnotation)co

(

R

)

=

O,co

(

O

)

=

Randco

(

•)

= •

.

Let v



= (

e1

,

...,

en

)

bea vector ofrank rv

=

n

≥

1,andlet v(



i) denote theith element with1

≤

i

≤

rv.By v



1



v2

· · · 

vm we denotetheconcatenationofm vectors



vi.Fromnowonwards,westipulatethatinanactionvectora there



iseithera single offerorasingle request,orasingle pairofrequest-offerthatmatch,i.e.thereexistsexactlyi

,

j suchthat



a(i) isan

offer and



a(j) isthecomplementaryrequest;all theother elementsofthevector containthesymbol

•

,meaningthat the

correspondingprincipalsremainidle.Inthefollowing,let

•

m denoteavectorofrankm,allelementsofwhichare

•

.

Definition1(Actions).Givenavector



a

∈ 

n_,if – a



= •

n1

_α

•

n2_,n

1

,

n2

≥

0 n1

+

n2

+

1

=

n,thena is



arequest(action)on

α

if

α

∈

R,whereas



a isanoffer(action)on

α

if

α

∈

O

Actionsa and



b are



complementary,denotedbya



1 

b,iffthefollowingholds:(i)

∃

α

∈

R

∪

Os.t.a is



eitherarequestoran offeron

α

;(ii)a is



anoffer(request,resp.)on

α

impliesthatb is



arequest(offer,resp.)onco

(

α

)

.

Theactionsandstatesofcontractautomataarevectorsofbasicactionsandstatesofprincipals,respectively.Thealphabet ofanFMCAconsistsofvectors,eachelementofwhichintuitivelyrecordstheexecutionofbasicactionsofprincipalsinthe contract.

AnFMCA declaresa productlineofservicecontractsthrough(i) permitted andnecessary transitions; and(ii) afeature constraint

ϕ

identifying all valid products (cf. Section 4). Modalities (i.e. permitted andnecessary) classify requests and matches,whilealloffersarepermitted.Offersandpermittedrequestsreflectoptionalbehaviourandcanthusbediscarded intheorchestration.

Wefurtherpartition thesetofnecessaryrequestsintourgent andlazy requests.Sincetheserequestsmust bematched toreachanagreementamongcontracts,they expressanotherlayerofvariabilitythat specifiesifanecessaryrequestmust

always oreventually be matchedin acontract. Thisextension leads to an increasing degreeofcontrollability, asformally showninSection3.2.Table1inSection2depictsthedifferenttypesofbasicactions.

ThedefinitionofanFMCAfollows,whichisessentiallyafinitestateautomatonwithanalphabetofbasicactions appro-priatelypartitioned,plusapropositionallogicformulausedtocharacterisetheproductline.

Definition2(Featuredmodalcontractautomata).Assumeasgivenafinitesetofstates

Q

= {

q1

,

q2

,

. . .

}

.Thenafeaturedmodal

contractautomaton

A

ofrankn

≥

1 isatuple

Q

,

q



0

,

A3

,

A2u

,

A2

,

Ao

,

T

,

ϕ

,

F,where

– Q

=

Q1

× · · · ×

Qn

⊆ Q

n – q



0

∈

Q istheinitialstate

– A3

,

A2u

_,

_A2

⊆

_{Rare(pairwisedisjoint)finitesets ofpermitted,urgentandlazyrequests,resp.;wedenotethesetof} requestsby Ar

=

A3

∪

A2u

∪

_A2

– Ao

⊆

Oisthefinitesetofoffers

– T

⊆

Q

×

A

×

Q ,where A

= (

Ar

_∪

_Ao

_{∪ {•})}

n_{, is theset of transitions partitioned intopermitted transitions T}3 _and necessary transitionsT2,constrainedasfollows.Givent

= (

q

,

a



,



q

)

∈

T ,

∗ 

a iseitherarequestoranofferoramatch

∗ ∀

i

∈

1

. . .

n

,



a(i)

= •

implies



q(i)

= 

q(i)

∗

t

∈

T3 iffa is



eitherarequestoramatchona

∈

A3 oranofferona

∈

Ao_;otherwiset

_∈

_T2 –

ϕ

isapropositionallogicformula,whoseatomsbelongtoR

∪

O

– F

⊆

Q isthesetoffinalstates

Aprincipal FMCA(orjustprincipal)hasrank1andAr

∩

co

(

Ao

)

= ∅

.

Forbrevity,unlessstateddifferently,weassumeafixedFMCA

A

=

Q_A

,

q0



A

,

A3_A

,

A2_Au

,

A2_A

,

Ao_A

,

TA

,

ϕ

A

,

FA

ofrank n. Subscript

A

maybeomittedwhen noconfusioncanarise.Moreover, ifnot statedotherwise,eachoperation f onone of theelementsofthetuple(e.g.union f

(

Ar

)

) isintended tohomomorphicallyact onits elements(e.g. f

(

A3

)

, f

(

A2u

₎

_,and

f

(

A2

₎

_{).Also, let T}3 ∪ 2 _{be ashorthand forT}3

∪

_T2 _{andlikewise forother transitionsets.Finally,we calla transitiont}

request,offer ormatch ifitslabelissuch.AnFMCArecognisesalanguageover(annotated)actions.

Definition3.Let

#

∈ {3,

2

u

,

2}

.Astep

(

w

,

q



)

−−→(

a# w

,

q





)

occursiff w

= 

a

#

w, w

∈(

A

∪ {#})

∗ and

(



q

,

a



,



q

)

∈

T#.We writeq



−−→

a# when w

,

wand



qareimmaterialand

(

w

,

q



)

→ (

w

,

q





)

when



a

#

isimmaterial.Let

→

∗ bethereflexiveand transitiveclosureoftransitionrelation

→

.Thelanguageof

A

is

L (A)

= {

w

| (

w

,

q



0

)

−→

w ∗

(

ε

,



q

),



q

∈

F

}

.

By an abuse of notation, the modalities can be attached to either basic actions or to their action vector (thus, e.g.,

(

a

2

,

a

)

≡ (

a

,

a

)

2

).

3.1. ComposingFMCA

TheFMCAoperatorsofcompositionarecrucialforgenerating(atbindingtime)anensembleofservices.Byaddingnew servicestoanexistingcomposition,itispossibletodynamicallyupdatetheproductline(i.e.bothitsfeaturemodelandits behaviour)andtosynthesise,ifpossible,acompositionsatisfyingallrequestsdefinedbytheservicecontracts(cf.Section4).

AsetofFMCAiscomposable ifandonlyiftheconjunctionoftheirfeatureconstraintsleadstonocontradiction.

Definition4(Composable).AsetSet

= {

A

i

|

i

∈

1

. . .

n

}

ofFMCAiscomposable iff

(



_Ai∈Set

ϕ

Ai

)

|=

false.

Wenowformallydefineourfirst(non-associative)compositionoperation,intuitivelypresentedinSection2.Itsoperands

A

i,i

∈

1

. . .

n areeitherprincipalsorcompositeservices.Intuitively,productcomposition

⊗

partiallyinterleavestheactions of all operands, withone restriction: iftwo operands

A

i and

A

j are ready to execute two complementary actions (i.e.

Fig. 6. Orchestration of composition BusinessClient⊗Hotelof the two automata in Figs.2and3for the canonical product P4859.



ai

1 

aj)thenonlytheir matchisallowedandtheirinterleavingsareprevented.Moreover,thegeneratedmatchwillinherit themodalityoftherequest.ThiswasshowninSection2andisfurtherillustratedinExample1followingthedefinition.

Indetail,thetransitionsofthecompositeservicearegeneratedasfollows.

Case (1) in Definition 5 generates match transitions starting from two transitions with complementary actions (i.e.



ai

1 

aj), coming fromtwo operands

A

i and

A

j.If, e.g.,

(



qj

,



aj

,



q_j

)

∈

T2, then the resulting matchtransition is marked as necessary(i.e.

(



q

,



c

,

q





)

∈

T2). Ifboth complementary actions are permitted,then their resulting matchtransitiont is

markedaspermitted.Allotherprincipalsnotinvolvedint remainidle.

Case (2) inDefinition 5 generatesall interleavedtransitionsifandonly ifnocomplementary actions can beexecuted fromthe composed sourcestate



q.Anoperand

A

i executesits transitiont

= (

qi

,



ai

,



q_i

)

whileall othersremain idle. The composedtransitionismarkedasnecessary(permitted)onlyift isnecessary(permitted,resp.).Notethatcondition



ai

1 

aj excludespre-existing matchtransitionsofthe operandsbeinginvolvedinnewmatches. Recallthatwe implicitlyassume thesetoflabelsofanFMCAofrankm tobe A

⊆ (

Ar

∪

Ao

∪ {•})

m.

Definition5(Composition).Let

A

i beacomposableFMCAofrankri,i

∈

1

,

. . . ,

n,andlet

#

∈ {3,

2}

.Theproductcomposition



i∈1...n

A

iistheFMCA

A

ofrankm

=



i∈1...nri,where – Q

=

Q1

× · · · ×

Qn

,

withq



0

= 

q01

· · · 

q0n – Ar

=



_i∈1...nAr_i, Ao

=



_i∈1...nAo_i, – T#

⊆

Q

×

A

×

Q s.t.

(

q



,



c

,

q





)

∈

T#iff,whenq



= 

q1

· · · 

qn

∈

Q , 1. either

∃

1

≤

i

<

j

≤

n s.t.

(

q



i

,



ai

,

q



_i

)

∈

T_i#,

(

q



j

,



aj

,



q_j

)

∈

T# ∪ 3_j ,



ai

1 

aj and





c

= •

u



_a i

•

va



j

•

z

,

with u

=

r1

+ · · · +

ri−1

,

v

=

ri+1

+ · · · +

rj−1

,

z

=

rj+1

+ · · · +

rn

,

|

c

| =

m and



q

= 

q1

· · · 

qi−1q



_i



qi+1

· · · 

qj−1q



_jq



j+1

· · · 

qn 2. or

∃

1

≤

i

≤

n s.t.

(

q



i

,

a



i

,

q



_i

)

∈

T_i#and

 

c

= •

u



_a i

•

v

,

with u

=

r1

+ · · · +

ri−1

,

v

=

ri+1

+ · · · +

rn

,

|

c

| =

m

,



q

= 

q1

· · · 

qi−1



qiq



i+1

· · · 

qnand

∀

j

=

i

,

1

≤

j

≤

n s.t.

(

q



j

,

a



j

,

q



j

)

∈

T# ∪ 3j

,

a



i

1 

ajdoes not hold –

ϕ

=



i∈1...n

ϕ

i

– F

= {

q



1

· · · 

qn

∈

Q

| 

qi

∈

Fi

,

i

∈

1

. . .

n

}

Example 1.In Figs. 2 and 3, two principals discussed in Section 2 are depicted. A sub-portion of their compo-sition BusinessClient

⊗

Hotel, which is their non-empty orchestration, is shown in Fig. 6. The outgoing transition



qB0,H0

−−−−−−−−−−−−−−−−→

(singleRoom,singleRoom)2u isanexampleofanurgentmatchbetweentheurgentrequestsingleRoom

2

uofthefirst prin-cipalandthepermittedoffersingleRoom

3

ofthesecond.Recallthatamatchexcludesanyinterleavingsofprincipals inthe composition. Forexample,in thiscomposition neitherofthe transitionsq



B0,H0

−−−−−−−−−−−→

(singleRoom2u,•) and



qB0,H0

−−−−−−−−−−→

(•,singleRoom3) areallowedbecauseof

(

singleRoom

2

u

,

•)

1 (•,

singleRoom

3)

.

In thefollowing, weassume every FMCA

A

ofrankr_A

>

1 tobe composedby FMCA withthecomposition operators described inthissection. We nowdefine the projection operator



i

(

A)

, whichretrieves theprincipal

A

i involvedin

A

andidentifiesitsoriginaltransitionsandfeatureconstraint.Thisoperatorisnowformallydefined(recallfromDefinition2

that the set Ar _{is the union ofall requests, permitted andnecessary, while T}3 _{and T}2 _{partition the set T ). Notethat}

ϕ

=



i∈1...n

ϕ

iasdictatedbyDefinition5.

Definition 6(Projection).Let

A

be of rank n. The projection



i

(A)

=



i

(

Q

),

q



0(i)

,



i

(

A3

),



i

(

A2u

_),



i

₍

_A2

_),



i

₍

_Ao

_),



i

(

T

),



i

(

ϕ

),



i

(

F

)

ontheithprincipal,i

∈

1

. . .

n,iss.t. –



i

(

Q

)

= {

q



(i)

| 

q

∈

Q

}

–



i

(

Ar

)

= {

a

|

a

∈

Ar

,

(

q

,

a

,

q

)

∈



i

(

T

)

}

–



i

(

Ao

₎

_{= {}

_a

_|

_a

_∈

_Ao

_,

₍

_q

_,

_a

_,

_q

₎

_∈



i

(

T

)

}

–



i

(

T3

)

= {

(



q(i)

,



a(i)

,



q(i)

)

| ((

q

,



a

,

q





)

∈

T3

∧ 

a(i)

∈ •)

/

∨ ((

q

,

a



,



q

)

∈

T2

∧ 

a(i)

∈

O

)

}

–



i

(

T2

)

= {

(

q(



i)

,

a(



i)

,

q



(i)

)

| ((

q

,

a



,



q

)

∈

T2

∧ 

a(i)

∈

R

)

}

–



i

(



_i∈1...n

ϕ

i

)

=

ϕ

i

–



i

(

F

)

= {

q(



i)

| 

q

∈

F

}

The associative composition operator

4

is definedbelow on top of the operators

⊗

and



. First, the corresponding principalsoftheoperandsareextractedby



andthentheyarerecomposedalltogetherinasinglestepby

⊗

.Thiscauses allpre-existingmatchestoberearranged.

Definition7(A-composition).Let

A

1

,

A

2 be two composable FMCAof rankm andn, resp., andlet I

= {



i

(

A

1

)

|

0

<

i

≤

m

}

∪ {



j

(

A

2

)

|

0

<

j

≤

n

}

.Thenthea-productcomposition of

A

1and

A

2is

A

1

4

A

2

=



_Ai∈I

A

i.

Notethat

4

modelsadynamic compositionpolicy:newservicesjoiningcompositeservicescaninterceptalreadymatched actions.

Hence,bychangingoperatorsofcompositionortheorderofcompositiondifferentcompositeFMCAcanbeobtained,as exemplifiedbelow.

Example2.Consider againthe example from Section 2 andcompositions (EconomyClient

⊗

Hotel)

4

BusinessClient and EconomyClient

⊗

(Hotel

⊗

BusinessClient).Inboth,thetransitionq



E0,H0,B0

−−−−−−−−−−−−−−−−−→

(•,singleroom,singleroom2u) isallowed,whereasitis notinthecomposition(EconomyClient

⊗

Hotel)

⊗

BusinessClient,whichhasanemptyorchestration.

3.2. Controllability

Webaseouralgorithmfororchestrationsynthesisonthatusedtoobtainthemostpermissivecontroller(mpc)in Super-visoryControlTheory(SCT).

ThepurposeofSCTisto synthesisethempcthat enforcesonly“good” computationsinfinitestateautomata inwhich

forbidden statesare nevertraversed whilemarked (i.e.final) statesrepresentthesuccessfulterminationof atask.Tothis aim,SCTdistinguishescontrollable actions(those thatthecontrollercandisable)anduncontrollable actions(those thatare always enabled),besidespartitioningactions intoobservable andunobservable (obviously uncontrollable). Ifallactions are observable,thenanmpcexistswhichneverblocksagoodcomputation,ifany.Ideally,theactionsthatruinanorchestration of servicecontractsshould be removed by the synthesis algorithm.However, thiscan only be done for actions that are controllableintheorchestration.

Besidestheclassicalcontrollableanduncontrollableactions,weintroducethenewsemi-controllableones.Moreover,we callatransitioncontrollable/uncontrollableifitsactionlabelissuch.

Allpermitted actions are fullycontrollable.Urgent actions (i.e.requests andmatches)areuncontrollable. Notethat in thesecasescontrollabilityanduncontrollabilitycanbecheckedlocally onasingletransition.

Lazyactions (i.e.requests andmatches)are semi-controllable. Semi-controllabletransitionsmaylead to either control-lableoruncontrollable transitions,depending onaglobal conditiontobecheckedonthewholeautomatonresultingfrom acomposition.Ifthisconditionissatisfied,thenthesemi-controllabletransitionisalsocontrollable,otherwiseitis uncon-trollable.Thisconditionstatesthat therequest(labellingthesemi-controllable transition)mustbe matchedinatleastone

transitionintheautomaton.Notethat thisisnot thecaseforurgentactions thatare uncontrollableinevery transition in whichtheyappear.Thesynthesisalgorithmcanthereforesafelydiscardthoselazytransitionsleadingtobadstates(because theyarecontrollable),providedthatintheresultingautomatonthatspecificrequesthasbeenmatchedsomewhereelse.The followingauxiliary definitionwillhelpindefining semi-controllability.Itintroduces dangling states,i.e.thoseunreachable orfromwhichnofinalstatecanbereached.

Definition8(Danglingstate).Thestate



q

∈

Dangling

(A)

isdangling iff



w s.t.q



0

−→

w ∗



q orq



−→

w ∗q



f

∈

F .

The next definition classifies the transitions in an FMCA

A

. Differently than what happens in standard SCT, all the transitionsofFMCA are observable,becausecontractsdeclarethe executionsofa principalin termsoftheir requests and offers.Then we define thetransitionsthat arecontrollableornot. Westate theconditionsthat makea semi-controllable transitiont controllableornot.Intuitively,t iscontrollableifinagivenportionof

A

thereexistsalazymatchtransitiont, withsourceandtargetnotdangling,andinbotht andt thesame principal,inthesame localstate,doesthesame request.

Otherwise,t isuncontrollable.

Inwhatfollows,wecall

A

sub-automatonof

A

(insymbols

A



⊆

A

)whenever

ϕ

_A

=

ϕ

_Aandtheothercomponentsof

A

_{areincludedinthecorrespondingonesof}

_A

_.

Definition9(Classifyingtransitions). Lett

= (

q1

,

a



1

,



q1

)

bean(observable)transitionin

A

.Then

– If



a1isanactionona

∈

A3,thent iscontrollable (in

A

);

Fig. 7. A spurious compositionKill.

– Ifa



1 isarequestoramatchona

∈

A2,thent issemi-controllable (in

A

).

Moreover, given

A



⊆

A

,ift is semi-controllableand

∃

t

=(

q2

,



a2

,

q



2

)

∈

T_A2 s.t.



a2 isa match,q



2

,



q2

∈

/

Dangling

(A



)

,



q1(i)= q2(i)anda



1(i)= a2(i)=a,thent iscontrollable in

A

(viat);otherwise,t isuncontrollable in

A

.

Example3.Consider

A

=

BusinessClient

⊗

Hotel

⊗

EconomyClientfromSection2,itsorchestration

K

_AP4858 inFig.5andthe trace



qB0,H0,E0

−−−−−−−−−−−−−−−−−→

(singleRoom,singleRoom,•)2u qB6,H6,E0

−

→

∗q



B3,H3,E0

−−−−−−−−−−−−−−−−−→

(•,singleRoom,singleRoom)2

The semi-controllable transition t

= 

qB0,H0,E0

−−−−−−−−−−−−−−−−−−→

(•,singleRoom,singleRoom)2 in TA is controllable in

K

AP4858 via t

=



qB3,H3,E0

−−−−−−−−−−−−−−−−−−→ ∈

(•,singleRoom,singleRoom)2 T_KAP4858.Thus, t issafelyremovedin

K

_AP4858 becausethecorresponding request ap-pearsinanothertransitioninamatch(inthisexamplet).

Example 4.Consider

A

=

BusinessClient

⊗

Hotel from Example 1 and its orchestration

K

_AP4858 displayed in Fig. 6. The semi-controllable transition t

= (

qB2,H2

,

(

invoice

,

invoice

)

2

,

q



B3,H7

)

in T_A is controllable in

K

_AP4858 via t

=

(

q



B2,H9

,

(

invoice

,

invoice

)

2

,



qB3,H3

)

.

Conversely, consider theill-formed orchestration

K

ill in Fig. 7, obtainedfrom

K

AP4858 by removing statesq



B2,H9 and



qB3,H7anditsincident transitions(includingt).Now noothermatches forinvoice

2

are reachable.Hence, inthiscase,t isuncontrollablein

K

ill.Indeed,

K

illcannotbesynthesisedstartingfrom

A

becauset cannotberemovedwithoutviolating theconstraintsin

A

.

4. ControllersynthesisforFMCA

WenowextendthestandardsynthesisalgorithmofSCTforcomputingthempctoalsodealwiththenewlyintroduced semi-controllableactions.Ofcourse,withonlyurgentandpermittedactions,thestandardsynthesis ofSCTisimmediately applicable. Moreover, wewant tosynthesisean orchestration ofservicesthat satisfiesthe featureconstraint. Tothisaim, thesynthesisalgorithmcomputesthempc ofavalidproduct oftheproductline.

We first recall from [9] the properties of (modal)agreement and of (modal)safety of FMCA. Intuitively, a trace is in agreementifitismadeofmatchesandofferactionsonly.AnFMCAissafewhenalltracesofitslanguageareinagreement, anditadmitsagreementwhenatleastoneofitstracesissuch.

Definition10(Modalagreement,modalsafety).Let

#

∈ {3,

2

u

,

2}

.AtraceacceptedbyanFMCAisinagreement ifitbelongs totheset

A

= {

w

∈ (

n

#)

∗

| ∀

i s.t. w(i)

= 

a

#, 

a is a match or an offer

,

n

>

1

}

AnFMCA

A

issafe iff

L (A)

⊆ A

;otherwiseitisunsafe.Finally,if

L (A)

∩ A

= ∅

,then

A

admitsagreement.

Example5.TheFMCAinFig.6admitsagreementbecausethefollowingtracebelongstoitslanguageandtotheset

A

(

singleRoom

,

singleRoom

)

2

u

(

noFreeCancellation

,

noFreeCancellation

)

3

(

privateBathroom

,

privateBathroom

)

3(

card

,

card

)

3(

receipt

,

receipt

)

3

Afewauxiliarydefinitionsfollow,whichhelptopresentouralgorithmforsynthesisinganorchestrationofanFMCA,viz. itsmaximalsafesub-portion.

Whilst generallyproducts aretotalinterpretationsofafeatureconstraint,inaproductwe allowsomeatomstohavea “don’tcare”valuebylettingtheinterpretationfunctiontobepartial.Wenowdefinewhenaproductisvalidunderagiven, possiblypartial,interpretation,andwhicharethebasicactionsthataremandatoryandforbiddeninthecontract.

Definition11(Validproducts).Let

ϕ

beaformulaoverR

∪

Oandlet

P 

p

:

R

∪

O

⇒ {

true

,

false

}

bea(partial)interpretation function.

Then

J

ϕ

K

= {

p

∈

P |

ϕ

|=

ptrue

}

is thesetofall validproducts of

ϕ

.Furthermore,let Mandatory

(

p

∈

P)

= {

a

∈

R

∪

O

|

p

(

a

)

=

true

}

andletForbidden

(

p

∈

P)

= {

a

∈

R

∪

O

|

p

(

a

)

=

false

}

.