9. Oviatt, S.L., Multimodal System Processing in Mobile environments, Proceedings of the Thirteenth Annual ACM Symposium on User Interface Software Technology UIST'2000, pp. 21-30, New York: ACM Press, 2000.
10. Hutchins, E. L., Holland, J. D. and Norman, D. A., Direct manipulation interfaces, In Norman, D. A. and Draper, S. W. Eds., User centred system design: new perspectives on human computer design, Hillsdale, NJ, Lawrence Erlbaum, 1986.
11. Oviatt, S.L., Cohen, P.R., Wu, L., Vergo, J., Duncan, L., Suhm, B., Bers, J., Holzman, T., Winograd, T., Landay, J., Larson, J. and Ferro, D., Designing the user interface for multimodal speech and gesture applications: State-of-the-art systems and research directions, Human Computer Interaction, vol. 15, no. 4, pp. 263-322, 2000.
12. Bregler, C., Manke, S., Hild, H., and Waibel, A. Improving connected letter recognition by lip reading, Proceedings of the International Conference on Acoustics, Speech and Signal Processing, 1, pp. 557-560. IEEE Press, 1993.
13. Projet AMIBE, Rapport d’activité, GDR |n ° 9, GDR-PRC Communication Homme-Machine, CNRS, MESR, 1994, pp. 59-70 (Technical Report in french), 1994.
14. Oviatt, S. L., Mutual disambiguation of recognition errors in a multimodal architecture, Proceedings of Conference on Human Factors in Computing Systems:
CHI '99, New York, N.Y., ACM Press, 576-583, 1999.
15. Coutaz, J., Nigay, L., Les propriétés CARE dans les interfaces multimodales, IHM’94.
Sixièmes journées sur l’ingénierie des Interfaces Homme-Machine, Lilles, 8-9 Déc, (French paper), 1994.
16. Jennings, N. R. and Wooldridge, M. J., “Applications of Intelligent Agents” in “Agent Technologies: Foundations, Applications and Markets”, Eds. N. R. Jennings and M.
Wooldridge, 3-28, 1998.
17. Weiss, G., Multiagent Systems, MIT-Press Ed., 1999.
18. Bird, S.D., Toward taxonomy of multi-agents systems, International Journal of Man-Machine Studies, 39, 689-704. 1993.
19. Bond, A.H. and Gasser, L., Readings in Distributed Artificial Intelligence, San Mateo, Calif.: Morgan Kaufmann, 1988.
20. Ishida, T., Real-Time Search for Learning Autonomous Agents, Kluwer Academic Publishers, 1997.
21. Muller, H. J., Negotiation principles, In G. M. P. O’Hare and N. R. Jennings, eds, Foundations of Distributed Artificial Intelligence, pp. 211-229, Wiley, 1996.
22. Cohen, P. R., Levesque, H. R., and Smith, I., On team formation, Hintikka, J. and Tuomela, R. (Eds.) Contemporary Action Theory. Synthesis, 1997.
23. Tambe M., Johnson W. L., Jones E. M., Koss F., Laid J. E., Rosenblum P. S., and Schwamb K., Intelligent agents for interactive simulation environments, Al Magazine, 16(1), pp. 15-39, 1995.
24. Abrial J.-R, The B-Book: Assigning Programs to Meanings, Cambridge University Press, 1996.
25. Bellik Y., : Thèse de Doctorat de l’Université de Paris XI, spécialité informatique.« Interfaces multimodales : concepts modèles architectures » soutenue le 30Mai 1995 par Yacine Bellik PHD Thesis of univerity au ParisXI (France)
26. Chen, S.-C. and Kashyap, R. L., Temporal and spatial semantic for multimedia presentations, International Symposium on Multimedia Information Processing, pp.
441-446, Dec.11-13, 1997.
modeling approach
G.Franceschinis (1)
,M.Gribaudo (2)
,M.Iacono (3)
, N.Mazzocca (3)
and V. Vittorini (4)
(1)Univ. delPiemonteOrientale,Alessandria,Italy,giuliana@mfn.unipmn.it
(2)Univ. diTorino,Torino,Italy,marcog@di.unito.it
(3)SecondaUniv. diNapoli,Aversa,Italy,fn.mazzocca,mauro.iaconog@unina2.it
(4)Univ. diNapoli"FedericoII",Napoli,Italy,vittorin@unina.it
Abstract
Analysisandsimulationofcomplexsystemsisanhardtaskthatrequirestheuseof
propermodelingformalismsandtools. Inmanycases,nosingleanalysisandmodeling
methodcansuccessfullycopewiththegrowingcomplexityofarealsystem. A
multi-formalismmulti-solutionapproachisveryappealing,sinceitallowstocopewiththe
complexityoftheproblembyusingdierentformalismstomodelandanalyzedierent
subsystemsandalsotodene reusablebuildingblocks. Nevertheless problemsarise
atmanylevels. The majorconcernsare: theinteroperabilityofdierent formalisms
andanalysis/simulationtools,thedenition andtheimplementationofmechanisms
toguaranteetheexibility andthe scalabilityof themodelingframeworksandthe
development of proper strategiesfor theanalysis of multi-formalism multi-solution
models.
Thispaperdescribesamulti-formalismmulti-solutionapproachtotheconstruction
ofmodelsbasedontheintegrationofdierentgraph-basedformalisms. Theproposed
approach is based on an object oriented construction method and it is supported
by theDrawNET++framework through aproper interface to the externalsolvers
(analysis/simulationengines)realizedbymeansoftheXMLandXSLtechnologies.
A simple dependability example is used throughout the paper to describe the
modelingprocessandthepossibilityofanalyzingasystembyintegratingtwodierent
formalisms: FaultTrees(FT)andGeneralizedStochasticPetriNets(GSPN).
Keywords: ObjectOrientedcompositionofmodels,multi-formalismmodeling,Petri
Nets,Fault Trees.
1 Introduction
Analysisandsimulationofcomplexsystemsisanhardtaskthatrequirestheuseofproper
modelingformalismsandtools. The complexityofmodelingandanalysisofrealsystems
canbemasteredthrougha\divideandconquer"approach: indeedmodularapproachesto
modelsconstructionallowtocope withthe complexityofmodelsbydeninglibrariesof
reusablebuildingblocks(sub-models)and encouraginga modelingdiscipline. Moreover,
modularapproachesenabletheconstructionofmulti-formalismmodelsandstimulatethe
development of multi-solution techniques that take advantage from eÆcient
formalism-specicsolutionmethods.
ThisworkispartiallysupportedbytheMIUR(Project"ISIDE").
others donot includeany supporttocomposition/renementof modelsin their original
denition, but several proposals for adding thesefeatures a-posteriorihave appeared in
theliterature[2 ,17 ].
Inthe contextofmulti-formalismmulti-solutionmodeling,itisinterestingtoobserve
that despite the fact that composition techniques ofdistinct classes offormalisms seem
dierent,theyoften have severalcommonaspects. Itisthusnaturaltothinkofa
frame-workforthe compositionofmulti-formalismmodels. Some resultsin thisdirectionhave
been achieved within the Mobius project [9 ]. Nevertheless, much more work should be
donein thisline sinceproblems ariseatmanylevels. The majorconcerns are:
composi-tion issues whenintegratingsub-models, the interoperabilityof dierentformalismsand
analysis/simulationtools,thedenitionandtheimplementationofpropermechanismsto
guaranteethe exibilityandthe scalabilityofthe modelingframework.
This paper describes a multi-formalism multi-solution approach to the construction
ofmodelsbasedontheintegrationofdierentgraph-basedformalisms,usinganexample
fromtheareaofdependability. Theproposedapproachisbasedon(a)anObjectOriented
(OO) methodology and (b) a proper interface to external solvers (analysis/simulation
engines). Atthe stateof ourresearch, the presentedmethodologyis partiallysupported
bythe DrawNET++framework [14 ,13 ].
Withrespectto point(a),the proposedmethodexploitscomposition,facilitatingthe
modelstructuringand(sub)modelreuseinastyleinspiredbytheOOparadigm. SomeOO
featuresarepresentalsoinotherexistingframeworks(forexampleTangram-II [6]). Our
proposalgoesonestepfurther. ThekeyconceptsbehindourOOconstructionmethodare
modelmetaclasses(allowingformalismsdenitionandinheritance),modelclasses,model
instances(objects),weakandstrong aggregation.
Withrespecttopoint(b),newgraph-basedformalismscanbecreatedandeasily
inte-gratedintheDrawNET++frameworkwithoutanyprogrammingeort. Inparticular,the
nodesofagraphmayrepresentdomainspecicsub-modelsexpressedinsomeunderlying
formalismbyanexpertmodeldesigner,andpresentedtothenaluserasblackboxeswith
proper interfaceandconnectors. Inorder toallowthe dierentformalismsandsolution
methods to inter-operate anXML descriptionof the sub-models isused. The back end
of the framework is an interface towards the solvers that consists of (1) XSL lters to
translatethe XMLrepresentationoftheDrawNET++'smodelsintotheformatsusedby
theexternalsolvers,(2)scriptsforrunningsolvers,(3)lterstofeedtheresultsbackinto
theXMLmodelsrepresentation.
ThisapproachdierssubstantiallyfromthatadvocatedintheMobiusproject[9 ]where
new formalisms, composition operators and solvers are actually implemented within a
uniquecomprehensive toolbutallformalismsarerequired tobe describedin termsof a
predenedgeneralframework[10 ].
Thepaperisorganized asfollows. Sec.2brieyplacesour workinthecontextofthe
faulttreesanalysistechniquesandintroducesthesimpleexamplewewillusethroughout
the paper. InSec.3 the OOmodelconstructionmethodisdescribedandappliedtothe
example. Sec. 3 mainlydeals withmulti-formalismmodeling, whereasSec. 4 presents a
newmulti-solutionstrategydevelopedfortheclassofapplicationsoftherunningexample
whichcombinesFaultTrees(FT)andGeneralizedStochasticPetriNets(GSPN).Finally,
Sec.5describesthearchitectureoftheDrawNET++interfacetosolversneededtosupport
theFT/GSPNintegratedsolutionapproach.
FTA(Fault Tree Analysis)techniquesarewidelyusedtomodel thefailuremodesof
de-pendablesystems[15 ,16 ]. Aminimalcutset(MCS)ofFTAshowsaminimalcombination
of component failures(or Basic Events, BEs)leading to system failure(the TopEvent,
TE), i.e. tothe occurrenceofanundesirableevent. FTA tools allowtocomputeallthe
minimalcut sets fora given FT model as wellas their probability, and the probability
of the TE. Such analysismethods are eÆciently applicableonly under quite restrictive
hypothesis. The quantitative analysisofFaultTrees(FT)modelsassumesindependence
amongcomponentfailuresanditisbasedoncombinatorialsolutionmethods. Statespace
solutionmethods arenecessary toincludemoreexibilityandexpressive power(e.g.
de-pendencebetweenbasicfaults,repair,complexfaulttolerancestrategies).
Mixed solution methods are however possible, based on the concept of \minimal"
independentsubtree[1 ,12 ];inthiscase astatespace method canbeappliedonlytothe
smallest sub-models that actually need it. The result of the subtree analysis can then
befed backintothe upper FTpartto perform combinatorialanalysis. To perform state
space based analysis, a suitable formalism must be used: we have chosen GSPN, since
automatictranslationfromFTtoGSPNformalismispossible.
Complex gates may be included in this case, as well as subsystem repair facilities
(withorwithoutconstraintsonthenumberofavailablerepairfacilities). Itturnsoutthat
GSPNscan be usedto express the most commonrepair strategies, and a repair GSPN
sub-modelcanbeeasilycomposed(usingaplacesuperpositionoperator)withtheGSPN
automaticallyobtainedfromaFT.Thisleadstoamulti-formalismmodelofadependable
system, allowing to combine FT and GSPN sub-models and to apply a multi-solution
methodtosolve theresultingmodel.
In this paper we will use a FT case study to present our approach which wants to
exploittheadvantagesofanOOmodularapproachtothe modelingofsystems. Inorder
to represent repairs at the FT level, we compose FT models with pre-dened blocks
representingGSPNsub-modelsofrepairs(i.e. RepairBlocks,RBs).
TheFT exampleusedthroughoutthe paperispresented inFig. 1,where(k:n) gates
areused. Itisthe FTmodelofahighlyredundantmultiprocessorsystemwhich consists
ofthree subsystemsSUB
i
, i2f1;2;3g, a shared memory M
s
andtwo busesconnecting
thesubsystemsandthesharedmemory.
EachsubsystemSUB
i
consistsofaprocessingunitCPU
i
Redundancyisadoptedatthesystemlevel(throughthetwobuslines)andatthelocal
level(thetwo diskscontainsthe samedata). Moreover, thesharedmemorymaybeused
toreplaceeachlocalmemoryifitfails. Notethat,asamatteroffact,aFTmodelcanbe
anacyclicgraph,sinceoneormoreBEsmaybecommontodierentsubtrees(likeM
s in
theexample).
Atthesystemlevelafaultoccursifthetwobusesfail ortwooutofthreesubsystems
simultaneouslyfail. Atthe subsystem levela faultoccurs in the following cases: either
theCPUfails,orboth thedisksfail,or boththe sharedandthelocalmemoryfail.
Thepresenceofasharedmemoryintroducesadependenceamongthesubsystem,since
theBErepresentingtherelatedfaultisaleafthatiscommontothesubtreesrepresenting
the three subsystems in Fig. 1. A slightlydierent version of this examplewill be also
usedin the paper whereM
s
is removedanda redundantlocal memoryisaddedto each
subsystem. Inthiscasethesubsystemfailswhenbothitsmemoriesfail.
AndNet
Figure1: AFT modelofthemultiprocessorsystem
Inthe next sections,wewill extendthe FTmodelofthe multiprocessorsystemwith
repairactionsinordertoevaluatethesystemunavailabilitywhenapreventivemaintenance
policy is implemented, e.g. the repair of a subsystem or the repair of one part of any
subsystemisactivatedassoonasitfails.
3 The OO model construction methodology
Inthissectionwe introducea newapproach tomulti-formalismmodelingofsystems. In
order to dene scalable andexible mechanisms to integrate dierent formal languages
we are developing a framework based on the concept of Metaformalism and an object
oriented methodology to create modelsand reusable models libraries. All the concepts
introduced in the following will be illustrated in the next subsections by means of the
runningexample.
A Metaformalism isa language usedto describe graph-based formalism, i.e.
for-malisms whose elements are nodes and edges, such as Petri Nets, Queueing Networks,
Fault Trees. Inotherwords a Metaformalism isa formal language that allowsto easily
deneanygraph-basedformalismwithinourmodelingframework.
Accordingtoour methodologythedevelopmentofa modelisaccomplishedby
adopt-inganobjectorientedapproach. ParaphrasingBooch's denitionofobject oriented
pro-gramming [5 ], we want to provide \a modeling method in which a model is organized
ascooperative collectionofsub-models 1
(objects),eachofwhichrepresentsaninstanceof
somemodelclass,andwhoseclassesareallmembersofahierarchyofmodelclassesunited
1
Sinceinourapproacheachmodelcanberegardedasapartofamorecomplexsystem,inthefollowing