# Full text of "mit :: lcs :: tr :: MIT-LCS-TR-170"

## See other formats

m MIT/LCS/TR-170 THE LOGIC OF SYSTEMS by Frederick Curtis Furtek December 1976 This research was prepared with the support of the National Science Foundation under Grant DCR74-21822. Massachusetts Institute of Technology Laboratory for Computer Science (Formerly Project MAC) Cambridge Massachusetts 02139 THI LOGIC Of SYSTEMS Frederick Curt* rurteJt Submitted to th« Department of Electrical U0m* mA Qmqvm tomim m jtif *• ** ** partial folftamont of the r oo alnm i m far the Degree of Docter of Mitetupt . y . We present a theory about the logical relationships associated with system behavior. The rates governing the behavior of a system are expressed bt a Pep net A sot of assumptions about the modelling; of a system permit us to separate system behavior into two components, what we refer to as information and ggrjgg l oform s ttai * c oiws ro o d with cbjtejt. and how they an rjsojyjd. CotititfteeMtcejtieiwlmth^ are njgeojstojQi or choices. We develop a concept of information that to nenprobaWllstk. It is not inconsistent with Shannon's approach, but simply proseads from a more bask idea: It deals with possibilities, rather than probs^ffltim. Our approach e m bo dies four common notions about information: (1) information distinguishes between alternatives; (*> it roteNes choices; (3) it is transmitted and transformed wlthm a syitem;<4) it mm something about future behavior (pr s rl i rM o n X Wo can identify mom points at which information either onters or temves a system, and we can trace teformtlten u n flowa tiirough a system. The control component of system behavior is de te rmin e d by a system's control structure. which to Mover* jra^ lnterprt^ s^hTiyg, tc^d^ T rmintw d rtL <« «*-**v< ? w .<v^ . - F*~ When considered separately, die theories of information and control are of limited applicability. When brought together, they provide a t o ahnteu e for predicting and postdkting behavior. Thesis Supervisor: SuhasS.Patil Title: Associate Prof ester of ElectrfcaJ Etigineiilng and Compute ACKNOWLEDGEMENTS I with to thank the foHowtaf for their comments and sugfestion* Aoatol Host, Suhai Part!, Ron Rivest, Robert GaHager, Mike Hack, and Frad Commontr. I atoo wish to thank Kkn Lewis for her perseverance in generating the text of this thesis, and Hannah Allen Ahtoott for her help in labelling the figures. {-.•• This research was prepared with the support of the National Science Foundation under Grant DCR7 4-2 1822. TAIL! OF CONTENTS L INTRODUCTION LL Spurn Models. 5 L2. Petri Nets. *u.'.Xr» 6 13. "The Problem. « S 11 Outttnc of the Thesis... 14 lllBlllll<-'-v:-*wl«! , 21 Nets. 29 2&'Pettt'N0tS. . i . . .yVifW*..-..* •«4^'i^*^««'^*iyt&l^.^4JM^^l|«n>*-V:i.>^«|'«V*» *■♦•:* .'•"j-'-W 23. The Simulation Rate. SB 1 SYSTEMS 1L Assumptions. 99 12. A System. 40 19. The Puis. 49 14. The Comiot Structure. . 48 11 The Modes. 59 16. An htttteMasd System. 99 17. ExaiMloi of faritteMMO Swomm. 97 4. INFORMATION 4J. Information Gomsnt 75 I T lufw mMm FTow St 41 Resotvtng Choice. 90 4.4. Resotvmg Conflict «.,.»,... . 92 1 CONTROL 5A Event Graphs. KM 12. Paths. 102 51 Cones. . . 119 14. System Space. 129 11 System Time. 129 6. PREDICTION AND POSTD1CTION 6J. Information end Control ....... 145 6.2. Transactions. 145 61 Extendible Stroubttom. 151 6.4. Predtctien Graphs and Pestdfctton Crapfcs. 159 7. CONCLUSIONS 71 Evaluation. . . 170 7.2. Putttri Wort 171 References. 179 Index 175 --•_■*•" &-— t > »"* ^.'"rf'jl-t- „V CHAPTER I wmo&ycffioii l in vm nut vital rutat m* mtfy tiwpwrtn y Soom of the mora it atop, it tiMt oif^rtv. : W^P »^PPPWW ^^Hi ^^Kt^9mm J *?£p I hf Ha * V a aaa|pjt «T taa («Mm tho ioiMMilojr ratting tymai tank aad mm of ftow (tht «mM of *|OMai (a)aMtof(ttff««ittal , • -, « "<,- ^ wp0W ^B 0OW0I0J ^HflOO (c) a aot of difftronot Dynasties') (d) a description la ptatn Enftwi Bach of thoN ha# » d^»min to whidi tt ta i^tto^ «l»al Tat tfoo of modal wo* bo worfcftnf with It MfMdalty appropriate for than iptemt in wfck* tht taOBtBfeB. Mi SaMfiGMtiffl. fit ini»w¥i^i^un an bw bub aian^a^. • *Modof it otad n two tMafcJljF d»lofoiit^io)iioii ftow^Kor .la a a particular tyjtojn* or to a goatral Mt of ratts aopacaMi to a dtfftroattal aquations rotating tht ottctrtc and fnagnitic fttM li aw tMkii pai affi tha distinction It Important, ooaaatt wW make dtar tht L2. Petri Net* Petri nju are * d*» of system mode*. Ute the ftrtf three types of models mentioned above. Petri nets art fjQ^ motets, and they permit mathematkal anaiysU of lystem behavior. However, unlike a set of differential equatkms, Petri nets art discrete, and only flntory methods an employed. Unlike finite-state macMnes, Petri nets makt no attempt to describe a «y*fm tn terms of a total, ansmicttjrad, system slate. «- -*r- l frT ,t ftm «tt 1 eWfrllg TTT FTT « which machines, they ntam a* 4* repfesenitfMp^ the ability to express ahernathws. , In relation It. thtmedcior^Btem^ ofi-fport primitive concepu and, therefore, permit a more f«iesi4 aod p9«NRtMt theory. A Peal net is simply a bipartite, directed graph wheat vertices are catted states and events. (The term condition is I nt er chan geable with 'state*.) In the graphical re p resen t a tio n of a hat, states are drawn u dixies sjkI events u rectsjtgk*. An example is given In Figure LL* 1 In Paste net examples, we shaU adopt- die cenvstutea pTaMte^fevkiwarcaM tetters to states and numocrs id events. ....... We say that state i is a pjspjnjjgfcjiof Event * ifnd only tf ttww b an ire leading fronw to *. Simitarty, State jr is a poMjenidjMon of Event « if and only if there is an arc lading rom * to *. Thus, in our exempts, »et« ft and S art tht pmomUtkim of Event J, while nates < and # are the Before we can use a net to sntertats system behavior, we most fir* Intttelto It This U done by desi gnatin g certain «b«b at jnjgal cojjg&ent Tlnm%s*e*oJsn1n%i§ are shewn graphically by placing a token' on them: Flgorel«t An Initialised Petri Net The 'firing nitr 1 for Petri nets statei simply Mat when oath p ie e O rtaiUm i of art event hohto (contains a token) then that evert nay geoi (fire). The occorroiKt terminate a WoMing of (removes a token from) each pr econ di tion and initiMtiia a holding of (places a token on) each p otte on dltlon , Nettee that this is a strtoHy fatal operation tetolvmg only the evom and its preconditions and pMtcon d ahms . h general, there may Iw nmral e va «» occ u rr lM liKJepefKle^ '■ ekJSMst -^MShoe^MsMMMM^anW' '■ ww pjoai£rjoja. -i *yj„',uSf>4jr#*3^,k-..-<- „-.**s*- ■ ; -XNS-. *f t i fRPSW<!9VM liJ?M^f%rfSi^lP^y|^i!flf^ iffnj* ere concunemry W^l* <tHi|f^Wcpnd|ttop hold) but they havt « conwoa BimmmM^Hwi v%jnf tbifcthe two and. therefore, ttM occurrence of tutor event will <U«bk »h« otlwr. In Fifure L2,£wto,/ «i»d 2 ^*P$^0$§m6M£M£mkpWtofr nn ti jmmit<im4 mmemm awb» fuydMUiig yet another Mt of holdings. It should be apparent that Acre are, In laaefaj many ahei aei^t limutationt of a net (and thai; In general, that ^^limiil^eiitf^toiKmdediiidefliiitel^L 1*. The Probton; For the dejignejiatid mm of complex »y»tcmi and f or the participants in such mtmi the boh; of the day-to-day problem* «re baity to be<efe*r^ tto f<*owiag torts of (1) Under what conditions win* attain pattern of behavior be produced? (2) What are the consequences of a decMea within the system? (S) What are the effects of a system modification? ffl How donhehantpr in one.pejiof tto tye^jaflhanri balaeier in^anosher part? ■ a#W*" •VwWpwW* f ' •"■ •-.■'--.' : ':- --.V :■ u:..:. ■: . - * r.*' . C- - , *■.>■> U . / ." .- : >V Surpri.tn^, very little ttttntta« h« bt«a p«M to ttostwpj.^ pmitom, jjnn heft» to teoaunt for'th^.^her mm#mmim*m»mmM!mjm*mmK-- -* Tfc, p_> i. -^-~. rrm p u 1<|T||i(( g lid „ l|MJi fn| lllli>)ilMft f^pmi r\ ; - ' rtln Mtt W DOBfl CnQSOR Of aM tytMin ieprOieaBmM< ^tmpiuewnv SO wWUf 'WlSWettWeW^W*; w» find a way of determining Hit coaoaaJnts that a Mt pawed on tkt o ct wr onco t of a- purtioutar subMC of events. If w view the system as siiwiatif mlems ( ■ m o ntfUO -a w^H oai i w wt, then those events can do urtsrproBsfl m lying on too systsmronvironmant oouuoaoy. , — a- -□ — a- i i 1 Syetam | ^virttfiaant I 1 .Q □- -QU - - Wv«nt lying on tbe boundary In this way wo can arrive at a chvacterttttton of tlw external behavior of the system - a characterisation that is independent of the perttaner flmhtflfrr by **** that behavior it trnptamenttd. Defining tht external behavior of a system at a Mt of constraints on tht boundary -'■ v/- ..■ * .■.^•-- -, -■ •■ .. .■^■. .-.■(„***;;■ J-$j*V. . iff : ,■/■ - ? ,: ./. - - ■'5y'A.r' i l - - j/. -. ^-;. *#•" S {3 ■- - ? * ' -.; ■-■* ■ ■■■ events roprtionti an attempt to got away from tht i » <i i ciiv notion of txtojnal behavior at a function from 'inputs' to 'outputs'. Then is, of count, a way of answering any outinw whjltntvor about tht behavior of a (bounded) system: exhaustlvt limuktton. This involves cataloging all tht different patterns of behavior. For very simple systems this is a practical approach and is, in fact, tht usual approach. However, it becomes pamfuHy char that thU method ncEtremsty i mpra ctica l for anything but the most ehmontary systems. A more dstuablt approach would bt one that afMtwored ojuasttons about 10 iiprciiffititlpi. ■ ■ ■■?■: Reduced to its staple* towns, tt wet tbie we nadc to ho »i)Ja tt> sj m rnrini how one choke influenced another, to a Petri net, a choice it re pre se nt ed by a shared state. For our Durpotes, we cm ditdngyjtft between two gmi of dwiOR fjM cMn 111A oaMt^Md ckoj^ ' v , ... -. ,_'■'"•*"' ... ..... r*"'!., .' . f™"'i (a) Example of Fr«« qHbico (b) Exowple of Conetrained Choice l.t In the first cue, the net in no way specifies how die choice is to be resolved, and thU U how .1. . ' .«■ *m. jK^v - i * "" : £- ' conflict or nondeterminecr. it re pre se nt e d . In die Moand case, a hoWtnf of die shared state is ■"*-r:v .. -., * « • , "''^s^i^^^ •- - "*; paired with t holding of one of the two outskk inuw to resorts the choke. Dopondinf on whether .o- ..;.;, "•:; •■ r^ - , ^ % • * *« sir , s . ,* . f-r* - *<?- the left or right hand state 'receive! a token', either the left or right hand event will Yire\ (We preclude the ate where both outside stales may bold con cur rootty .) Nets containing onb/ free choices are, naturally enough, known u fret-choke Petri nets. They are very amenable to analysis and their properties are weB understood. This is became, to a fr ee c ho i ce net, no choice influences any other. As might be expected, f r ee choke nets were net general enough for our purposes. We ■■•■-- - ■ ■ ■' - ~ » . :~w\. ff... i -.-- needed constrained choices. At a constrained choke, now a decision is resetted win depend upon some previous pattern 11 of decisi on s at tfeifree eholeai infl otliir rimdiiliteri rfiitrai Thi nrtiMBtti imi to tfaittiillrif thli deoendencv. TtM situation was snOrt vemebaued hi the fit!/ mm wt had to^dftttnJoteh between '•'■ raMAliil'iteariMu at ftMiMMtiitiiei. TIm unh heM ntoiBifOri in lie In dlsciitorlne: The iaochanlirn Opjy "HWI HII ^0O^SWwa^0> 10V v^s*p^B*s^Eue^n^Bv 1 IWn wj*sj*|SV feVO^v^Bj^Sv W OtVW^wSVPTfw* ■ - "iJ^grts^anin^iW^ dfll^a^ . and there «nu no way of adMvMf ewfoau using iimonttfttf Mtfc So we had to find m sotof restrictions that permitted us to tract the flew of 'influences' white stM maintaining generosity. - Turing nwxMrM had shewn that • model coeld be OKemfc p o moa t o* without jpdjctwg its L4. _ Petri iwtt originated with the work of Ctrl Adam Petri who pubtohed tte awninal paper Kommuniiatton rait A u to m ato n in M62. The model introduced there was later refined by Anatoi Holt DOX and the modified structures wen given the name "Petri nets'. With Holt's work there has been a steadily increasing Interest in nets* the key attraction being then* ability to represent both Unrestricted nets have come to be recognised at an ORtremsiy general, syoMuov model But because unrestricted nets are inathometicam; intractable, dot approach has boon to study restricted ctei s ei of nets. If we eliminate either concurrency or chotee, the problem becomes quite manageable. State machines air* daw of note In which behevkr te steittf jeeoentteJ - chore U no (juntui lency. m one form orrunoiuer, swjrnwjcranm^novwoeoB'Oiwuno'rOFmany yea*i> invyvv 12 been studied quite wu o n i ivt ty end a gnat 4«al it Jaowi about tbetr properties. State machines will be mud In oar theory to provide a natfcm of 'sJaaaoiiionoii'. „ . ivm wp j TPa» |Pf^nF7ajeBan3< en .js apeejaBajvi pp.^,|paaB|pf>aajpp^fffjp|pwffpo - ; ;t,. .- . -..* ^ ; £9Js£2SL WbQBSk W Mow* «m«U v* iaf^w'' llw||BllillWi • Wy ^^bt|W»> e^^f^lf^wJIlVy - 9JVVtr wVonvtW^tW ls#«w»^l*» r ' Although they've not been studied a^a^ojtejiiiof^ watt utiderstaod EL -.4* ^ 1&.JSL Tlte-nwM Bea^tecaaMananenfent.a^nuuFfcad 1 eranii is that it can describe: uahr » feted. aeaoBltinB^aeananMwl, aelMwka& JMaSi 4eaJMb«iMeHJeMUa.aae of Jade- fact in our theory. . ■•.„ - ._ *,-s: ; -',Y4' - ■ '"»."'.*-„- Fr ee- d aaeca neti art a seaavaaBaiawr oT botifc^jotie aaaddaaa >and ^fiiarkad ajaphs. They oermit both conc ur renc y and cheese. Seme shtttift&tnt leton* hew been obtained EL SL but. as wo ■*** ••*•• wF^w*ae ww»w»iM i wtiii i wme w*»w^^owwp» a^wpa*wei enfin eweou* ■ # wae^waaef aaoa»w» wwwti wppo^ppj ^wsT *o^pjjjwb> ?t^^_ : ww ^ mentioned in the preceding section, the e ac hi i i en of onastreJnod c h oic e s mtrictt generality. An even larger dots than fr os eho t cs nets art dw ib msi nets. The mathematical analysis of this cam of nets is considerably more dtffkut than far fras choi c e nets. Only a fW results have been obtained & m Patift resut 091 is rigmftetnt since It shews that in spite of their power, shnole nets are stW not coftudeedv ewwral, There at a duns of conrdewjion oroblirns that thav ^^•••n*** wvmwm ww . emewe wow** wmooawaKwoRewswv .. aaasopwaaaawt ■ •.aaaaa-wa .ajar av>: wjPBeoweo; . weu/ . ejeaMRKWMweoeuePtn* . new wnwFaapwoeap- ■■■■•' ■■•■■•.sj CaUinot fnodcL In working with thto hierarchy of net sobdusn tt Iwcamt tocreutngty dear that the key to the problem was the abitty to trace die propagation of 'influences' within a net Over a period of time, the 'propagation of influences* began to leak iwipicloaily like the flow of hrform atta n. This was an area in which Petrt t», 80, tL 2fl and Hek H, K HI had developed many ideas. Their major points may be summarized as foHews: (1) Informatitw U<or *t tanat ought to be) a tysta ai r< a Ulw concept ^, % ,i r ^. \*»r a"t^ va»?jOBBaj»a^eoi lev .aurootaV lfa^w v f|w7wap'^|^ppalB^w» • \aV^rJ^^R.d» y^^^^^^K^^m pa^aw» eHw i^wwl •Jv«a»'aw9« a ^la^wW ■»/ Shannon.) *» 1 n (S) lnronmatan to ataH W ,*r **••». ft fl >i M>u i m ^»# > H w w » Y a maaii oonnkt* (i w nde tar mtn acy whoa Hit system is tmaUmwi to be rennJnf forwards in time.) The (4) Information Is tag by a system at tliost paints wham there "is > ■'toOmmmtimee (noiid o ai nonacy whoa iht systsm Is con i td a r a d to bt ronntng backwards In tone). Two information toot In a conflict s itu at io n specified bow to back op one stop. ns^Ne> Kl^V a^Pve^Beooe^o^B HW eewe ^meveaWe^eol l^WeaHl e^ej Wo^PW oaol ee ^eWsw • ^W*.vHeoleaPB^PMee^^-i-^ew^^wJ^r^^bwn^^^wm^n^ behavior. Ha and Commoner m n M t w s fu l H up p lyttj tha hka to itate machtaos D31 Within the context of a statt macho* they wwf aWs ^ 'id pi Pf'^fbib^W^ jyiiiiio^' and traca their hJttories. The theory irtojie^Mtw^aJfl^ m stajnif Hsnot of Ibis wont it tnat n onaonsnaa war prowspw natrawannBaow oaom amsatwnioeM ap« wf^mmw^mww concept and -tty~'ittdfc^^^ *©*• neTorimuiori flow to a ihoa» Mt^ sjs^ > sj o j sjwsj» oMnt • Out -of tboaa asi towgnmnt t hrn a eJ i'i^aafflfc' -^^/M&di^^^J9&&jL ^^^1 Maaa^fc^adhYT *nyinasr iaa o^h^^^s^emobnY^iaola^fc^ih^^ttl^sa^^f^efr a^lanl Jamo^bVMflaol^hlotol I ^•W Hm^S^O o^& ■»e^ SHBCsHt fh» e*W^swa^i^B^WnW^Bnen^r^Bon1^Rv^^b^P F ' ^» "3F..^yf*^fl5HHS?^r chokas art resolved. The dtotrot ewnp e a s nt Hat to dfr w at r a* ?teo» ropstttivo - aspoaa of behavior Ihnat aaeetts nenvsiteaOnffetsaff bfhew dkOlaaaaftlliMkt^^HtfMl^laitJF fooofnlsod ■swpfOO»w swooa oeeesape ejBjBos^atasea? miBaeepwisj^F''wswosjeoo^neawmo ww ooopw- onwenmsmnrasa^v wwmwnr^ppaBo^"WmeeeowswmaeJipv'-^^^«jr:;, »v^ ^^^»w»»» *-.■ ,y i tf 'i M .j; -±t$!± j£ -^ m a:J '■■■-■■■*« & itL^i **';&. «&&&*£■.*• j-j-i.-. - '-^Mf/i f tyar\ fiffriiiiai^iinilif jtk isjsVr^Y^nrfni^tfi'i , f ^^^A^^^^i»-f^^ o^ B fy'g*^e^aoinarMSMl ntt mm f or iwiKHH tfemweWKOiifc^j^^ anw no^ o*"^^w e^^noanppoww^oe'^^oowwo ^e^ne^MeaH^w awi iw^'o^^n ™ eo^^ * ■ I.:.' . .^"i i -.I. : "-' v : ; v ■ j.-'^'Vti*:.",-'; a . ;, 7 , ?!>■ .■ :., ; ■■':-■; \ ■ ■ , ~ ■ '.«*-^ ,: ?-'-*-' ; ;. ** l' 7^?r-?^' *"i**; « « ' : V* ■ -* '* * *■■ n ; ■■ ? '- : '- ■- -;". ^-V '' ■' . ■■-■"■'"■■> * Hob and Oorafnonar , i wort actoaJy daab onta wtb postdMbw. Howoaar, abhotnh K*s net m o ntto nad in tha paper, there is a deal not la tha thearj daeanf wtth p nj dtct ta n . I Private oomnMmicatton 14 Ho* has continued Mi work i« the*** of ooav** fcft too oufy to say how our approach ~**,-=5» relates to Ms 01001 tot mn Owory &4) H ^ Jn * fmmto* m* *** *» body «* Th€b»*te»mictu«w1|W W «dUii fI ^k«lWAflol UU|«t*Wp.rtit«.dtrfct«dgr»ph. A fogi nfi. te a oot to which ,. m ottach ,* y*& frmpmim ** f<* whs* we dofjno o 'simulation rutf. A MUttUh. (*m onon^ « i^net io whicli 0Mh^Z«l Mu «t»ol]r one taddont ore and cm emergent are. An fXoHgja^ioo^^jfopli)^^ P«tH oo: to which each s&£ h" «x*rty «* iitdd«nt «f< and one aw uf w O. ^w. A state ja«imon«A t of a Petri wt * a oMHhfrapli subnet m »Mc* •« am conneo* to a ,,»/tt^^ front oonojgnoM of o Pott net it on evort-gropft subnet io wb** all s * i c a nn o n ed to tfuutkifwting mrent on uMd. APortM covered by note wmoonsntt (oxot rm^mmU)U said* be^as- tr§£h <1y9fTf^^ (laaiaa^ ^MPMlBteJi)- :M^»ioi»?*M>!t £»♦ J^ : f»f>Ai fhjthjfGp .and *P" ' ^■'^^"^WWfl flO*"^;,,. W^p -^ .mijw- *»»*«$ ^^ppa^p^^i^OOjavOWr >OPj^^0^a^n0^pjW %MSU9npUOa«AjP6*v Tho UooJoHbL a kfo a n » t o Mt of paitfcJ rr'nMtJfftMlul .#«*>• MWlf ,* sw&la tfjagan. among a tit of o**4nm1ieft fM «w«sagaB* s t|Pf **§ fow way*,** w^ two *"«»nces (holdings or occurrences) x and y may bo relate* ^MuLyraajr bj Jgniftn^^ *&• «"»• instance), x may precede y, x may fottow y, and x and y may be concurrent We show that In a simulation, the Instances associated w*h a Mnrf stati tonunoio* form ^ ■*^^*mm>?' -A>mwmfts*®*«**^ Chapter* Ojstomt Seme baste amtnnfrtons «bo«t »# modtHlnf of t iy^ >f« p . ^i.l. a. Tt— em nonitowrt mhb me tonowa^ approicn. A swtem to to defined as a Petri nst - tN svjsaa Mf^ tojsther with (I) a sot -of ettbosti of states and (2) a Mt of stibssts of events. With tM help of five axiom (r**m$mr seswopttoiu). we're able to establish aN the feeturoi of our mod* Tht stibssts of states an mod to gantrato a covering of l-token' Matt components, the parti of the system. The wbeeti of events are used to genera* a covering of event components, the modes. «* liewoito* fl*paro*fe jaojl itructuret aseodatod Kith strtedy ssouonnst behavior. Tht mooes atefjojalotwaoroi modeled wkh asoil state behavior. The modes may be vbjiod ai the'haiMeJ fi i fiiii i i i f ofithooyotom. To eattaet the control <*me«noM of syitem behavior, »• ftrstfensrato the ttnasfiZlQaUifi of the system. This to done of ' c sMap i mg' oech oNbe p«*. T1i*aln»tiativ»dBis» the Mates and events of the system net. Themamtwe*yfNe of sh o m ol ivs dusts: those that contain just stales - they're caned Mi • and these that contain JOst events - they'w cafled ■] ajtjwi The alternative dassss induce a e^etssnt net that teaneeeftt ftapk, Thhtto tM offi^ tfpjfflfo of the system. The msotings fossa the events of thoenntsoi neamno, <rhrtethe tt»U form the stafnv As with any quotient system, the control tfructttie losss certain fsaturarof the oria^nei system. What't tost to jnstthentdity toananjnmnotn^ <* the system net), there to a corresponding control amnjflg ( i fcw n ^wi of the conn* structure), and the two HiiajhmHlii u« Isom o rph ic Tbe snmiid i toi u b nvm ^^^ Urn fit* by replacing each instance of an element with an instance of the altomattv e daw to which thai itauaui bitenfi. Distinguishing between akernativei to the domain of Information. Thafs the topic of ■^^^^sn^i-^v^^i^i^is^-^*^^, ft--- ■- -J.;** n, „ Chapter 4, and in that chapter mo(k» ytof > f > u w ll B WWt»l role. We note here an important property of eaado* wi »e<i mmm m fmm&MJ +imtlMkmmL^ » direct mult of this, each mode it to o m or p l ik to At central ttrvctura. aoeV Mtofff eea, Ihe no4ea,-#ro iwawtophto to eadi other, nto^eaw *ata e » a » , noleao N »tow > d^ #n loto irwu oo itlm i of ThO OBOJBOl 0»Mto« p»Oi^*#OWi^ ^■runpond' <ht lirfuiMtofJl m99 nm 9t mmtm^m II|JJ»J» I J hoi^to a «io >U > w^e ifttrodtlCt the ip a.,w ra o^ f^» »i ,. j-. ^. r ^ _ n| | ^ jhhjugwej titoioj Hon (In nut comain d* .iimemX No t~ fctttoct) ontotO otoaiotoeltol.ietoM i» MI an ha^ too tame mfortmttoncoot.it to no» » oro«» »im«.h ■■ T l uri) IJ n i O f ii i by «f^^ two «h«ef»: «) the atojSf^^hM «• wMd. « hH ja gml - toJatotoj|| W mm " * cotor ' <*htoHftjitoi*»^^ to Uetoi aodnopl ic 111 lehew' m ihi unniul •tfdetoro. By de fl wlw a, o pp t lej n lol o l oan eoooforatoitoat^ooeli owoataf, onweao rec apto w th« 'iihipuni Behavior of the sjoam. - ^ l2 . v , . <*» pecuaar ~y of d**^ tt«tontapt of Inf otlmi oaftoff *>«!**»«; ui » Wtortat. information «*h «to > ii nojo^ >ot*hojpjh^^ * the ^no 'OaMwatoa'OnMosona ofTt^avjei/'ao^o^ y{'>':--i% vjs. 17 ■A, Certain choicm will mveive cpnfj k L which, in oar cast* U •ojiivatont to free choke. We define the i nformation yarn of an event to be the information content of the event mlnui the combined information content of the event's oncondtttonv (The information content of an event will always contain the information contents of itt precondition* end po o aondt tio n i). The Mefjnayoyy fcjft of an event is defined to be the information content of the event mimu the combined information ootitem of the event*! poj|cen^^ The tefoiinatlon ob of » eveiit « to en^ conflict with *. The tafermstton jo* of an event « to the set of iwadei covering those events Ito f^vnjflda conflict with #. this means that btfomwtton it gatojei by a system at >fHm*9*+miim +*** fjsward. conflict, and to fcnfbrajfnomat nrectoefc/ ilmei pinto » hi» the* to hagwonft * Furthermore, the inferinttoei gained or hat fn t cwtfto sto ma* to enervate** to modf vtoaj how the choice to resoheo. The stmt mm of Ideat i^m mwmM Mm mm* ■+» #" information to resolve the choice to inpoltod by the svitom - 1 5^>>;;^.ji?'4':jft^ The control component of ivstsm behavkf te snttoeh; determined by tht control structure. Sine* th« control strueafte it an event graph, the tsjsaff/ef-esnj^is tht ttwavj of event graphs. Wt should mention that virtual aU of our resufa pertain * event graphs covered by bask cte&(ekmen*arr draito omtsining e*s«ilf «ie witen). Thn n net a BMtedon for us since tho imafos of the system parts wtthm tht control ttnid«nfom» a oovwax of bask circuits. We begin by ^ ba ^ki g the c^ wtufs of stem a^%nuJilon i,' " We then show an Important r»buk>iuWp betw ee n the paths in an eve* be paths hi a correeporidteg Unwtattsenl Thfc pernttt ui to expost tht sytmn* v ft is an f 1 Utht* < tti fltothss'tfi ooainme of ^ fo is na^ ft (Note that because we're dealing with event graphs covered by bask circuits, all instances of the ra mi i » i nt wiatal»oidefedJ ThtvolntotAmjh^^ - ^ ■p hlhmwth ^m «venkin<an'event^^ path* huffing the sine wri poh m as » Th« Cnl l n^ l iia gnt i ml i>. N.^ «a#T»*pt to tht tFo j^en above. There exists a path from q x to f s whose 'ImsaV in the event graph is a path with a irnchronic detay of k-L Remember that a simulation fc a partial order J9 . Because synchronic delay it not & convwiiBliCBnMpfelft^MKkv^ifc wo:ird*aduoi;^he;;Op n c op ct of Wk com' and 'frant com.' The backcoar ef inmit<liU4v«tpi» h to the set of states j such that: tlwjrt dow n* oatott ptfhof deny itro rorffl i ntdnt, atrand w h o os fto* state to *. The f rent cont of * to tht set of states < such that; tntre dees net aatot a path of delay uro originating it * mnd whose to* state to I, There to > rimpto utottowl i tf b e twe e n synchronic delay and back ■ltd front cones: ' The synchronic delay of a path a (In an event graph) to equal to the number of ttonoi the back boundary of *% bjgd. to < Tht lyiwhronte delay of a path a toeouet to thtmindwjr cf tunes wtefjeeg boundary of n's tail to crossed. Condi have an oxttdnthY inenuating onwtoction ■w'the dnnriatiafii of an eveufcrgeueNt. ■- Tho states of a particular com ddftno a an-tos of cone-like slfces In oach stimitotson. If It's a back nana, than that* cone-like surfaces point forwards, and if it's a front cone, then they point backwards. At the tip of each 'cone' to an occurrence of tht i s su e d event For that occurrence, the 'cone' provides a boundary between the past and 'not past' -If it's a back com- or tlw future and 'm* future* * if Ufa a front tone. Between any two consecutive 'cons*', tnaetfto ^eautdy: om oomrrem* of each event System space to assocsatad with tht notion of !s yaclwu a^de<snce vwMch to a t neamre of- the • 'flack* between two events. -.- Tlie saithpord c d toj f a nra b aiwoa^two etanto in an eye ejuoh to the msntohal token leading on those drcuta containing both sv qui, Whan in event graph to strongly connected and fret of blank drcuito ( c lr cu tto without onti-iofcontay M^fi e ^^ * metric on -the w t Do not confuse synchronic delay and synchronic distance. f;--.-.-! , . .. .-a: > »«,« i.j^.j^^jej^ja^ig^^jij^ij^jj^^^,^^ » Hi t«Mt •nit to (M MteMMMM^iMT ^^^^P wPJP^ *^^^H?y »^P^* cku of tottM Uatfed « circuit. Thli ft i mmAvsImci C toBUM MM Ml '-■' «"'-' ";■■" t^* » f *:5«p# %: ^<$<|£1$ l synchronous cvmt gnpn, wt slices strictly atematc Ooohtwcm wNmb tfet mum Mm Am m» «M to ht VMMnMM • ■ ^W ^pM**p 9MHM'BvM»W %»™J • * «l) m rftsejj.- Wp^i. > l jS0^rt;»»if3 sir," AM) tMMt of Tin >;»»>•. • -r * 'itwioi fc* wi"^ ,« wiw*- ,- -3, F rt«sw«o"t ?n«3*f *r>£'h ••.*.: •■■•'*{ i3O0 $ '.. mm th»tto*wn toMMiililu %truttoj»ii Mj^NMrti KMwW tflHWMMBt pwwinin; .-mt> to Chapter ««M ■no cm proptrtMi or uiufufcr MMNto if tht intom MMN'PQMWMMI^M a Wfchm the oMitml ataaeh*to* there to » mat o rd t n^ am o ng t win Wi tts of the seme inttttiig. For each such fttoel oidtrfcigt there to<a esifaBaandmg^4Bori otdtring ■'iB-'ttii'-ijSltni wnaanan anwny OBcuninMi oc .- rmi - mm mm|M| v an nmib MMnng. * », - whbhi in* afMMPR toinutoaen, the ntoooomenca sjscdttea wtoh MttMng «t to an eorurmiMt of Ivent «, then i^mlPJp/omoW pWBW--' ».mo? oaWPnT* BjTggi'Tgg^gMggmggg^^^K f^g ^^^b^^^^K i *jB. • wwP^WWw^'^^^^W ; onwmWeWeMsolBwFoA ■ "'Pbt,.*w. enr'W" L 'oe^B^nnT«WnL-. wP» g. In ton* Jan. * will Be onbtr n e gathrt or ^^^^^K^^> '^^^go^^tsh^^^n atS^^at ^ ^^ Wt Wc know that f to an imttnce in somt system tlta riw rfi tw chute, tf weal toe? lunutotion and that f to associated with the t*va*ftmur/whatwB««MhU patterns of transactions prior to a mm The additional knowtodft alews w to identify an ftomnt from among tot ahafnattvei. Thto to exactly the same thing that oar notten of tefommtkm centra* dees. So tht 'information contant' of the additional knowledge to tejuJvatont eo tha tnfeimetten content of tha rtwn a nt tokntiflad. Anything that can ba deduced from ana can be deduct* from the othtr, and vice veree- Of course, we can't »y anything about how far tht limutotton containing f aatandt, either forwards or backwards, but wa can say that tht patterns of trsamcnoni mutt ba conatota nt with certain requirements. Our approach la tht problem U to try la characterise all tha ways In which the information associated with q could haw gotten there (p ool dktt o n ) and mJ] the ways in which it could have tmanttad f aem them (preaktioa^ feton^ of excluded modes. Since information to 'add Wta', wt ew oeat each made m the ntforrnatoon content of f separately and than marge the results. ^■^t^J^^a*.' :-. 22 Far oath oyjb j d s d m odi , we know that by tracker ihs sartadhiii hniiieuli ^forwards) we're going to generate a sut^ of d» d W , ht lsa faea^em <eat of? * Th* soim* define, a partial history of At mimrM wi prlnr M wireo m) t»or la |0 ww al, Uwt ti be araarat such eartM histoid fsessibfc. «-«-rr mmtW ttw pamal hae o rtai i w i bs siio ad iidi a^bMiaiily liu, m which case, there faty beenia#iB#iaOftdMir «f : |MMf§||I^Nifl|^iHMhifcr-Mt time Wry d sallni •wi # into «,ate»% **» |» A nmtwr*+mm*mi t mm*i+Bm* **-—***&* pwtW hirtoris* ataxtatej adaVeaeb mM* *A 3te aaas* AiM m Chepwr 3 ten be used to 'sitae up' the forward! and backward ptetleiaaa*^ *be*^^ and front corns for forward, historic This ii nii • t*m m ot +i*xj n§*mnu '. To characterize the set of forward, or backwards partial hktorist, wt mod only describe bow tbt appropriate is gra w m may b< «owwo^ lotatair l^dO dd» w«h a auto graph, each 'state* c»nas|ioiidliigioa|»rttailarsa|mtm. For * jufllflfca fltt «ad» path i d yni li a M n a ) a»a 'finishing state* defines a posslblt backwards partial history. Par a Bfjjgoji m& aacb path originating at a 'stating state' defines a possiblt forwards partial history, m batb cam. tbt transactions associated w*h thm «Vh ,~u u> > pi. .— ^ ^ -i^ mnmritoni " the lonespiinilii^ psiilal liiitui j Chapter? Condtukau We discuss aspects of the theory and the mthaary. The disco*** of theory Is mainly ...■/'.-,■_■,:■■■ *' '• - ' <• ' • ' "■ 'i **r* • j$i AS" *w H-"~' • t> «• concerned with the future directkw of the ma rh e m t rki in the ana of metetheory, we touch upon four related topics: <T5g>?o.:,;,y 9f»1 '*? ■:■:*•;■-,■ : : <2tis ":•;;•■ .5 i^'if' (I) ' found ^«isJl« *ere a set of 'sttf^idam' axionu for die theory?) <S) methodology (How Is the theory to be applied?) u\~^ <*^~^ fr-^ma II itii mni| waartfl • . 23 CHAPTER 2 PETRI NETS 2X gefi: Nets are tht bttk structural of our theory. DtfMttatK .-A-MM 1 an 01*10* ttfrlo of sets «A, 1, C> In which ATI** and CfiAxBUBxA. AUB it ttw set of elareonti of N. (N will be » Hw o d at a bipartite, directed graph with AUB as tlw vertices and C m the am) Notation: In die context of a net structure <A3,C>, we w rite jw y to m e an oe, y»<C For xcAUB, Definition: If N U the net <AAC>, then R is a subnet of N, written RfiN, iff R-<A'.B'.C' where, A'jA B" c B C fi C fXA'xB'U B'xAO Property 2 J: A subnet is a net Notation: If R to a subnet of tht net <A,B,C> and RwcA'A^O, then, for XfiAUB: X R -XD(A'UB') forYfiC: Y 1 -Yf1C' Qfttothena&iggaaf.gto.R.. :- ^?H*^©^^;^-: -^^^fisw^i^^^ir^ffi-' ' The ratal fovernJnf the tehavior tf<«r*i«i»«i« «*pr<«Md *» Mm* * * **■* Mt Definition: A Petri mt to t tut <S JLF> where. SU« finite nonempty <et of «alo» Eli a f taiite nonamotv aat pf evanti • WP HPW# "^^^J^g^^^^^P^^WPJJ ;■' ,-'* > .:-''- [ *.?'■■■"■ ;■';'■ -■ ■.-'■L*"i >'■':' ■ ■ ' "'■' . ...::■ If MS, then the etements of °> are called the tamt evento of s, and the dements of a* thtajspjrtjvejjtof *. IT eel, then the w— haw of a are catted the Input itataa. or , . i- fMMMarfOaPlOL dtMhM wA taiH >j|M^aM4if-JfueaMiaikkHlMiiaMaMpAMMi^eiifcMiiiae'M'<. Definition: An frtftjaHjod PfgLfflt. to a puadniph ^ I, F, I> whew, •■■■ <S. €, F> to a P e tit war . ^ :*•# .-•-''" <*,*■> M^-vy «^ ,* ■<:.. ■?.-..? IfiSUtheaatof Definition: A state grap h fata* machine) k a Petri eat *JLP> ai which. 'Each event haa exactly one pracoodWeji and one | Definition: An event graph (marked graph) la a Pert aet AJLF> aa wfcteh. VteS: TH-Pl-I Inch itate hat exact* one input event and one ettpwt event' / (a) A State Graph (IbV ''■%&" WN^z4XNBto. Figure 2*1 Sines Hi a Matt graph and an event graph one type of node Has exactly em inddent arc and one emergent arc, it becomes superfluous in the graphical representation to expNdth; show that ^type of i»odfc Wt ttieteTore adapt an ab brevi a te* l ep f tie ntatk m in whkn eft*y the nates in a state graph arid only the events in an evert graph are «^^ are now drawn as in Figure ZZ It should he noted that this practice in no way affects the foftnal '. ■ ■ ■ •- • •.. •■:■ •■ -' -: ,", • --< .■ J- <g ,.■ ■■ , ■.-.^..»«- ■-. , .. . . •.--«*'•' of state graphs and event graphs. (a) A State Graph '(b) * £n"lBvoht Graph Figure M Abbreviated rsji-f ^^^i*^i:*v.*t*jvs^TT-,v ; --^^^^^ig^^s^wr^*.^ Definition: If N-<S,EJ> It a Purl net, then R-«SM'.F'> to a Hssl ITOTOItlft "* N iff, (a) R tea connected, non-empty statt graph (b)*RSp WP^FrtrxiuExsO 4 k to a cosmottad, non-empty statffreph subnet of Nt In which aV am connected to a Deiticunit^sttttamiisee? V >*~\ V Definition: If N-eSAF* to a Patrl nit, than R-cA', 1', C> to an evem component of N iff. (a) R to a co nn a cf a d, nan-empty event graph <b)R£N (c) F' - Fnfcxl'u E'xS) •R to a connected, no n -empty event-graph subnet af N In which aR arcs oomadad to a patticipetsns! event ara used." :1, ;^3 *fif* * : "' "'i *?; Sf*0> " -'jj *■ : "» , ''"-j v -' c- if.- : .,57f Definition: A Petri net to said to be sttm*ranh <km— nbfc <*GD) iff each etemam (and thus e^™^^^™ip ^■* ^w^wsw ^mosifi^HBVsm ^us^swsn ^•^w^w ^w^wwa wwu/ aw ^^w^wew n» w^% In Figure 2.3, we show a stafegraph iirnnuuisHsn and an erent-graph decomposition for the Petri net N. Each of the two nets in Figure OW is a state oampofant of ft, and each of the two nets in Figure 2J{e) is an event comp one n t af N. Notice that each state component selects aH arcs connected toaitatcbutjustontsrcimesjidomarcoiitofeach event With an event component the situation is just reversed: it sates at any fafwenTidfoan eveht but just one arc into and one arc out of each state. In the case of N. there is a ittleut tttRt-grepti decomposition and a unique evenfrgrtph rt s mm e w i tiu ii. But, as well tat later, there may be several decompositions of each type doe to overlap of 27 O & 8* c mo B- «H'-' ■?*{ 4J a M V •* <*' ll '»■.;■■. -^Iftte- «^- ? ■.«&..■ ,Q "» m V " l0 "'**' £ ' ' *" ■V :%*.-* ;. '<*» o • (M 48 10 -H V U 4i Vl W % H| •H fa *l to jo 0) •<-Q IB i ^'■^SjWsi/.S^-fr'SSSftri-si-i Definition: A circuit it a (directed) path whose two endpofaits art the same. An elementary circuit U a circuit m which no vetfex ts Lemma 2J: In a Petri net, the intersection of a tfttf • (oosatbtv emotv) cottMtia^-ef dkMnt wttfcan event eesnaonent it a Proof: Let $ be a state in the intersection of a Hate component and an event c om p onent Because 0ie state comoonent contaJail nil i«t lata^niHIo and franfYientie die event comooncnt »"i w^^ww* *nm'ia**M ■ wm Mfffnawt* fane . awaptav aunuMpsuiBB aw* aaajoes ••wjapw • .uwejoonap hio ofwi* %*#oaaaw^aoa^»aa» chooses exactly one ta6B& m^ ^0m^^^M^ n ^^ 13 ^ uim Just the two arcs of the event iiaisyjiim. By a o^l afljunteot \*»' incident arc and one emerfam arc for each mm. Twos, eac# clamant in the intersection has exactly one I ncident arc and one e m e rge n t arc The of** tmm structure satisfying Wl^eW i^^pwi^kwlWWa? H •» ^^^^Kto^M wv WJDVuW VtmsmolHowHuY Ue^BKsV U Theorem 2J: In a Petri net that is both SGD and EOD, every stale component and every event component 9 strongly coRnaccea. Proof: We prove the thecfem for state componfnta. the proof for events •ymmetrkaL Consider «n arc <x,T>in state e/ — " — "*■ " *~ J an event comp o n e nt K that aho contacts <*, .and R. By the m^ing kmn*, <xf>mm intersection of X( and % ThUmeiM t$at Q — 9r ^ m „ .^„ ,. elementary circuit Now from the def mMan '"of • state eamponem, "w« cormecfea. from these nut two facts* it ts being there is 4* Q in tne by am chat Q is D 2A The Simulation Rule: In Section 12, we gave an informal description of the simulation rule for Petri nets. In this section, we formalize that rule. Our scheme is patterned after the Js^rence graphs' of Holt 001 The basic idea U very simple. Oiven an mifettsed Ptari itet^ Streol>#oi» Rule generates all possible finite 'simulations'. Each simulation expresses a causal relationship among a set of stale 29 •holdings' and event 'occurrences'. The causal rote ttemh l p reflests the pattern of WjinatfW Mid 'inittatlonj' of hokllngi by occurrence*. A simulation is represented »» net «H.O, G> in which H is the set of holdings, O ii the set of occurrences, end C is the causality relation. In order to distinguish between repeated instances of the same dement, an instance (either a holding or an occurrence) is represented as an ordered pair <x.n> where x is an dement ,- the Instance type' -and ni* a positive integer - the 'instance number'. The Simulation Ruk is defined recursive^ ^.If^sfnnjata Is a collection of isolated holdings of the form <j4> where * is an initial condition. In a simulation, the set of unterminated holdings U referred to as the 'front boundary' of the simulation. When there exists a set of holdings in the front boundary of an existing simulation consisting of one holding for each precondition of Event #, then a new simtlatsan can be generated. The new simulation contains one new occurrence for Event t and onenew holding for each of /s postconditions. The new occurrence of * Wndnates' the previously uirterminatd holdings of #'s preconditions and 'initiates' the new holdings of #'s postconditions. To create new instances, we employ an auxggary fm&m* Definition: eX*,Q) - {«, IQrXMxNJHfc} n(x,Q) creates a set consisting of a new instance of Eteatentx The msttnee number to one greater than the number of instances of x in a As a resuk, instance i » for an dement are assigned in numerical order beginning with L We're now ready for the formal simulation rule. to Definition (The Slmirtotlon *«!* If Z * the MHMI— I Pen n*+> I» J, I» Own, (I) 4*[l)44> Is a tjQujgon.of Z. (2) If T ts the exlstfef BftmikKtw 4M), C>*nd if A to a i* of toMteft' In the front boundary* of T rowiMlm of out TieMing;' for each pfeosndftftsn of Event #, then, ' */< t.'s'i -f"r*> * , *n ■ F,tt.S; . »»*■ of*. O UefcO). (s) Tm flwiy ftaaato|qf z*tt ttaom» o i iy« mw t» Step (2) is iHuttrated in Figure Z4. ;.'i»a'1 nt*M ■ ■'■■ *. ■:'< :\ [■:'■■;■.- 1 ,sswi>;<, Definition: If T te the simulation <HAC>, then, Htttheiettf O U tht tot of C is the ofT V We're using a rotational convention here, ft W etsrnents In the rango of f on am, thou for JfjjQ, Thm.f> a ,H)-^.fXf,H)L ; oP f ta a tnd If the 81 The ordered pairs in C are the etenwntanr caw*l oayctiom of T. Occurrence q is said to terminate Qnjgajt) Holding h iff then is iMpfffprf % «-»> """^ leaning fromhtoqCqtohXThesetof utnstmi i wMrtfo nlnltsatod) holdings is celled the front (back) boundary of T. In the graphical representation of a sirouwikw. the vertices are drawn as points. The simulation in Figure 23 is one of these generated from the net in Figure 23(a) with States a4, and g designated as initial conditions. Because instance numbers are redundant in a graphical representation and because they might be confined with event name*, they're usually omitted. The abbreviated form of the Umukbon in Fsjure 23 is shewn to) .Figure 23. Note that this practice has no effect on the fjrmal representation of a Hmulatton. The following four propertiei follow Immediately f ran the simulation rule. Property 2& A simulation is a «et. Property 2A An occurrence of an event tewnfcales ont holding of each prec^^ and Initiates one hotmng of each p oitc on d m op. Property 2.4: A holding it initiated by no mow than oweecurrencB and U terniUiated by no rnore Mum one i Property 2* A simulation is circutt-f ret. Definition: Consider the result of taking the transitive and reflexive closures of a simulation. The new structure is transitive, reflsxive, and - because of Property 23 - antUrnmwtric In short, ttU a partial order. We wts»*&* indicate that x is related to y by this partial order, and x<y to indicate that x& but x*y. We adopt the following ter rninol e g y t x-y - xand * arc coincident 32 <a,l>. (1,1) <b,l>\ (d.l^ (3,1? <a,2).' <e,l)X <g,l) (2,1) (5,1) <c,l>V <d,2>.^ <h,iy (4,1) (7,ir <a,3>* <f,l>X <8,2> (1,2) (6,1) <b,2>% (d,3).^ <i,l) 5 (3,2)' (8, 1? <a,4>^ <e,2>X (g,3> (d,4).^ <h,2f (g,4> Figure 2.5 A Simulation 33 a • 1 •: 2 •; l • g • Figure 2.6 A Simulation (Abbreviated) :■;;=*&; rfa^^jw^^^ . f foBooe * *iy A y 1* - * and y art concurrent (Note that by our convention an Um*n<* y mad si itestf and foHows itself. This U not normal usage, but it's mora canvwrio^ %p our pmyam Net** that concurrency is nofhinc mora then tha ahomoi of anaoMha J t nv neat property iono^ SMeuiy ihm hh vanvmi imhv< Property 2ft If tha instances of Element x are totally ordered hMMmuattlon T, and if <x«m> and <imi> are instances m T, tha* «**> la the aaa^aaaMee of a fatowang <ayn> Iff We now establish tame baste structure/ lettfenaMps bet w ee n Petri nets and their simulations. then each Notation: If a Is tha instance <ayi>, then f • k ^hs notation is extended to a sequence of instances m the obvious manner. If ♦ is either an bufanra or a path in a simulation, •••unrw- w ■ ana aMniovn^B ouor ^^H ^^Ef ''a, Theorem 2.2: If T to a simulation of the tntttataed Petri net <N4>. then, #«ncr) # Hn.w s The image of a path in T is a path In N.' Proof: Every we in T it either of the form <hotd*y, utun ie m«> or <oceurr«nce, hokHhgx Thto together with Property *■> h»ds » «*» ioHlili lW l l D Definition: A strand of a simuletton is a path orifinattnj in the ■•** boundary of the simulation and terminating in the f root boundary. Definiton: If T«H,O.C> is a *imulatton of th« teittatad Peirt n* <SsW> and if R to a subnet of <SJSJ>, then forAfiHUO: A R - {qaA^e^RUE^} 'A R contains those instances in A that hail fifcjfcei wMiln R.' forBsC: B R - {<^r>cBK^*fxFi} •Bj contains those ares in B that hav^iineferwuhin R.' Property 2.7: If T it a tfmutottoo of the WttaHied Petri net <N4> and R U a subnet of N, then Property 2A If T.^O,C> Is a stmiilatkm of the Wttaaaed Patrt net <SJE^4> and ft to » aubnet of <S£J>, then, F K -Fn(S K xC ft UE ft >e5 ft ) * C R - Cn(H 1 x0 1 U O^xHr) If F R constott of an arcs On F) connecttaf two 'elemental of R, then C R consists of an ana (in C) ce im ti ttng two le s tin i ui of T»' Property 2.9: If T - <H,O.C> U a sfcmrietion of the huaaJtoed Petri net <NJ> and R is either a state component or an event com p one n t of N, then, C R - CD(H R xO R U O r xH r ) *C R consists of all arcs in C connecting two instances of H R UO R .' » Theorem** If T to a timukdon of tip t n^hwri F ^|^ <N^ wrt R to > «^ coropomniof N. then T, consists of g^ saJ Jrial ihl»lll ' Proof: If T U the initial limuktkm of <NJ>, then T K canto* of the hokitngi in I K x{|}. They fofm Igt disjoint strands. Now suppose that <H t , 0|, C t > is a simulation of <N, I> for which the theorem is satisfied, and that <H t O x , C,> to derived from «H I# 0|,G|> throufh a single application of Step (2) of the Simulation Role. Thus, there exists an event t and a set of holdings A sn the front boofw^ef ^.O!; Creech thet, " : H l -H|UnU',H 1 ) Oj-OiUtfcOj) C, - C t U AMntnO|Ml t^WMJ From Property 2J we have, There are now two poutbilttiec t is contained in R. or t to^ contained Jn R. In the first case, JAjl - Ke^.0,%1 - Xe>'^i%l - L And in the second JApJ - Kfie.0,^1 - KeX«'^ 1 » m | - a Either way, tht theorem it satisfied for ^O^Cjx D In the net of Figure 2.7, there is a '2-token' stale component corittotmg *f those states, events, and arcs that lie on the outside ring. According to Theorem 24 (here should be two strands associated with that state component in each sh^ the simulation in Figure 2A Notice that the net in Figure 2.7 contains another 2-token state component - the inside ring - and four htoken soste components. The reader may verify that the simulation of Figure 24 contains the ■p p t op rltte num h n ejf i traji t > tor <ach of these * H R | is the number of 'tokens' on R. 1*W ,^'« ,Xs ~ S7 Figurtt.7 Corottary 24 If T to a stoufcttan of the mttteUud P*ri Net ^4>. ond R to a co m p o nent of N, then T K consists of • single strenoY Corollary ZZ If <H,O.C> to a simulatton of the inittalixed Petri Net <K,*r, and R is a Hokcn state component of N, then the instances In Hjj[ U 0* are tetOf ordered. Corollary W If T to a tonrtetton of an Initialized Petri net covered by Hoken state components, then within Tine tnptaness of each etonsnt w totals ordered. 38 e • Figure 2.8 Strands of a State Component 38 CHAPTERS SYSTEMS Si. Agumftjonj: Like any theory, the one rM following: here to bo*ei^ owm i n ii i jjioni t oni . Tim major one* are (1) Associated with each system to a Mt of Ham ( c onditi o ns) and events - the system elements. (2) The loftcat aspects of system behavior can he com p l e t e ly expressed in terms of the thai a system relation of behavior. (S) Petri net* am an appceprtottt tool for i mrs mi sf ie f the leg**! pieces on the holdings and occurrence* of its eSsmsnts. (4) A system may be decomposed into soajoenttai ""P**"** ^"* th * ■ mdiieoB o^M>mimieBjBnBjB]i|(Bj|t%ae«^ "PRJiiR|^w*i [fi) fcvory system ossmoni4Srpnr( oi*o* oBW'ejm^j^^eesw^i^PwwyT^^^PrW*^** Assumptions (1) and (D represent en attempt to find » common ground for describinf the myriad facets of system behavior. The notions of s*tt, event, holding , end oeoirrence appear to be general enough to encompass everything that one ndght consider to be logical b e hav io r *, Note thar^ are^epeetftmty^ ' for be a f »»*• wi-<*4****rWM ihm of its element* Experience with «cb enpflmmts. ThUis the basts Because weVe deeiinf wRh finite systems, constraints that a system places on the holdings and Petri nets ha* shown them to be ideally suited for for Assumption (S). : 1i«*!*!§^ 40 The most natural wr> of tntr o d d tif Hit iHBon of etarnattveneu Is by auumtng the existence of sequential co m po n e nts . Each sacfc aBmpontnt induces a natural partition of its elements into alternative dessos. (To bo captained bssew). By aawmlng that alternative dassos from different comp o n e nt! do not perttaBy overlap* we get a partttkm of the entire sot of system elements. This is the meaning of Assumption ffi Assumption (if UHHUosei the astern of s»oa1fo»ar Inmavlot. Hr-aj nan hat been an important concept in many different dlicsaltnoi, tut thest iiiUpimai have been b aiod on continuous models white ours is bawd on a djsgotj. taodoi The fact mat steady-state appears in conjunction with a discrete modal should not be too surpt i i tog m o ugti . After ah, we're trying to describe the same reality wheal* wVWvitfhM The f fre sjsgf np t hw w Hi JHittWIITw li^ tunem. This definition incorporates five axioms. Akfcougti men axioms eachate many mmrtun and maaningf ul nets. It has so far bee* poomw m convert seth nor Tnif mffMmmmm^im mmfi Much more ^••■^•e MIVb So) sTo^b^R^o^mV w9 1 embody. SX. A System? in tie proDBBing cneeesr wmsejngumiee wejamewtPiiaMpsHR^ . We do the same for structural properaal or a mtaauzea system. we system This soshon and the next throt are of an .',->'. ; . '--.« t6s3a"'^ rf-> 41 of «iw and a set of tubtets of events. The subsets of stet* an used » |«mm a covering of state compononti - the 'parts' of the system. The wbiw of tvontt aw uwd to gonwalt a covtrtng of evemeix«ponei»-theVoedes'ef thesysteni. WeceoMtof ^eiii^liav#liKlujledlNpamafid model themselves in the def tuition of a qmm, ****•?*** haw beta a grmt deal of redundant information. We're taking advantage of the fact that a state component U uniquely Identified by its states, white an event component U unkaieH; identified by to events. Note** for a given Petri net, there may be several covertngi of both state components and event components. The constructs of the theory will, in general, depend, ju^ w«ch^;coferlB|i am setecttd, but the implications of this art not fully understood. Def initlon: & - <N, Dp, Djn> where, N - <S, E, F> is a Petri net - the svttem ne£ D«£(P(S)UthepartdjffiGffiO»i^ r Dm^ s ^ (£) te the moi£ djccmpo^sp. X denotes SUE, the i^ttem etetwitt Axiom 1: Nil connected. This axiom merely prevents a system ftom having seveml dlouiiissirinrl oemaooonts. TWtisoota real limitation since in sucheaseseach connected cgmponert o^betieatedas a separate lyetem. Axioms S-UDp A VAeDn: <A, *AUA\ Fn(AxEUExA)> U a connected, non-empty stale graph The sets of stales in Dp genemiea eevertng of stata components.' 1 OKA) denotes the power set of A - U, the set of all subsets of A. 42 Definition: The state components goaars as d by the MO to Pp are catted <he parts of £ The sen* parts it denoted by p. When the spum J ii tatttattM* ve wit rw p Urs th at o* h psot bes j i iy so d oa s aly one krtttal condition. Thu% the ports wit besom Hohen itsie nnmoenewh end wit be tincwjfd with- strictly seojttentiel isehewtor . Axiom J: £*UB*i A VtdOfjf «1U*', B, FA|**1WM<*)» is s essesa^ ttoo-esepty event fraob. The sett of events in dm tenenti a i Definition: The event component* generated by the sett in Dffl am caBoa the roodes of A The set of modes is denoted by % Each mode is to be associated with a steady-stats pattern of behavior. The reasons for this interpretation are simpls. If an event is involved in a steady itatt pattern of behavior, then all of the states connected to that event are also involved. For a state that is part of a steady-state pattern the situation is different Here, Jose one input event and one output event of the state are involved. So we me that is sod y suue u s IiaU st is m o wHI s ws sUa is l -wHh event c o n y o n o nis. In Section 1* welt strengths the eomwotion between *ts»dy«stojt* behavior art tfaoee event co mp on e nts that comprise the modes. Property SJ: Every part and every mode is strongly connected. This follows from the fact that N is be* 8QD and SOD, (lee Theeraro 2J) , Property 12: N it strongly con ne cted. Since N is conneeted (Axtom 1) end covered by strongly connected c ompon e nts (Property SJX it mutt be strongly connect ed. 11 The Parts: The main reason for Including putt in our definition of t system is so that we can define the notion of akernativsness. We begin by assuming that sencurrency and akernativeneu are mutually exclusive. That is, if two system elements may either hold or occur concurrently, then they cannot be considered alternative. The most natural way of guaranteeing that two elements _ ■■:■-.! ^rv ... ' ..,;;,.,■>■. ■■---**:: ^ '*.?;<(*» T >.<■-. • - ■ -.. ■ fft win never hoM or occur conc urr e nt ly is to require that they both be contained in a single Hoken state component - that is, a part But we don't want to say that u se e le me n ts are aterrwtive just because they belong to the same part For example, if die part consists of a single elementary circuit, then no two elements on the circuit can be said to be alternative. There U a situation, however, in which two elements would definitely be celled alternative: when they are alternatives in a choke. Since our theory is intended to be ty n u not rfca t with respect to the forwards and backwards directions of time, we include bath f erwasds sM eeAwatds choices, In Figure 90, Events «i and # s are alternative, as are Events # 3 and « 4 . We carry this idea one step further by defining the alternative dostife' & ft put If two elemsnts in a past aft^ajteatiet**, then their immediate successors wKMn the part are aho akernatrtev as arerthejr irttnedhtfe predecessors. Thus in Figure 12. States ^ and s» at we»a» Stteas ^mis ¥ wm nfa w ii a il u - 44 FfcjweM Aaeraedve Event* a. Figure S.2 AJtornett v« Statej a 4 ThUkUateforpuUiedwfoHonri, Definition: The fbnffH^ rtTftn f ff fff f * «- --*~i -i-m- „ f r fv^ ..-u >u.» VxcXp: XpCjX W« uy that X} and x, are aj&»&£ 0* W iff *i*»*i but *|i«fc (We do not ay that on «h*n e nt to elteiontlv e wirt i met.) - ate* «* ,*«& « •— -*' v Thoaram It For Pe?, * P fc an cqutvannce reletien on the rttii ten tib f P, and, VA « Xytey; Afil V AgE* tJ 'Each eQUivatamciau Mucosa? «, events.' ' If ■ is an equivalence relation on the «t X, then X/« induced by «. d e note! the set of equivalence chutes 45 Proof: Reftexivity and symmetry follow diroctly from the definition of .-ece* f or transitivity «d the second put of die theorem, we make use of the fact that two elements are related by «tp iff there U a state f rom (to) which there exist paths of equal length boding to (from) those two dements* Thus if aipb and bdji m'Uk^fatm^ timtikm lit which h*,hhft 2 | • a I I 1*6 *' Because a part is strongly connected (f r^serty SJX there exist paths jig and m as shown. This gives us paths of equal length leading from * to e and c - namely, stfstjstyii and MS*!**** Thus, e«tp£ and *p is transitive To set that a state and an event can never be a w stnaU ve, It is ertfy twceewjMo nott that eeiwasn iay two Half* aft path* are of even length while bet w ee n a state and an event aft paths are of odd length. D Now since «ep is an equivalence mletien on tht stoments of Pan ? , «tp;is>doeei;*' of P. Definition: For Pep, P*«<{W*p|se8p}. H<pl»«*pJ. * This fact may be verified by the reader. 46 Property 3 A P* is a ml The method of generating a quotient net ii iBuitrated in Figure 11 (a) Part P I {b,c} <b) Equivalence Classes Induced by a P Figure M (c) P Notice that the eoettant net In figure Si (e) tsaw etpmemafy efeeufc Thss is always the < What's more, the length of such a circuit is equal to the god (gnats* common divisor) of the lengras ot tne elementary qroms ubii esweiBeneme^aara Definition: If G is a strongly-connected directed graph, then, <jKO) - ged {n)n is me length of an elementary often* nN) Theorem $2r. For Pep, P* is an elementary circuit of tength ?<PX Proof: The definition of u f eliminated all branching, both forwards and backwards, in P*. Because P is strongly connected, so too is P*. it foMews that P* is an elementary circuit Let n be the length of the elementary circuit comprising P* We note that two elements belong to the same equivalence chut iff the length of every path be tw ee n the two is a multiple of n. Now each el e menta ry drat* m P may he viewed at a path starting and 47 terminating at tht tame element Therefore, th« length of each ehvnentary circuit tn P mutt be a nwktpte of ». Thus, n £ 7<P). Let m be a path in P that makes exactly em Org* of length/is h. Let a and t be to two endpomts. ctastfthere must ex»W Han f from which I and IT P*. It begins and ends in the same Such a path dearer exists. Its ft are in the.mme equivalence <T e^ hngth-hwding to e Because P is strongly connected, there exists a path m 5 from t to s. We now have two circuits: py^ >nd »a*l** Since every circuit, elementary or otherwise, can be decomposed into etsmentary circuits, it fofews that t(P) divides me l e ngm i e^ j | cif<oi>» m P. In .pnrttcttlar,^^^ m*™T* also divide the difference between fc^) and%|^ But Bus Is just n. Therefore, yPp^n. ftbeae wehst sJrendt>ebeom mil fmyPn i inMwltt*^ffi* t Jp ^ The state graph In Figure 3.4(e) has two elementary drains, one of length » and the other of length 12. The quotient net induced by mis state graph U shown hi Figure 9.4(b). It is an elementary circuit of length 4, which is die g ed of 8 and Gt 48 {a,c,e} ■4 »^| CI'.3;^H {2,4,6,8} {b,d,f,g} (b) P FifurcK4 What we've done so far is to gtnerttt » iiparttt f*dtht Mt f or «»ch ptrt In order to construct a single quotient n«t for the wftra iyi«i> t ^^ ttt« 1»^« <e ipok »t the possible relationships between two alternative classes from two different parts. There are three possibilities; (I) the alternative classes are disjoint, <*) they partially overlap, or (S) they are Wentkal Since we need a partition of the system dements to construct a quotient system, we must exclude the second possibility, alternative classes that partially overlap. This is accomplished with die following axiom. 49 Axiom* VP^PjC^: VfcXp^^: VrcXpj/^ ffTr-4 V f-r Two alternative ctattiei tre either «tjMHHV Figure 16 ithiitratei the type of notation that ta pfehtMted by this axiom. Part P t generates an alternative 4a* containinf ili«-«««Hla-«|'-«n»^%' ^WMt-^lptelii* an aRernaaw cku containing the single event «|. The two alternative daises overlap Identical. Figures. 5 Partially Overtopping Aternetive Classes At a remit of Axiom 4. we now have an equivalmet relation on tlw sit of syaem elements. Definition: u - J^eCp * »» the ajeragyjnjss. gajga& f * * 50 Property 3.4 oi U an equivalence rttatlon on x,»»d, y „ rV VA c X/rf: AcS V Ac E •Each equivalence cJatMftdufid a? * m****** m**x*f state or exclusively •vents. Since « is an equivalence relation onto elements of the net N,u induces a quotient net of N. Definition: The control structure for $ U the quote* net N* - ** E* FS where; S'-tfi^lJtS} it^act $ E*-{I*^|«eE} (to meting! of £ X* denotes S«UE* We writer to nwea <**>€**. (Rota! that xy means <x.y> c F.) For^tX* ""\ . ,•""" PropertyS.5 N* to a ml (N* wi» m fctoprelad u a M net) The steps involved in generating a control structure are ffiustrated kfcF%ure SJft. Notke that the control structure mar be viewed u an tntsrconMttfcm of to ststontary circuits generated by the parts. From this we have to follo win g . - V*-*?»tv *-Wfc*,-$,"%. -**-"*-. ■i^^^S^M^i^^K:"..'-*^'' 51 rg u <* <^ . *. « <o a 1 X> (•»(*>« KV tf> C »*» 0) n o s •p CO SB ■P I « O n -p a o a a •H ■P 10 M 0) (3 O n •H 52 o d) •H 0) n 3 •P u H ■P Ui o n +> c o u a> -a 0) 3 c •H c o o a n M O 4) > ■H * 0) 4J H << 9) ■ CO ai n & •H fa 53 Property 16 N* it strongly connected. And there is something else that we can say about N* Theorem SA N* to an event graph. Proof: Each link I belongs to at wast one part Lit P bt such a part Then / to contained in the elementary drcutt generated by P. Within that eJrwK. / has a unique input meeting and a unique output meeting. Because P to a statt component, theae two meetings contain all the events that are adjMent to the states in L fherafore, mere can be no other meetings connected to /• Since it to our custom not to txpUdtty show the states in an event graph, the links in a control structure will be drawn as . . . links'. Thus, the control structure tot Figure 16(d) win" be depicted as fen Figure 17. M {...} M Figure 3. 7 A Control Structure (Abbreviated Representation) -*H-^'-** **-"" » J - *^"' *•*' M Between the system net N and the control structure. N* there eiistt an important structural relationship, one that will be used in relating system behavior to control behavior. The relationship is Mntstrated in Figure 18 and is expressed by the fouowtag theorem. Figure 5.8 Theorem 14 VecE: WeS*: /♦M* ~ I in*«| - 1 The preconditions of Event # select ont state from each input hnk of W^-' Cr^*/ ~ |lfV|-l The postconditions of Event « stent one state from each output hnk of M^-' (a) (b) (0 (d) »;$£j^-i0!^:3;£?*g^ 56 Proof: The theorem follows from then observations, (I) A meetine*m*nd««nkx4 an conn erts d « Ht Jfr these it * par* P each that m and / are connected in P*. (2) m and / atteonMcted in P* iff each -even *«* Mnasil s d tooaactfrooe state jtfct, (I) if et and I arenot conmct s d in W*. dw» woenn m I » es n g o t te d teen etc* m -et a 15. The Mode*: The model arc event components of the seaserA »*;X. The event co m p on e nts of N have an Lemma XL If at is an event com p o ne n t of N, men, Vf/cX* PCiinfli^unrl \i, 'An event component intersects all aksmativecevasei the same number of times.' Proof: An event component selects all arcs into and^iejaf an eveiit aiid one arc Into and one arc out of a state. Prom ija j i n jw It we then haveO ■""-""jfT "-■■■ V' . i sp , "' : .-t -' "y* v - ■-<**■ ■ ■ ' . ' - " P "$T *. This fact, together with the cownocttvtty of N* pr o duce s the desired result Q Modes are the structures that correspond to iteadT-etatt paiterm of behavior. We shall take the term 'steady-state' to mean that a mode intersects an ehernauvt dass in no more than one element. 86 Axiom* VMcflk VfcX*: PC M Hf| ^ t 'Anted* and an alternative diss internet in In figure S£ we presented a system net together with a the modei In Figure 34 we yet e eamplstt systole, setlsfled. Wten these are combined with tetsfy diet Axiom 5 is 1 6 Figures. 9 Modet From Lemma SJ and Axiom 5 it follows that a mode either dees not intersect any alternative class at all, or intersects each alternative dan exactly erne. But die first cut cannot be, since it would imply a mode with no elements. 87 Theorem 15: VMaffl: VfeXV PCsjnel-1 A mOOt IHWHlgl HOI awonienTe cs« oxacay once. Corollary 3J: VtaX* ty £ UN The tin of an alternative dan cannot be greater than the number of modes.' Theorem 15 together with the next theorem establish an tmpeftint relationship between each mode and the control structure. Theorem 18: VMcfll: Vx,y€X M : <*,v>eF M ~ M**W* There is an arc in M connecting x to y iff there is an arc m N* connectinf fej* to Proof : «► Definition of N* as a quotient net ♦ Assume M^W*- Either x or><botno*botb>» an event Assume .tfi x. By Theorem 14 and the definition of a mode as an event component, there exists an element x in X M fK^ such that <x > z>cFjj ( . But by Theorem St we knew mat mare U only one element in X M n lyl^. Therefore, y - z and <x,y>cF M . O Corollary Ifc VMalfc M is isomorphic to N* 'Each mode is isomorphic to mi control structure,' We now have a nice visual interpretation fOf the dan ot nets produced by Axioms 1 through 5. Each net in this dan can be viewed as an Interconnection of isomorphic event graphs. If we imagine the elements m each alternative class to be vertically in tine, then each mode wilt be 58 roughly horizontal (see Figure S.10). In the top view, alternatives are indistinguishable. So too are the modes. Their projection forms the control structure In the side view, we can distinguish between the alternatives in an alternative class, and we can identify the individual modes. TOP VIEW Control Structure SIDE VIEW Individual Modes Figure 3. 10 Views of a System Net From the structure of the modes, we can say something about the structure of the parts. Theorem 8.7: Vp€/>: VMeTTl; POM is an elementary circuit of length <y<P). 59 Proof: P* is an elementary circuit of length <y(P). Since M is isomorphic to N $ , M contains an elementary circuit of length <y(P) whose image is P*. This circuit is also contained in P. D Corollary S3: VP«p: P is covered by elementary circuits of length <y(P). 3.6. An Initialized System: Over the last four sections, we've established the structural properties of the system A We're now ready to consider the behavioral properties of the initialized system £.. Definition: £• <ZJ>pJ>n^> where Z - <S, E, F, I> IfiS VAcDp: |Ani|-l lis the set of initial conditions of I. Z is the initialized system net The third requirement says that I assigns exactly one initial condition to each part If we think of I as the system 'hardware', then the set of initial conditions may be viewed as the system 'software'. With this interpretation, a piece of software (Le. a program) has no meaning outside the context of a system. This is exactly as it should be. Since Z is an initialized Petri net, the Simulation Rule an be applied. Definition: The simulations of Z are called system simulations. Because Z is covered by 1-token state components, namely the parts, the results of Section 23 are applicable 60 Property 3.7: Within a system simulation, all instances of the same element are totally ordered. Property 3.8: If <xjm> and <x,n> are instances within a system simulation, then <xjn> is the next instance of x following <x,m> iff n-m-rt. We've introduced the initialized system net, and now we introduce the 'initialized control structure'. We use the initial conditions of the system net to generate a corresponding initialization of the control structure. Definition: Z* - <N* I*> where I*-{MeJ S€l l Z* is the initialized control structure In Figure 3.11(a), we show an initialization of the system net from Figure 3.6(a). In Figure 3.11(b), we show the corresponding initialization of the control strucure from Figure 3.6(d). 81 , JtuVr^ ■%*•"«- s (a) Z FlgttreS.il An imuaased System Wit and Definition: Th« ilmuhtlom of Z* are celled control simulations. In an event graph, each elementary draft to aauifcteen^aeht, and vice vena. The control structure has a special covering of elementary circuit! gw e wl e d by the parts. Because each part to assigned one token by X the corresponding elementary circuit to assigned one token by I*. Theorems J: 2» to covered fcyBefcen state c onyene m Coronary 5.4: Within a control simutauon, *H ordered. instancei of the same alternative data are totally 62 Corollary 3.5: If <qjn> and <qji> are instances within a control simulation, then <q?i> is the next instance of q following <qjn> iff n»n-*i. We now show that for each system simulation, there is a corresponding control simulation, and two simulations are isomorphic Definition: If T is the system simulation <H,O.C> and q e HUO, then ©T<?> " < W3*« KrcHUO | r£f A htf}\ > Gj(q) is going to be the image of q in the control simulation corresponding to T. Notice that Qj(q) is an instance of the alternative class to which 9 belongs. Thus, if two instances in T are associated with alternatives, then those two instances will map into the same type of instance in the control simulation. Because of this, the instance number assigned to &f(q) is not necessarily the instance number of q. We must count the number of instances in T that precede (£) q and are associated with the same alternative class as q. The instance number of 9j(q ) will never be leu than the instance number of q. Definition: If T is the system simulation <H.O,C>, then, T* - <e T (H) l e T (0),» r <C)>t In Figure 3.12(a) is a simulation of the initialized system net in Figure 3.11(a). In Figure 3.12(b) is the corresponding simulation generated by 6^. Notice that the second holding of State b in T corresponds to the third holding of Link {b,c} in T*. The next two theorems establish the relationship between T and T* and the relationship between Z* and T*. T 0t(C) - {<%(?),9 T (r)>|< ? />eC} 63 a • 2 •: d • 3>: e • 5>. c ■ 4 > a • 7 • 1 •; / i • 3> 8> e • (a) T Figure 3.12 Corresponding Simulations 64 W {..; {'•' {..: "■ c }\ W {a}/{./K {g} c} \ {t} / { *- ,} " {0} / {e,^. {g} (5,6) {d} /{M}' w (b) T* Figure 3.12 (Continued) b 65 Theorem 3.9: If T is a system simulation, then 9j is an isomorphism from T to T*. Proof: 6x *« clearly onto. Now suppose that 0r(ft) - 0T<ftX Then and, Kr | r*ft A r^JI - «r | r£ft A fVfyl (2) Let e - [f ^ - [9 2 ]*- Since e is an alternative class, there exists a part containing all the elements of c. Consequently, the instances of elements belonging to e are totally ordered. Line (2) says that ft and ft appear at the same point in that total ordering. Hence, ft - ft and T is 1-1. If C is the causality relation for T and C* the causality relation for T*. then it follows immediately from the definition of T* that, <q,r>*C 4» <6r(j), 9i<r)> « C* □ Theorem SJO: If T is a system simulation, then T* is a control simulation. Proof: If T is the initial simulation of Z, then T - <Ix{|}, +, +> and T* - <{Ci]eJs«I}x{l}. ♦. ♦>• But [bXtUel] - 1*. and therefore, T* is the initial simulation of Z*. Suppose now that Tj satisfies the requirements of the theorem, and that Tj Is derived from Tj through a single application of Step 2 of the Simulation Rule. Let, Tj - <Hj, Oj, C!> T 2 - <H 2 . Oj, C 2 > V - <Hf, Of, Cf> T 2 * - <Hj*. Oj*. C,S Now there must exist a set of holdings A in the front boundary of Tj consisting of one holding for each precondition of an event « and such that, H 2 - H, U *e\ rty 2 - Oj U fl<«, 0{i C 2 - C t U Ax^.0!) U iK#,0 1 )xiK* , ^ 1 ) We must show that a similar relationship exists between T t * and T 2 *. We note that M^ c E*. Let A* - 6t.(A). Because A is contained in the front boundary of Tj. and Q Tl is an isomorphism, A* must be contained in the front boundary of Tf. By Theorem l«a 66 & b), A* consists of one holding for each precondition of U^. For the three component* of T 2 * we have, H 2 *-e T2 (H 2 ) -e Tl <Hi>ue Tl <f(«\H 1 )) <»> o 2 *-e T2 (o 2 ) - er^juer^Oi)) (2) C 2 * - {<8r 2 (f >.e T2 (r)>l<f,r>eC 2 } - {<e T2 (?),e T2 (r)>|<?,r>eC 1 } (3) U {<e T ,(f).e T .(r)>|<f,r>€Ax^«,0 1 )} z z U {<Q Tl (q)J^ l (r)>\<qjr>€^*,Oi)^'Mi)} Since Ti is, in effect, a 'prefix' of T 2 , we have e^C?) - e^fo) f« all f tfliUOi- Thus, 9 T2 (A)-e Tl (A)-A* ©T 2 < H 1> - OtjWi) - H l* (4> eT 2 <Oj) - Bt^OP - Of <5) {<e T2 (?)« e T2 (r)>|<?,r>eC 1 } - {<9 Tl <?), 9 Tl (r)>|<j/>eC 1 } - C t * <6) Let <s,n> be a holding in ^'.Hj). Because [s] u is an alternative class, there exists a part containing all the states of b] u . Therefore, the holdings of states belonging to b\ u are totally ordered in both T l and T 2 . Furthermore, <*, n> is the last holding in the total ordering of T 2 . From all this, we get, BtMi'Hi)) - {<M*.«>I *«' »"d « »* *« number of holdings in H 2 of states belonging to - {<[i] oC ,n>|i€<* and n is the number of holdings in H t of states belonging to Wot " P ,UI U But by Theorem 14(c & d), {tsjji«0 - {WJ &k« W^*}. This, together with the fact that 6-r is a bijection, gives us, Gt,(iK«*. Hj)) - {<&]*» n> l M* 6 M** and n u the number rf *n«ances of D]^ in z Hf- plus 1} -iKM^.Hf O) Similarly, e Tl <i(«,o 1 )).t(i#k.<V) W 67 From Lines (7) and (8) and the fact that 8t s <A) - A*, i<9rj*>. *r,M>l<f n * a*^)} - A'xefl^.0^ W {<%,<*>. «T 2 <'W<f/> iffcOj^e^fftf - '#^f» ^«f©U*. »1*> (l0) Finally, wt get, H^-iyuoH/.Hj*) Llnesl,4.fc7 O^.Ot'UfCU^.O!*) Llnes2.5.*8 C,* - Cj* U A*^^*) M.^N^^') *•*"•* * 6 «* * W Since, by hypothesis, Tf i» a sMatton Of Z», m must condudt that T,* to also a simulation of Z*. ° Coronary SA For aach spam ismutotfon, there to a cormawKUr^ control tkwriathm, wrf tiw Ww simulations art Isamorphlc, Nam that the co r r aipoii d anw bttwawi iyn«rn Urmdatlom arid oootrot stomilaaero to not, in general, one-to-one. In mo* cam more will be si sy*sm sUmitaitoru mapping into a single control simulation. 8.7. Examples of ffffllMlltf ffTftffTT In thUstctton.i* present thr«ttx»mpte» of mitialtooi systems. For each one we provide an Interpretation. The formal technique! developed in the J|«ewii|h<cha|>tefs will confirm these interpretations. The inittahwd system depicted in Figure Sfl r e pres e n ts a three-*age bit pipeline The three parts comprise the three stages. Each made mm^^ Ujlm^ttim^ <*"*"* , b^format^on^ •Bits' enter at the topmost stage and are passed from stage to stage untU they are lost at the bottommost stage. ^-■■i^i^-p^ 68 ' 1,,: ' -Iff'- t , ' V '"- S ' i *- ; 1 V « e iH 01 «■ * f» en y*-i ■" ';%-V 0i £ 1 W N «0 •H .*•»■. '■H c « 69 {b,c} {...} {"•'} (d) Initialized Control Structure Figure 3.13 (Continued) 70 Tht inittatiMd system shown in Figure 1W to formed by taking a four-stage bit pipeline and connecting the first and test stages. Tht remk toa ctroiktttnf Wt pipeline. Netke that in this case, •tots' are conserved. The initialled system of Figure JU5 desoiMra half adder. The choices associated with States a and » represent the two binary (npetr. the reverse chokes aseadated with States k and / represent, respectively, the sum and carry outputs. Thert are four modes and they correspond to the four possibtt operations. Notice that the system net is covered by four Hoken state components. We've chosen two of those i| ear parts. Although the choice Is arbitrary, it has no effect on the resulting control structure {There pm. however. sttuetions in which this is not the case. The net in Figure 116 U tn examett. Defending on which covering of state components is selected, either of two control structures wM be generate*. The ssinsfkancc of this is not yet 71 (a) Initialised System Net Figure 3.14 circulating Sit pipeline 72 1 1 6 6 5 5 (b) Parts Figure 3.14 (Continued) 73 v o 74 (d) Initialized Control Structure Figure 3.14 (Continued) -t r - * , - ft . ■ 75 Input A Sum Carry (a) Initialised System Net Figure 3.15 Half Adder 76 1 I \ I 0, A *-* in o • M 77 I 4J a 8 *-. m 0) M •rl 78 m «* i n M i . ii M i nn U ' JEa i 1 •naiOTM "2 ■5 H o -4 « 3. ■H ft* 79 {,,2> R □ M '{*•*)//$ \\ w 1 xt ef } {5,6,7,8}["T Or 1 \H i} {*-}\ /v WW {^w)0 * Cl(»*,>a} {»} (d) Initialized Control Structure Figure^ 3.15 ^C^i#6ittued> Figure 3.16 System Net with Two Control Structures *--. -, ■■.^. < a^'^*^*^'a*fe**;^ 80 CHAPTER 4 INFORMATION 4J. Inf orfnation, CggasE In this chapter we continue with our study of the system A In Chapter S, w« showed that the control structure N* d e t e r m ines those sJpffti of behavior that result when alternatives are made indistinguishable We are now Interemd in provUinf the ability to distinguish between alternatives. We introduce the notion of 'Information context' for that purpose. Definition: The set of parts contaiiUng Elemtnt vis denoted by ?(xX The set of modes containing Element x is denoted by UKvX Definition: ForxcX, I(x)-m-T!Kx) Kx) to the set of modes excluded from ^ Ifat) to rtie inf ormation content of x. The reason for defining information content as the set-el excluded rather than included modes has to do with the (psotuttoa of xhokei. This if dbxnsswl m Sections 43 and 4.4. We might note that when an element has no akemauvei, there ale no modes excluded (Theorem W) and. therefore, the information content of the element is mnt It to convenient to associate a color with each flwde. The information content of an element ' This resembles a definition by Heft and Commoner 0S1 bi the context of a strongly connected state graph, they defined the Wormxtion sst'ofastatetebethesetof excluded elementary circuits. j1»¥!iSW*W**Wft***S*l«SR»'^»s can then be viewed u the set of colore associated with the exduded modet. In Figures 4J through 43 ere the system nets for the systems described m Figure US through SJ5. We've associated a color with the events defining each mode. Next to each system element to its information content expressed as a set of colors. We now show that inf ormattori content dots iedeeddtottnguish between alternatives. Theorem 4 J: tej^cX: If two elements belong to the^s ^ateama ttve dm and have the same information content, then they mutt bJMue simeiehMpBW v * Proof: * Obvious * This part of the theorem foltowi ftnm thew ebesnfationi. (aJI^W^^Wxj^TWxj) s (b) Each element is contained » at toast one j (c) An*odemteriectotniltenMUireclattmexacth;cmfhwm»»t □ So now a system element can be uoje^ JdeMtfJfd -bjr spedfytog two things: 0) the ajternattve ch«towhkhitbdoi^iJ»d(2)iOiDl9n!aa9!L£fi!fflS: 45. Inf ormation Flow: Suppose that qj and o^ are instances in a system il mutetmn , and that there is an elementary causal co nn ect i o n leading from 04 to <fr 82 Red = {1,3,5,7} Violet = {2,4,6,8} Figure 4.1 Bit Pipeline - Information Contents of the System Elements 83 Red = {1,3,0,7} Violet = {2,4,6,8} Pigure 4.2 Circulating Bit Pipeline t Information contents of the System Elements 84 Green = j 1,3,5,9,10,12 Red j 1,4, 6, 9, 11, 12 Orange = (2,3,7,9,11,12 Violet = (2,4,8,9,10,13 Figure 4.3 Half Adder - Information Contents of the Syetem Elements 85 9l Let qj be an instance of x v and q 2 an instance of x 2 . Associated with q x is the information content of Xj, and associated with q 2 is the information content of x 2 . We shall interpret the information that is common to both Xj and x 2 as 'flowing' from q } to q 2 - Our convention of associating modes with colors permits a graphic representation of information flow. The arcs of a system simulation are colored according to the following algorithm: An arc connecting instance <X|,?t|> with instance <x 2 ,n 2 > is assigned a particular color iff the mode represented by that color is contained in Ify) n I(x 2 ). In Figures 4.4 through 4.6 are some simulations for the systems described in Figures 3.13 through 3.15. Using the correspondence between colors and modes given in Figures 4.1 through 45, we've indicated the colors assigned to each arc The reader is encouraged to do the actual coloring. Note that some ares may be assigned several colors, while other arcs may be assigned no colors at all. This formaliiation of information flow corresponds remarkably well with intuition. In Figure 4.4, we can see quite clearly the flow of "bits'* down the bit pipeline. The two colors correspond to the two different bits. At Events 1 and 2, bits enter the pipeline At Events 3 and 4, the bits are transferred from the first to the second stage. At Events 5 and 6, the bits are transferred from the second to the third stage And finally, at Events 7 and 8, the bits are lost As expected, in the circulating bit pipeline, bits are conserved. As shown in Figure 4.5, the same two bits are present at the beginning of the simulation and the end of the simulation. * The notion of a *bit' is very restrictive and is used hen only in an informal manner. Formally, information is expressed in terms of excluded modes, not in terms of bits. 86 1 •; b y d > a .• e •. 5> y c % h^. 4 > R 7 > * ■•- g R 1 • 6 >: b > d .• 3 ;•: V a • e V 5>; 7> g • Figure 4.4 Bit Pipeline - Information Flow 87 • J • c Figure 4.5 Circulating Bit Pipeline - Information Flow :^^S^«S^ m o ♦ c •H a H ! H 10 » M §. •H O O 89 With the half adder, the situation become! more complicated. It it no longer possible to interpret information flow in terms of bits. But the flow of information still corresponds to our intuition. As shown in Figure 4.6, information enters at the designated inputs - Events 1, 2, 3, and 4 - and is lost at the designated outputs - Events 10, II, 12, and IS. Notice that in each of the two middle simulations, information is also lost at an interior event In the '04' operation, the color orange is lost at Event 6, while in the 'l-ttf operation the color red is lost at Event 7. At Events 5 and 8, there is no such information loss. The reasons for this are simple. In the case of both 0-rt and 1*0, we get the same outputs - a sum of 1 and a carry of 0. In these two situations we are unable to reconstruct the inputs from the outputs. The information lost at Events 6 and 7 is what allows us to distinguish between OH and 1*0. In the cases of 0*0 and 14, the conservation of information at Events 5 and 8 corresponds to the fact that, in both cases, the inputs can be reconstructed from the outputs. This short discussion is a preview of the ideas contained in the next two sections and in Chapter 6. We mention now an interpretation for information flow that the reader might find helpful. We've shown that the control structure determines those aspects of behavior that result when the alternatives in an alternative class are lumped together. We've also shown that information content provides a way of distinguishing between alternatives. Our practice of associating modes with colors then permits us to think of information as colors assigned to the 'tokens' on the control structure. The colors assigned to each token determine a unique system element By defining appropriate color transformations for the meetings in the control structure, we can duplicate the behavior of the original system. 4J. RqylyjftgClwks . ^. We've tttt nethief te far resotutiort of cholcei teofc* ** coafemt and 'the or We might ask how the tatfartratfait c o ntent! of « ant * art rohtfod, The foflowtng answers that qiMttton. w * I<#)-Kj)U !«*•-{#)> (*) ♦* * IW-Kj)UWVW) (b) Thr infnniilim «ntpt #c ipeji rtn bifaimiw 11 model cowtof •§ eatprt Qapat) own* ef * eaeipt *• «t tlwi ph* the Mt of ^« (a) (b) 91 Proof : We prove just Part (a). Because an evert ampenamsele&eUa^ fflw-mu*) Since *cj*, Ms 9 ) - W*> U TftU'-W) Thus, B«aiuie TTK«)nTIKi '-{*})•♦ CTMowmW), TW«) - Ms) - W-W And. From thedefmitioneftofonnetioa content we get* Corollary 4.1: VxcS: V«e£: («vw) # IWcK*) The Information content of an event contain* the information content of each precondition an« each postcondition of the event' - To iltuttrate Theorem 4.2. we note that in Figure 4J, I(S)-{Y}, I(d)-4, and M4)-{V}. So we have I(3M(d)UlTK4) u predicted. Coronary 4J meant that, with our scheme for coloring the arcs of a system simulation, the colors entering and leaving a holding are the same In other words, colors appear and disappear only at occurrences. Whit is the significance of Theorem 48? to the case of tn, t is one of the aim nati » n in the forward! chalet associated with i. Whin Hm olHWoHs iiiujwissuJ in twocowjoe Of a system- simulation, it will have to be resolved. (We are not co nc erned at the moment wfcetiier this is a free choice or a constrained choice, or possibly a combination of me two.> RwoMng «he choice is equivalent to selecting one of the aternatives in s\ But setsctmg an event in # is equivalent to specifying the modes that cover the remaining events in s*. (Given UK**-M), we-caii determine WM and thus #.) Therefore, the information gained is going f*em / to one of the events in s' resolves the forwards choice associated with*? No«* mat when #* the only ^Ite^ative' in s\ there is no choice to be resolved and mere is no informatfcMjpttned. For the case where «•*, everything is reversed. We are now dealing with Ha** backwards choice associated with s. Instead of (atking aboet tM Infomw^iiei gemed to going from t to #. we talk about the information Jest in going from « to $. That mfbl i ae i Ion l o u l m ti nt backwards choice assoc ia t ed with s. It Is what we would need to %ecfc up' fiom Stale * to one of the events In # «. 4.4. Resolving Conflict In the preceding section, we looked % the fefcttenitrty b e tw e wi <he taforroatton content of an event and the information content of a tingle precondition (peetoondttlon) of the event We now look at the relationship between the information content of an event and the combined information of ajl the event's preconditions (postcondtttoiu). From CoroHary 4J, we have the foflowing • hV* ,*:■/£*, t%l-**t&*4*'r » • m Property 41 VeeE: I('e)cl(«) and «t-)sKf) The information content of an event ojnteins th« combined information content of the eventrs precondttions (portcondtttom). The concepts of 'information gain' tnd 'information leu' at an event foflow naturally. Definition: ForecE, I^e)-KeH(e7 <a> r<e) - I(eH(e*) (b) I^t)U the infornaasaOMl»t Event e. He) is the information km at Event e. The Information g»in (lots) at Event e is lie inrcrmajton oontent ef e minus the combined infuj motion content of ct precBneBttini^neeleinnwons^ ■ In Tables 4J-44 we Hat the information gains and knee* for 4he event! tot Figures 41-45. ^^ 1 - , L.._. ., . ■ Note that these tablet are entirely consistent with our remarks hi Section 4.2 We can think ef information gain as inf ornwiion -that entere a system from the system environment, and we can think of Information losi as iitf ortratftm peawd f font the system to the system environment The significance of Information gam and information loss ttes hi their relationship to conflict The term 'conflict' has bom applied to the sftuatten in which two events are concurrently enabled and have a common precondition. Such a situation is shown m Figure 4.7. But for the class of structures we're dealing with, (forwards) conflict can arise only when two events have the same set of preconditions. (This is catted free, choke. ) The reasons f Or this are as follows. If two ;r*^^?gj?^&#i£^^ 94 .J-*-v K?.7i: I (•) I (e) r(e) fie)' [v} * UO * * t * * * * * ■ +« * * Cv) 0. ,,, t*}.* 1 2 3 4 5 € 7 & Table 4.1 .•'• Bit -Pipviia**? *-i ■■■■- Information Gains 1 2 3 ' -<> » ::^ ,, f^tk^-j;..; , 3 /■.;'* <*•■:= *$%'; « * ;-..-*■ .. * ys;'.»ii- ■»! fc>* 5-J^,, , * ^ * S.** fk.¥~\.& ,y.#: , ; J* :>. ■■■' i,K^ *i^ :, V :: y^-Si ::■■■■'■ . - Table 4.2 «tal«*«M#SHl*t?J8i*i»line Information Gains p ''-■> kSll 95 I (e) I (e) 1 [o,v} * 2 {g,r} t 3 {R,V} t 4 [g,o] t 5 rf t 6 ft {0} 7 t [R] 8 t ^ 9 t t 10 t {R-0} 11 ft {G,V} 12 9<> {v} 13 t {g,r,o} Table 4.3 Half Adder - Information Gains and Losses events have a common precondition, then they mat beting to the Mow meeting. By theorem S.4, each event selects exactly one state from each moot tmk of that meeting. Because each link is contained within a 1-token state coMpemnt (* pnrft no two statet in the same link can hold concurrently. It follows that if the two events arc to be enabled conc ur re ntl y, then they must have the same preconditions. As a result, the tttutaon d e picted m Figure 4.7 cannot arise. However, the situation in Figure 4J can. It should be noted that ■ mjtha u j we've said applsss not only to forwards confMct but to backward* conflict, at wet Figure 4.7 Figure*,* Since in our theory forward* and back w ards conflict coincides with certain structural configurations, we might as well define 'conf tet' m nmaursl terms. Definition: Fore^cE, W We «iy that e 1 Mid H are In forwards fflftfltt*f ^^^ Weiflrthatej irKJ«,>rtin btdLWM^coBnkt tff ■ 1 y'» t MiAt 1 ^. (We do not say that an event to In conflict with Itself .) Property 4.2: x**" ' X" **• •ojuiviliiKi relations en E. Definition: The equivalenct dasm of X + we called foryirds conflict classes. The equivalence CIUMI W J[ MW^jW^. jjpjj |)ff|yf l3 Blm|JJPJ**r ■■■;■■ Property 4J: VeoE, The forward* (backwards) conflict dan alternative daw ■isociawd with «.' owpB^H^BaBi^Biw ^»w»ee ^ •• (a) within the In Tables 4.4-4* we tat the forwards and backwards conflict da** for the system nea in figures 4J-4J. {«} w {*} {2} W m {4} W « « ro W « {73} (a) Forwards (b) Backwards Table 4.4 Bit Pipeline - Conflict Classes w ■» . ■» »■ .a PI {4} {4} w {»} w W ro ro «;.,. $ (») Forwsj<U (b) Backwards Table 43 Cireulatin| Bit Pipeline Conflict denes ~~ m & m m m w m w pi m » M m w (a) Tattfei* aftm Wt now HuMUk the and the rtttttonaMp ft* and fqnwrdf conflict chum, ;»"*'■ II ¥wdE. tijy" * T t i pf of Proof: Wt provt Pwt (»). V «•» w (b) Thoonm 14<a)fc(b) dofttiMon • . ,.-,....£„. ..)„-,. 99 Theorem 43; ¥#•£: The information gamed (tort) at Event § U eaual to tht Mt of mote covering thoN events m towards (backwards) conflict with «.' Proof: We prove Part (a). r"W • K*HC«) definition - Ke>- JL£ K*) definition - Q (K«)-Ki» DeMorgam's Uw - Q ffld'-W) Theorem 45(a) - UK, Q <*•-«» Theorems " W{ ri*t i>W B ° 0k,n AI ** ,m -1Rtt»L*-{«}) Lemma 4.1(a) a The reader may verify this theorem by comparing tht information fains and tones in Tables 4J-4J with the forwards and backwards conflict classes of Tables 4.4-4.8. For example, in Table 4J, we see that the information gain of Event 1 in the bit pipeline is {V}, In Table 4.4, we see that Event 1 is in forwards confUct with Event 2. The set of modes covering Event 2 is {V}. It checks. We note that when an event is not in forwards (backward!) conflict with any other event, its ISO information (Ion) ti miH. Thus, mfu n ntUon fc gamed (tost) at predseh; those points where there is forwards (backwards) conflict Furthermore, the Information gamed or fast in a conflict situation specifies how the conflict is resolved. TMa is bicami sstsctlng an event la a conflict data to equivalent to specifying the modes covering the remaining «▼«*• ~fHw& either em we can derive the other. KM CHAPTERS C^TRQJU &1 Event Graph* In Chapter S, we showed that «ch system simulation is isornornhic t© a simulation of the control structure. Since the control structure is an event $raph.,any ijwulu w obtain for event* graph simulations can be applied to system limufettoov ThU to fortunate becawe event-graph .■,*■■ simulations have some very nice properties. Those properties are Hie subject of this chapter. Before getting »»■**> "wb, we must introduce some rwxatiw and term in olo gy . \ Definition: For a directed Graph C, 11(C) denotes the paths of ; o) Definition: For a path p in a directed graph, > denotes the initial endpoint (tail) of p I the terminal endpojnt (hod)af # Definition: If * is a path in the directed graph G, and x is a vertex of G, then, xcji iff x appears mm Definition: For paths at| and « 2 * n * directed graph. * We're repeating the definition of 11(G) given in Chapter 2. Definition: If » Ui path In the directed graph G, end AHasetof verttoeiof G,thcn, |»| A denotes tht number of tiw Mr Hmmu of A appears in *. If <N4> it an inttialUed event graph, and»lsapethinN,thenki(iis called the token taedine* on «.. Definition: A circuit Is a path whose two endpotnti ate the same, An fJpiaSM ldEglil t,lt c * ftutt ' ' tti S no «eim to encenin** mo* Jwl T e ^ ^ ' fj(0) denotes the drew* of fltyji denotes the etMMMuf dreeto of Definition: In an tnttafttad event graph, a Wat atdi » t dm* «entaWnf no initial conditions (no tofeans'X A fcejfccfegg * '■* * tmm *t «itw« eoiilaininf eaactfjr one Initial eendtten (enpettf ene WeaV^ 5.2. Paths: Many of the ideas in this chapter folate tepadM, the eeJhi mows* avephs and the patha In event-graph simulations. Wc befin with baik ctrcttlta Property &k In an mtttahsed event graph, the be* dree* and the t-esken Mate comp o n e nts estioe\ejh44tfn l 4tt This can be seen from the fallowing . (a) In an event graph, each Hate hat exactly one toe**** arc and otic emergent arc (b) In a state com p onen t , each event has exactly ene incident are and one emergent arc (c) A state component is connected. m When an initialized event graph U covered by basic circuits, we know from Corollary ZS that in each simulation of the event graph all instances of the same element are totally ordered. We also have the following lemma. Lemma 5J: If Z U an Initialized event graph covered by basfc drcutts, I U the set of initial condittojutof Z, % C is the causality relation fotf liimiteuen of Z, then for «x 1 ^ 1 >,<x 1 nj»eC, n 2 «4i} ^ * x dl nj-nj+l «- Xjcl If there U an elementary causal cpu#tten leading from Instance <*!*!> to Instance <x 2 ,n 2 >, then n s -n t for xjeS and igmfil for x&V Proof: From Theorem t***%i*» **mtj& ******* *k Ih4h**«im graph f or Z, and therefore, must be contained tn a basic circuit of Z. The image of that basic circuit in the simulation associated wtti C is a single strand (Cowilwy W » *Mch <x lt nt> and <x*n t > are consecutive instancll Tnt^itrii^K« t^itfl. ifU O W v fh« IttM beginning at the unique initial condition of the basic ctecoft. Since the instances of each element are numbered conserve!* the i number of an. instance tad*t strand todicaw which cycle the instance appears ft. TWlniuYfflnlJrlflfM^ mtmn^tnmffm wii*w<i*»»ing of the tnl^Uondttion umm^SilMmmi^ ^ ^ ■ * ^ ' ° In Figure U is an initialized event gfapl%&%ered bf bit* ctotutti IiiflguwWfli » Emulation of that event graph tot which each hotting of in to*** €**&* ******** dashod <*** Notice that instance numbers are in c r eme n ted by 1 at each holding of an initial condition, and that they remain [the same at all other Instances. FlfunS.t InlttallnH Keent of LemeM 54. Theorem 64: If Z to an i ntt ta tyi ietf ej|an|j^^4a!fl|l)^ T ii tin mi iif InliU) uiiliitiMH i| T e , .' ' T to a stamfcttafi of '% thin, " If # s and * t w« paths (causal token to T having the same then the Proof: Let , r 1 -*r x -<x^> and rf-cj'-^/o. By Uraim 54* |hi conditions crowd by both #} and r t U n-tn for x*I and Mr** r-ohI for vol In either caw Q As an illustration of Theorem 54, consider the foHowmg two paths in Figure 52, rj-<24xd4><S4><f4><il><e^><Si2xf^xi2>«e3x83> 105 V <a,0/ i <1.1> ) <1.2> <3.1> <b,2>\ «c,2>.^; <t,i> <2.2> <4,1> «a,3)/; <d.2>% (<e,2>« X , <1.3> <3,2> 4>,3>\ (<C3>/) <f i2 > 4-2>: f <£ , 4> fj <d , 3>\ (<e , J)*) (<c,4>/} <f,3>V C<e,4> Figure 5.2 Holdings of Initial Conditions 10* Since #! ami r x hive the same endpoinu, their images should have the lame token loadings. Let's see. ^-^Ib2alb2d3 and Uj| r 2 » 2 -2dSf4e5f4eS and lfyj-2 It checks. For an initialized event graph covered by basic circuits, the next theorem establishes a special relationship between the paths of the event graph and the paths of a corresponding simulation. Theorem 5.2: If Z-<N,I> U an initialized event graph covered by basic circuits, and T is a simulation of Z, then VmcIKN): VrdI(T): >-> A *•-** A lMh-Wl * ErdlCT): >V A f V A f- M . If M is a path in N and 9 is a path in T, and if the endpoinu of m and 9 are the same and p. and 9 have the same token loadings, then there exists a path in T having the same endpoinu as 9 and whose image is *.' Proof: Let V-ce^n^ and **«<x 2 ,n 2 >. The required path f can be constructed by backtracking from <x 2 ,n 2 >. Property 25 guarantees that at each step there will be a way of extending the path in accordance with p. There's one exception though, and that's when a holding in the back boundary of T is reached. By Lemma 5.1, when a holding in the back boundary is reached, the token loading on the path already generated is n 2 . There are two cases to consider (1) oc^np in the back boundary of T and (2) <x^ x > not in the back boundary of T. In the first case, Wr-n 2 by Lemma 5.1, and, therefore, the path must be complete (otherwise, we would have Mi>n 2 and Im^Ii)- In the second case, Wi<n 2 by Lemma 5.1, and, thus, this case cannot arise. So we've now got a path f such that f '-<x 2 ^i 2 >»e > * and t"H- Because *jt-*}, *f must be an insUnce of Xj, and because |pli-Pli, lfli-1% From Lemma 5.1 and the three factt (1) >V, (2) fJrPli. Mi < s > '*"'*• ll fo,tow * thtt 'f " v D 107 To illustrate Theorem M, we consider the foHowinf path u in the event graph of Figure 5J and the following path r in the simulation of Figure W u - 2alb2»lb2dS 9 - <24>«Ux34><f JxilxeJJxS^xf 2><*2><**><S*> We have V-V-2, u'-f'-S, and lpfc-Wi-2. Therefore, there should be a path f in the simulation of Figure 5.2 having the sanie endpotets u r and such that f-n- Therels. We now look at the circumstances surrounding the ordering of two occurrences in an event- graph simulation The ftrst part ot off dilt miiwi l i appsMuh ) *» ■* Pmti net sim uh rtofi t, . ' Suppose that q isan uuurienor ti a im^ulauo^ Tt sui w e e rt iep > a ^ l lw ^the? oa»rro»c«« Into three categories: -&wm that tfjOjgi f fcHhoei tfs^fiiB^s^ 4 #hliiii^,ltipt *re \ A ' '.*■ ":'.: r '...'..',i^-~. '/■ is" occurrences . .,:-lH , e«Ojdifif«i U'- : ' ■'■■::#*■ .-tk . ..- .. V. ■vv?.v--: occurrence* \ / concurrent with q / ^ ■ ' : : ■■■■•.< 4£ , . . - / \ / \ w otcu i»fo«ee» fcjUpwinag ... ^ \ Suppose that the occurrences of Event t are totally ordered in the simulation with f r ^:.^^^^*^^^x^^/;^ \ \ \ i >¥■■ \ / \ / \ / / \ / octurFFintis of / V i \l / \ / x,.4>^tl>-J: / "V \ Now if Ms aw otarnmnx* Xwt * o so a o dmg v»H B J*»«* oyi«»».|^t^ integer * such tb*t V 'ITth«<#tJroWU»*«^^ occurrence eT I vem # i>reotf*ng q, b Wgtlw !%#»# 0» n^ Joft HMwpgor^*^ ' preceding <S3>. while <U>Uth«^oceurr«KerfEv«mlpm«Wiif<S3> ^^fm^^^ff to occurrences of Event * foBowing a. We know that In t simulation of an event graph covered by basic circuits, alt instances of the tame dement are totally ordered. W# woo* mm Mks to determine f or such a simulation under what condition* it Occurrence <*i«ni> the Vth occurrence of Event « t preceding Occurrence <« 2 ,n 2 >. To do that, we need the concept of 'synchronic defer*- Definition: For a path a connecting two events in the inWalHed event graph Z-cN4>, *zOs) - Wli - min{irii I WHN> A '»» A fiO 'l^n) U the token loading on '"* minus the minimal token loading on those paths having the same endpotnti as *7 t^a) is the sg|$agcje& of p (with raspoct to ZX (When Z to understood, we shall write the swxhromcdelty of pu Just IU>) .. 1 1, ':>■ t^v«*^/5£ "'-;■> 3&&: 109 We give the synchronic delays for several of the paths in the event graph of Figure SI 9 X - Ib2d3f4 W»i) ■ 0-0 - * 2 - 4e3c2al ««r 2 ) - 3-3 - * 3 - 2d3c2al 0V3) - 2-1 - 1 * 4 - 3f 4e3 KvJ - 1-0 - 1 * 5 - Sc2d3f 4e3 9(9$ - 2-0 - 2 In the special case where p is a circuit, the minimal token loading between the endpoinu of p is 0. We thus have the following property. Property 52: If Z is the initialized event graph <N,I>, then, VweO(N>. ty^-bk The synchronic delay of a circuit is equal to its token loading.' The following theorem says, in effect, that the synchronic delay of a path cannot be decreased by extending the path - the synchronic delay either remains the same or increases. Theorem 5.3: If m and j* 2 are paths connecting events in the initialized event graph Z, then, M1SM2 * *zO»i>£'z(M2) 'If mi i» a subpath of fi 2 , then the synchronic delay of m is less than or equal to the synchronic delay of 4*2' Proof: Let p 2 - ft^f. Let ¥\ be a path of minimal token loading from *Mi »>i # - Let '2 ** a path of minimal token loading from *pz to H We nave < «z0»i> - Ml " *& and, t^) - Ml " *lk ¥>S>:-~:»*S3?s^'<f8<>t8S<»Ji|^^ '.- ■**je<;*3: -*#*R s^q&^^r^P^i" ' jgi- Sshajv*** Thus, i^j) - n, ♦ tod ♦ Hr j »& t *> Because r s to a path of minimal token loading from *m s to uj*. ►ill * IVhk**- <*> Combining Una (1) and (2), we get, aft" We're now ready for the major result of tMS MCtfcm. -• ■ • . ■;;;■ -^ f '**■*"? ■,■•■■■ ;V«r-*i,-7-:- -*>^-<t •■.,- > ... ..., v . / , Theorem 5.4: If Z to an initialised event graph covered by baste circuits, ...... TtoarimmationofZ. f ^-«^ ■ • <t,/il» off jf^nj? a» r oo^irio»p|. te T v , _ ; ,^ ; ^^ ^ ^ , . then the following are equivalent (a) «|/ii> to the fc\h occurrence of «i p r todl o f ^n^" '(b) <«,*!> to *o toi ocoirrwce ofV, fbi6w^<» 1(n > *» ?^'- > <• There exists a path from «*•*!> to «»»»♦>♦ and the wncl i ron o n te delay of its imago to J*ti Proof: We prove that (a) ^(c). It follows, by symmetry, thaHB) «*«. L*2~*U>. (a)*(c) Since <fjji|> U thei^txainoattof^ iisowriiM iii|ny rii^th^must be the tost Let #i be a path from «\#i> to «»g, nj+k-b, and # s a path from «f|, n t <*> M> to <*j/ij>. (A path always eatoto between ordered qoomvojioss? v ■ A* Ul •<e,,n 1 > ► k occurrences ofei <«a n a> " Let r-#i*#> and tot |i be a path in N frwt «i te « s swefc chat ez(si)-0- The (wrifmion or tyntiiiuMiiiL atwy gifavav - ^■■-^■■^■.-■■-- From Lemma 50, we have (1) (2) We now show that Wfrtyt Since *zUK t^^i. Let HfyrWi. and tat « be an (Such a circuit exists because Z Is covered by basic circuit*.) Let ji'-e*V*' a)' is a path in N from «i to «j. fc'li - «*Wi - Ni Since *' and *j have Mm ...seme endpomti (#j and <j) and s»'IH*ili' Theorem 5.2 implies the existence of a path | in T f rom^^irt|%4> to <^n s > such that fat'. Because f-w*ji and «i*w, f will crass a occusWnces of *i after leaving <#|/i|4k-l>, and before reaching <»^n s >. But <#i/i|-«k-&.>is the bat o ct u t nance of #| preceding <«2^i>- Therefore, we must conclude that a-0 and, From Lines (I). (8). and (S), we have %(*H-1. W (0 * (a) Let p and m be as defined in the first part, and 1st */ • eA'V We get. * M a means that m is repeated a times. r- Theorem M impMei the existence of a fMth f in T from <fi.ii!> to <*j,nj> such that f - m' - e^'V Let f • flffl whw * f 1 • e^" 1 «*» *l " »• fi *» a path in T from «l^ l > to <i v «|4- »-!>, whik fj to a path in T from <*i. n x * krl> to <**n 2 >. To show that <# 1( *i+W> to the lyi occurrence of « t preceding <*»**>. kt ( be any path in T from <#!,«!+ W> to <^aj>. By Theorem H But since f| • fi and IjOt) • % 0) Suppose that ( contains an ossiiBpi^jaJt^-s^.^i^s^Ari^.^ffll^ be the part of ( preceding that occurrence. | t to a circuit in N fbogftnning and ending at «,). By Lemma 5J, fill >0. m other wordf^l eflllii^^^^ than a But this to inconsistent wtdi Line (0. We mutt conclude that no path in T between <* v «,♦ iW> and <* «*> «i«yni^-i»iiM4in»^4fil*ir <* t , n t + k-\>. Thus. <#!> n t + IH> to the tost occurrence of #| |n e tedtn| <# t a 1 >, and <*i*%> to the Jfth ocuii r e nte of #} preceding <*»*•>< ^ * D The equivalence of Statements (a) and (6) In Tfteerii'frWb* etoualtoedlis nr figure W r<*t.n«-^*.l>t k occurrences < of e a > "k Occurrences of e<| <«i ri, ♦ fc-i> J <e 2 ,n 2 >J- Figure 5.3 Ordered Occurrenced in an Event-Graph Simulation 113 In the simulation of Figure 5.2, we see that <24> is the second occurrence of Event 2 preceding Occurrence <13> and that <\fi> is the second occurrence of Event 1 following <24>- We have the following path v connecting <24> and <1,3>. 9 - <24><d4><34><c,2><2,2><a3><W> *-2dSc2al and <(»)-! The theorem checks out 5.3. Cones: Because synchronic delay is not a convenient concept to work with, we introduce the concepts of 'back cone' and 'front cone'. Definition: If Z is an initialized event graph, N is the event graph associated with Z, S is the set of states of N, e is an event in N, then, + z ~(e) - {seS | IpentN): >s A sep A *»*-« A «jt)-0} > z ~(e) is the set of states s such that there does not exist a path of delay zero beginning at the input event of s, passing through s, and terminating at e.' + z \e) - {seS | lj»en<N): * M -* A se M A $y A «(m)-0} > z "*<e) is the set of states s such that there does not exist a path of delay zero beginning at e, passing through s, and terminating at the output event of s.' 4 z '(e) is the back cone of e! and e^e) the front cone of e. (When Z is understood, we shall omit it as a subscript of +.) The two definitions are illustrated in Figure 5.4. In effect, what se«> z '(e) means is that the 114 Such a path has non-minimal token loading e . paths with minimal token loading 1 *"T--Such a path has non-minimal token loading <•) »€$"(•) (b) • €++(•) p&flftm 5.4 B*tfe* A0f»eA«toa4 *ri£fe M$W%p*^ : **&. Con *» ; *f'-. <T(2) ♦ "<:?); 4"" (4) abode f >n uj^aa •*■ jM* sjw* 5^y . yfw I- lirlli i Um> o- .1 ■0f b T-t'? » jji i^aa 10 a b c d e ^%.), ♦ T (2) 4 + (3) it|«! Nw* "$#-J WW ^5»# .4"'(£)&kA 1 w (fe-r Innsj •*-« **-* i~i' ?*0f^ * 1 (a) Back Conea %{&),. Front Cones Table 5.1 Characteristic Functions for Front and Back cones 115 'quickest' way from the input event of s to e is not through s. Similarly, what se+zte) means is that the 'quickest' way from « to the output event of s is not through s. In Tables 5.1(a) and 5.1(b) we give the characteristic functions for the front and back cones of the events in Figure 5.1. Note that in our example, 4z"(e) is the complement of ^z^e) for each event t. This is not generally the case. The significance of front and back cones is best understood in terms of simulations. (The first part of our discussion applies to all simulations, not just event-graph simulations). Suppose that q is an occurrence in a simulation. The occurrences in that simulation can be separated into two categories: (1) those that precede or are equal to q and (2) all others. With respect to q, these two sets form, respectively, the past and the 'not past'. Now between the two sets of occurrences there is a boundary, and this boundary is associated with a set of holdings. These holdings have the property of not preceding q but of being initiated by occurrences that do. This is illustrated in Figure 53. If we imagine the simulation to be three-dimensional, then the boundary resembles the surface of a cone. Similar remarks apply to the boundary between the future and the 'not future' with respect to q. In this case, the holdings making up the boundary have the property of not following q but of being terminated by occurrences that do. This is illustrated in Figure 5.6. In Figures 5.7 and 5.8 is a simulation of the event graph in Figure 5.1. We've indicated the T>ack cones' and 'front cones' for occurrences of Event S. Notice that the simulation is 'sliced up' by the 'cones' of each type. The reader has undoubtedly noticed that we've used the term 'cone' to describe both sets of states and sets of holdings. The correspondence between the two views is straightforward: If q is an occurrence of Event e, then the holdings in the tack cone' of q are holdings of states in ♦z'(e) 116 occur rences preceding q holdings not preceding q Figure 5.5 Boundary between Past and 'Not Past* / / / / / / / / / / / \ \ / \ \ \ \ \ \ 5^ \ \ holdings not fol lowing q \ v ,. occurrences fol lowing q Figure 5.6 Boundary between Future and 'Not Future 117 a • 1 •: b • c • 2 > / \ / a • " \ d e • \ 1 •: \ \ \ 2 >: \ \ V / /a \ \ \ d •, e • \ \ \ \ \ \ b^» \ \ 3>: \ C • S ' f V I / > e • f a •' \ d v \ \ s \ \ \ \ \ \ \ / v_ ' e • Figure 5.7 'Back Cones' for Occurrences of Event 3 118 a .• 1 •: c • 2 > / S N / \ \ \ /. a • / a * / \ e • j / / \ / 1 •: ' / 3/ • / / f ^. a „• ^ d % / \ e • y 2 >: / / / 1 • / / / / / x *-' 3 V / / b T • / c • \ / f • / N 2 ;•: / . 4 > / \ / \ d • / \ e • 3> f X e • Figure 5.8 'Front Cones' for Occurrences of Event 3 m and the holdings in the front cone* off ere homing* of «e*s incite* Thue, m see that in Figure 57 each holding in the "beck eone'of wi occorrenm ef Event B to * holding of » state In 4'(tht*fiJt). Similarly, weeir thst to Flguie 18 mew h eel in g In the front cone' of an occurrence of Event 3 to a holding of a Matt In ♦UMM^ Then Ideas aw eKpce»»«l to the f ettowing theorem. Theorem 5Jfe If Z is an InittoJtocd event graph covered by bask diwto, and <H,O.C> Is a simutotien of Z, then f or <vr»cH and <**>eO, <s J m>i<e,n> A (3f eO: f •*s l m>Aqi<a«>) • *«♦«<•) *** <eji>i<im< A (3qeO: <wn>«qA<W>$") *■ se%^|# <°> If <*m> doesn't precede (fotew) <«*> but is Wttotod (terminated) by an octurrenee that dees, mens must k*i*dmk1hm*mi*& '*' ^ Proof: We prove Jutt the f bit litJf.tNiem^ Let q - <*'*'>. Then q must nemmvtiy be the lur e*wrenee of <#* preceding <**>. because any later oocnmmm of «' would have to follow <s,m>. (<wn> must be terminated before amther hemmg of sulnmased.) By Tl. teliOl w/ m«^ eete» > path * from q to «*> such that *z<#>-0. Now, tf them existed a path a in the event graph swcJt*tat >*'A s«« A «*-# A KeM then by Theorem 12 mem itfm^vitebe'ipe^ event graph eiUsts, An m»ed7*(«). ° We new relate the concept of cones to the .Idem, to. the preceding section. Consider the following observation about me Umuktfort *i Flgum 5>. If q is an oemrrence of Event S, and If * to a path originating at an occurrence «*> and termtoattof at q. then «mi> to «he irth occurrence of # preceding q iff * creemYltf "beck cones'. For eeampk <U> to the fourth-to-tost occurrence of Event I preceding <M>. and each path between the two occurrences crosses e*actt> mmck cones*. A similar observation aoplto to d» Yrost oaatlA * Jtfo* ffe, $>«?* Ift oj|a*piP* * **««l * and if # to a pa* ortojMutoat; at o, m*mmH*#*>*m mmm* **#>>$** «m> *•$?$* ooamonca of # faUovteg q Iff o o*»« H fro* f^ ^^^ the Theorem && If Z to an initialled event graph covered if •** etooalto and » to a path in i fiien. The synchronic delay of * to equal to the nomoor of tome) *• bock (front) oont of m'i head (tai0 to creaifcif .. -f., *,. . v -j« Proof: Wei prove Port (a) brto4«e»Me»tole»jg**** . For loK we have ftpX) and W^'^*)-*- For the Induction Map, It to oaff ktont to than) thai onoa .a to { otto) tfe) if^iO V* Hs JM-Mrtti vtOinotnMg, we gee, v «P#zKm"K For thto qua, there cannot «tot a ft* eojftnntoM at *m umtal n lna, s, endinf at ■■' ■*-^' - <-• , iu* r, , jrf* -*■> „?$# k |;*9 Wjp Se ,«i£> inl^^. r . 'nasyj . n , ana wnoM aoiay n xero. Mcaaoijf: nat ma nm moi propartnv, imw do max KsfV^O. Thto toaoltoi ttat ffWktb. or oMtvotootlr. 121 MiHUrlfli*! : ~ ■ ■• ■ » ~ >:■■'■■ ■ : ■■ * w . ■■ ...■""¥■' ■■■.,:, ■ .. ; ; - , ■ ^-. ;- n ^;-./ : >'. > ^ i' ■ " B7 hypothesis, there wilts a bMfc dratt flontttolff •** ». This means there's a path from V to > with a token kwdittfof t«|^ Wopatl^p^li i»afptnd«l to tht tall of f, we get » path from > to r* with a tokan loading of 1-WfHTh- Since { is a path from > to p* and K$-0, From Lines (2) and (S) wo have Nr**Hfc-» and from Line (1), *eV<*> For this cast, inert «tfef»* pHh bogmnmg ft, ,*» » ? "»» ? *r » *#** * »** «"* whose delay is tero. Since |V|, {\*\ and KD-0, s| must be «sch a path. That fiwani- that ^ end f ha^ tfw «ne ea#em» onrl <io same dotty (seroX Thus, ^Hfkor.eouivtJentfy. wi««raV From Lint (IX we got, IfcHoW D As an illustration of Theorem &A, consider the pa%*f { lMMIeynNilie]Pnr«UvWo have, eW-2 ■ >-3 and p*-4 ♦VMw) and ♦VjtHb/UJ Combining Theorem M and Theorem 16. we get the foNgpJng corolkry. ' ^^^^^e^^^f^^P^^jf^!^^^! 1 !^. '''-'•- -•* 4 "" " '. V***:* ■ Coronary 54: If Z U an miUaUxed event graph covered by bask circuits, T is a simulation of Z, - < <» t , nf> asst o j o> * y. s * » oesetronsm in Tv ■ . ofcen th*£ofawiM stfe esin>ah*K* (a) <*i. nj> is the *•* occurrence of I, jiteoiaThf <** *,> (b) <tj, n x > is tht Jkth occurrence of #j fohowtag <* t , «|> (c)3rtII(T): V-^np A r *-<# 1 jj> A *e(#)-A-I *,..■.;■* ,v-., -. ».*■,■. /V* ^,,.> ."■;--■■. ^'-e ■:-:,■ - S-v- -..-..- $2 *£ M- - There U a path from <«|,»i> to <V4> and the synchronic delay of Us image U k-L' (d) 3rtII(T>. V-et} ji|> A e'xf^a|> A HtVfcj)- *"* There is a path from <tift\> to <****>, and its image cresses the back cone of « s a-l times/ H! -'- s * ^->* <e) 3*eHff* ^"t-«i^i> A # # ^oj|4iji A^^ff^ K" , ' TZAlZ 01**. > , .A. " ' There is* psnh from <» 1 ^ to j^* «M *o imajs ssostes the f |«nt cone of «, a-l The next two theorems provide us with some useful properties of cones. Theorem 5.7: If Z^4> u wi mitiakied event grip* awered by t>^ E is the set of events of H. men, V#eJ*-*rfi1Nfc-i|iifc^b^ Tor any event #, the token loading en a dree* is equal to the number of times «'s back (front) cone is crossed.* Proof : We'll prove Just the first equality ,■.*.» Since N is connected and covered by circuits, it ^sfrfagiy Os pn o Qd Let.jt be a path from '•» and ei* to «. Thus, J(*) - and p* -#. Consider me path sip* •z(«p) - kalrlpOi-hftr ffl In addition, we have by Theorem &6(aX : ! ^^sii#£'^ m But W^,)- ##*)««. Thw, Front Line* (I) and «> we get. Wi •*%•<«) • e Theorem 5* If Z-<NJ> ii »n littt i ilh i d twwt fayli w i c i i faf fcwto dfotto, N is ^onn nottd. and E U tht Mt of events of N, then, If two paths have IN same endpoints, then the difference In their token loadings is equal to the difference In the number of times they cross A bacMf root) cone.' Proof: We prwe the theorem for J««t the fint •oualtty. Since N it connected and covered by drcuto, It from pj* and Mi/ to >i hod >|. By Theorem 17, o»lll + l»ah - «»lle>-«eV*>»«e>-W) Combining, we get, Let n, be a path i ^1 j '■j/*t r J*i 5.4. Syfjern Space; mo tneory ot mwmi can introduce in this section a nouen of and time We •****» notion of 'system thne'. i^i^^^^^i^R)*W^fetJ%S*»^««iSS #* Suppose that « t and «| ara awn* in an t nw l st l wd aym fra f h wrgatf by bade drcuta. In S action 5,2, we Isamed that In each skanktitn of |he meat gteph the oi dating^ |njdjng front occurrence* of <| to occurrence! of f| aia at shewn to fl|iiwji|(|n n yljlh o, onf o r i n g*4o*dlnf from occurrences of ..a*- to occwTOMas of «| inu ihew* in Pleura 8J(bX Tha auatftan now is this: How do w« combine tha two fifttftt to fat Um < Of ^and*^ *^sf? r H %< :,<n*«'» te <a,.m t > «il I <e1.n1> 1 <o I .m I *2> <e v n,*2> a& <o,,m t »3> <Oi,»^ <e„m,*4> <» 1# n,*4> (a) Figure ft. t Ordering} (b) aynHirano* ohohno ai a d e termin e s *ho# far alfeed 4 emanates* fat tht ,ilBd^ intvMn:rii^>iifaBii In an eaen>]graph. It 125 Definition: For Events « t and « s in the ttrongty-oonimimi viwt gjrnph Z-cN}>) tf«l^ nrin{|Mii I inO(N) A ^jCm} **i"t *PA*\*$ 1* the minimal token loading on s h ow drcusts contatoiny both « t and « t .' /%(*i/2> " understood, we tanefly omH it as a subscript of *) In Table 52 we give the synchronic distances between the events in Figure 51 e. 12 3 4 12 3 10 12 2 10 1 ■ ■■ 1— * * in— ,m m 1 3 2 1 a 3 4 p(e 1 ,e 2 ) TebteS.fc Synchronic Ototanees The following theorem provides the connection b e twe e n synchronic distance and the ordering relationship b et w ee n two events. * This is equivalent to the notion of distance Used by Commoner ti3| (See pp. 112-06) K^^^jr.";- ■ ^#~^ Theorem 5A If 2 1* an Tisa then, The vi«m fl^ni ^WWWI OfHK ONNI MO lUONgiy flfZ, end <t|^i» ««miM in t\ *% <e a ,n a >»; • <«i.mi> <# 1 ,m,»p, («,,*,)> By Theorem M there exists a path «, from <*},»,> to «,*,> and a path from » x from <*!,n 2 > to ^j.np such that *#,).« and fl^-a Let Z - <N,I> and r • eye> Because #1 is a path from «, to «, of mlrift^ tefcaa lead** and I* it a path from «, to #, of minimal tokon loading, » mart have mtntojet Man leading with respect to thaw draita oomammf both a and * In oehar wd». ^ - ^, *,). atom* to a path from «,^>ft <»l*l>. we have,!* Lemma Utnttft,^.||fc. The deM resot foam*. D We see In Figure W that <U> Is the jfe occorrenca of Event I preceding <S4>, and <W> to the next occurrence of Event i fojewjnx <34>. The difference in occurrence numbers of the two occurrences of Event 1 Is 2. This Is the synchronic distance Eventslandl With Theorem 5.9, if we have an initialized event graph satisfying the necessary retirements, than we can determine the ordering relationship between occurrences of two events. AH we need know is the synchronic distance between the two events, hi Figure 5J0, we show the orderliigrelaticwhipsfvstvaralTaliwof/^^!). 127 ii 4) V 4) V U n 4> 4) -•- 4) o ^ ii o *•* ii u V it n +> c a) o n <u o a a) n M 3 O O c <D I 0) ,0 00 ■H .C (0 c o •H ■P at ■-I o> c •H H 0> •O O O H in a) •H *', ij^ffi^fig^Rj*; Th« next theorem iMM that p is a men* when Km event graph satisfied two elementary properties. Theorem U0-. If Z is an takialiied event graph that U 0>*rongh; oamajaad and (2) frac of blank droi**,th«n^toam**antfnt*af«*w«i i ee rtfl cj n>, far events^, eg, and »> <b) ^rf«i^i) - 4rfVl> (c) /■fcW-'s) £ ^i<M^ Proof: First of all, strong comwetivitr guarantees that ^ is watt defined. Property (a) follows from the fact that Z U ftet ef us** tiiuji Fiofpiltai (h) awj fr) fatliiw duortty from the atftttnoR w wfmJiTomc i Strong connectivity and absence of Wank droits, together wife wvembittty by besfc drcuits. might be regarded as criteria for 'wtM f orimdn eti' in eve* graphs. Earthwork W hat shown that absence of bhuik circuits and coverabMity by basse cheat* are necessary and suf fsdant conditions for liveness' and 'safeness' in event graphs.* We now relate the ideas of this section to the theory in Chapter 1 Theorems 3.3 and 3.8 and -■■ <: ' ip Property SA state that the Wttattaed control structure k a strongly connected event graph covered by basic circuits. Thus; Theorem SJ asuftev Fttrtfuemert, we have the foMowsnf coronary to Theorem 5J0. Corollary Wfc If the initialized control structure Z* is free of blank drcuits, then <£*,^*> is a t Liveness means that simuhvoons of the event graph can be extended arbitrarily far. Safety means that instances of the same element are totally ordered. 129 Definition: If Z* ii free of blank circuits, then <&*,/>z*> is called the system space. 5.5. System Time; In most theories of system behavior, 'time' is Introduced as a primitive concept Our approach is novel in that the concept of time is derived from the logical structure of a system. We only require that the initialized control structure satisfy three simple properties. There is no need to augment the definition of a system, and there is no need to modify the simulation rule. Definition: An initialized event graph <N J> is said to be synchronous iff it (1) U connected, (2) it covered by basic circuits, and (S) satisfies the synchrony property: 3kdN: VitffftN): IwHImIt The length of each elementary circuit is proportional to its token loading.' An initialized event graph that is not synchronous is called nonsvnchronous. A synchronous system is one in which the initialized control structure is synchronous. A system that is not synchronous is called nonsvnchronous. ' For example! of synchronous systems, the reader may refer back to Figures 3.13-3.15. In Figure 3.13(d), the proportionality constant between the length of an elementary circuit and its token loading is 2* In Figure 3.H<d), it is also 2. In Figure 3.15(d), it is 4. An example of a nonsynchronous event graph is shown in Figure 511. t The question of what an 'asynchronous' system is is outside the scope of this discussion. * In determining the length of a circuit or a path in an event graph, we count the arcs in the abbreviated representation of the event graph. This reduces the length by a factor of two. Figure 5. U A Nww ynchrwwm Event Qtaph We consider now ion* bask property of sy iK hi eao oo ovo« graphs. Beceim a synchronous - • - .** <■« ^ . - •- - • -■'■• •vent graph is connected and obw^*t»*^ <*^«^^ ***•*• f * iDI,rt, « Property 5>. A synchronous evem graph to itimigh; < rrom ine sywouimy prwpwty, w« gw wwtowinnHSj. ^ Property 5.4: A synchronous event graph to f roe of blank drcuJt*. Alto from the synchrony property, we know that the length of etch elementary circuit to a multiple of k, and that the length of each boric circuit to equal to k. itfettewt that k to equal to the god of the lengths of the elementary drains. Now, bectuft any circuit, elementary or otherwise, can be viewed as the superpotitkon of elementary drcuto, the ryndwony property applies to §£ circuits. These results are reflected in die next property. < ' •" " < . "*™. 11 ■.* - - , , m P iuu er u Ut ff xNJkii ft svndiraMutavait^afrfi. dMn. VimCKN): M-r(NH«ii To help tu In understanding ttw notion of time prssontod below, we introduce the concept of the 'phase relation'. The phut relation to generated from an event graph in exactly the tame way that the akernattvenen relation to generated from a part The tame 'cottapiing' procedure to used. Definition: The phase leJatten for the event graph N-<SXJ> to the minimal relation /J.S^SUE) 2 such that VxeXSUE): x/J N x Elements x t and Xj are said to he inohate iff X|£ N Xg. The concepts and results on tbhih o d toi Stetson 19 for the ikentttiienejs relation carry over the the phase relation; Property SA If N tottaeventfflts*<SJ^th^ VAeXSUEVi%: AfiSVAfiE 'Each eooivatonct class induced by /J N contains either exclusively states or exclusively events.' -1. r\/- Definition: If N to an event graph, then those «ouivatonct daiecs Jnduced by 4„ consisting of states are catted Rhjsji and those assisting of ivshts'ara called phase transition*. Definition: if Nit the U the quottant Mt ft-41£>. Property 5.7: ft tot net #£* ■fkititK', .3 l *^i J t */ "■/*'?; ■?**&*"! Property SJc ft *• »* elementary draUt ef length $#f)t* In Figure 5J& ve »how bow the fwefeeioaftri tira*£er p ^«^^ to ■W ..^ CUv- I" "I fa, <*,♦>, &$^Jfe?»l€:: *bj»re.J. Q«»f*ti w n V*3&" £;'*■ '■-'? '■> The fundamental dreuit may be thought of at a fcetk'. New with this interpretation. It might appear that to make an event graph '•yiwfcronew', it WW be neeenary to YhV the event* *" ••>< t This pro p e rty corresponds to Theorem 12 ■*•*•■*■ *.%v **. » «yw,V** , «JVw ( "--fi , *. - ■ 188 a phase transition 'in unison'. However, this is not the case In fact, ii.wof^t even>be necessary for the initial conditions to be in phase. AH that's required is that the ku^l comiitioiu belong to a 'marking; class' in which it is possible for Just those states in a given phase to hold. As it turns out, there U exactly one such marking dais* It Jm§ been sheW-that in * «t*prtfy connected event graph free of blank circuits, two 'markings' belong to the saim mar Uogetatt iff they induce the same token loading on each circuit Now in the *MtJW Trtwil J^ theer pritni in a given phase hold, the token loading on each circuit is known: M ' VsjeJMN): Mi- — T(N) But this is Just Property 5A which is equivalent to the synchrony property. Therefore, a set of initial conditions can he brought 'into phase' iff 'mespiibJia^fMBasYt^ii'atisfied. With the preceding discussion m backgw*ihct Wre no* road y<to flwahy <r» major results 1101 limine tn srnftirnnfluiavont gmnht Theorem 9JI: If <N J> is a sync h rono u s event graph, then, If sti and st s are paths in N having the same endpetnts, then the length of «} minus <y(NMtoken loading on «}) equals the length of jig minus <*<NMtoken loading on nj).' Proof: Because a synchronous event graph i^strangjy mmm& t here eautt a patbug from nf and nj* to *«i "** Vs* From Property &ft we have, y»lNu 3 l - T<NHb»ili^i3il) • Theorem 11 in [4] ^^?^p|^^r*^^^i^; #4 Oxnbfciirif , we get, Theorem Mfc If «ff,*Vis t ryncl i r o w e oi event tuaph, torn, If U^ f0**»* 1*^11*01 J ••'■: .M-^ '■■-.. ftofc'* Proof: Beauue p^ forms & circuit, wt have bv Property &&, Tim theorem f onows. Thoorom U* If T«*H.QjG» tea iimuliHaii of ai In * limubiion of a l ynehfoooui CTo mrm ya y 4f,-t— f law hawa l o w m a w a miuntni i, then they must bo the seme length. Proof: From thoorom Si, we know that PtlrHtife- 8bjNt #} and fr| are both paths In the l ynd i i o w oni owni t i aa l i iin a iaiiH % ^hWp|»M^«y *•&"*% J* ft fotows that Before we can define the 'time intervar b e tw ee n two bettings or two occurrences hi a 'synchronous i tm a l e ttorf , we meet f iret have a notten of 1e9w4n**uref whawi^the first i of two stales or two events are. ■***' 135 Definition: If Z is the synchronous event graph <NJ>, then, for Events t and * z > dzfcj^-n iff 3»»dI(N): M-«l ^ M # -«2 A n-||thr(N)lMli •d^i^j) . n iff there exists a path p from « x to « 2 such that n - lnhKN)!^.' for States *| and j 2 , ■'*■' «zOl- 'i> - *d<V «2> wh « re «l i$ the uni< \ m 0Ut P ut event rf *i *"" '* is the unique output event of i 2 . :-* ■ (Theorem 5J1 guarantees that fy il weH defined.) dzfa*t> te,u u * ' how far ahead ' lhe fir,t in$tance * *i te S oln & to ■* with m P* ct to the f ,r * 1 instance of x v In Table 5*. we give the values of a^/j) and afr^) for the synchronous event graph of Figure 5J. 1 2 3 4 1 1 2 3 2 -1 1 2 3 -2 -1 1 4 -3 -2 -1 (a) 3(e ;L ,e 2 ) a b c d e f a 1 1 2 2 3 b -1 1 1 2 c -1 1 1 2 d -2 -1 -1 1 e -2 -1 -1 1 f -3 -2 -2 -1 -1 (b) d(s r s 2 ) Table U Using dz, we now define the 'time interval* between two holdings or two occurrences in a synchronous simulation. & m Definition: If <x l( nj> and ow am either two %t lj \* p m tmvmnmm m a timulation of tht synchronous event graph ZxN,I>, then, A z (<x 1 ,n 1 >,<* > ni>) - (iir^>tW**^i%Jfc> Aj^i4i) **• aansiSil*»« ft *tr W« five some samplt time inttnrali f or tht Unwhtton in Fifiiw It In this case, y<N)-& A(<U>.<1W • t*2«* - 1 A(t2>,<14>) • tet-3 ** A(b^>,<f4>) - (-0K2 ♦« «0 AC<a>,«^) - ta2*2 -2 The next three theorems show that Ag satiaflei these prop o rtl ei that one wont* i meinc TOT QRM> Theorem !U4t If y 1>flt »nd ^art dther thrwhofcUatsmth rwo c otntn^ synenraneut erem §Mpo *« OMn* <W ^l**> - -A^ftf 1> fe> Atffi*i> - *2<fi**> ♦ Aztofi) Proof: (a) Follows directly from tht definitions of L z and djg. <W e^*,) - -dzdt^x,) by Theorem SJ2. ft foNews that ^ tf j) - *&z!tf i**)- (c) Let e/|*<x 1 .n 1 >, ?j-<x*«i>, ?s-<*i.*3>. and 1st I • *l, I». We hare, and *<«,*,) + Affeft) - (ii^hKN) ♦ ««|^ ♦<«r"l>r< N > ♦ *«»*») For occurrences (and similarly for holdings), 137 tfx^j) ♦ d(xj^3) - n <*- a^jClKN): Vl"«l A Ml'-** A *M2"*2 A Mj'"*3 An-| Ml | + lM 2 |-7(NXlMill+lM2ll) ~ 3 M «n(N>. V-X! A M # -x 3 A n - Ijil - tKN)^ «•* d(xi^3)-n Thus, a(xj, x 2 ) + ^ X3) - a(xj, X3). It follow* that, A(f 1. fl) ♦ A(f» fa) " ^lMNJ + ^.Xg) - Atft.ft) ° Theorem 5.1& If T-<H.O,C> is a simulation of the synchronous event graph Z, then, V^n(T): V^'cH * AzfeV)-kb ^ .If r isa path in T connecting two occurrences (holdings), then the time interval between V and r* is equal to the number of holdings (occurrences) crossed by #.' Proof: (a) Let V - <f }ji|>, 9' - <ty4>, and Z - <N, I>. Thus, A^V,**) - (n % -n{i 7(N) + dzfa'l) Since 9 is a path from < x to < 2 , the definition of d gives us, We know that |e% - ft and, therefore, *(>*•> - (nj-n^ y(N) + klg - fQWh From Lemma 5J, we have n 2 -ni - Ify The desired result follows immediately. (b) Let V - <*ii»i> and »* - <J2.ni>- Let ji be generated from 9 according to the following diagram, m ** < > 9 I ! Which, in turn, products, A( V, O - 04-mhKN) ♦ If fc - vCNfefe '-Became ot the vaoiiB wfakh m ^ •,*»1'f w« 1^ fi«o*ibanw» J4 n,-*! - |»|,. Tht **» Theorem 5J6: If <H, O, C> U a HtmilatioQ of tin iroc oronom event traph Z, then, Vfi.fjcO: VA^cti: (b) If Occurrences ft and f, IntttaUt (ttrminm) Hokjtnfi % Mid Aj respectively, then tht time Interval between fi and f, to t l.i iMi l f i s pf» ta iM^ ) | i ii|t iniiii f « i l t And V Proof: Welt prove just Part (a). Lot f ! - <«i.n t >, ft . «j,n,>. A} - cf^* and A, - <i»*jk. And lit Z *!sN|Ik Wo know that «|**| and § g *M t Now tat « be a path in N from th« oniojue output event of *i to «* Let 43 bt the unieut output event of if WefOt, 139 A<?M2> - (nj-nj) T(N)+ki«iMl-7(N)|*iMli ^(Aj.Aj) - (mj-w^ ^(N) + bu 2 « 3 | - ^(NJljWjl! We have immediately, ki'iMl - ImI + > - Iftf^l- From Lemma 5J, we get, mj - nj + (j^ and m 2 - n 2 + |* 2 li- Thus, A(*l..*l) - (nj-H^-ni-I^MN) + ki'iHl - YM^ - (»2 _B l) T<N) + ki'iMl - Y(N)|J 1 Mli • e, • s, J" < • s 3 • e. The notion of 'simultaneity' is defined in a straightforward way. Definition: If q j and f 2 * re either two occurrences or two holdings in a simulation of the synchronous event graph Z, then, f z is called the simultaneity relation. We say that Instances q | and q t are simultaneous Property 5.9: If T is a simulation of the synchronous event graph Z, then rg defines an equivalence relation on the holdings and occurrences of T. Furthermore, each equivalence class induced by r% contains either exclusively holdings or exclusively occurrences. Definition: In a simulation of the synchronous event graph Z, the equivalence classes induced by T£ are called simultaneity classes. A simultaneity class of occurrences is called an instant of time, or just a time. A simultaneity class of holdings is called an ( elementary) interval of time. We have the following property from Theorem 5J5. ^^«^¥^gffi^i*e^^ ■*** HO Property BJ& If two Instances in a coincident or concurrent art then they are either We have the fottowtnf property from THaaoim M* Property 501: If fl , e^ *» and f 4 are mnwm tea itvotUMnofttkt »fnctir«NM* event graph Z. then, flf J A *I*f 4 A fl'Zft * ft*Z?4 •if 3 A fTf* A *J*Zf4 * fl'Zfl If two instances are to (b) (predecessors) are Propertiet 5J0 and &JI mean that in a VyndtroMoi isfflMhtJon', the stoMritaneity classes form a •tries of 'slices', with Instants of time and Intervals o f irn s sW s J i l^t ua g *t*tt is INustrated in Figure 5.H The rtmulation dopfcttd to generated f rom nWl n^iauoj waul grant in Figure Si. Theorem 5J7: If ^ and e s are instances in a timileuon of the lynehroneoaoreBtgraph Z, then, fl*Zfc • MA *If ft and ft art l i mulm i i s o i ii, < *m f t and f^ meets** phase.' Proof: We give the proof for occurrence!, the proof for holdings being *«m*kr. Let Z - <N, I>, and tet ft - <xj. *,> and f, - <x 1( n x >. We have, 1\ T &1 ~ Az(fi.f|)-0 .'-•• far*th&® *«o>|. »i>-o - 3*tn(N): >-#! A .Ve, A |jt| - T^- ^m^N) «•► ^wn(N): >-#! A **-«, AW- (H^+fcfcMN) Thus, eirzf 2 implies that there exists a path b s tw es n x, and *, whose length U a multiple of t(N). It fellows that » l and x, must be in phase. D «>■» »•*„ a~- «-_* * '*it)tiitmofxiii»& - m In Section ft*, we introduced tht neiioa ef «#^> beJiif tht k^ oawrrtnce of «| preceding (following) <#,/*,>. For a spchreMm rtuatortM, time to a iww p ta f e rrouh rata** k and the time interval between ^j^> and <v»i» 1* ***"* ff" "* ** MM V * VUatMM>t te ■ directed graph. Definition: If v» and v. are verttoai in the Ui oi fcjj u a nmrt a J dtrfgtod graph O. then, d^vj.vj) - mln{W«n<0) | >*iV*ri d^^i.ti) li Dii (|ii|ili limiiii) UmiHH fiaw *i * V Theorem 5J& If ^p and « > n,> are occttmnra* hi a rtmtttarton of die lynchronoui event graph Z~eN,I>, then, <«|jn 1 > to the kta eccunwx ef #| preceding <VV and <#ya«> to the k 01 oscenenei of #| renewing •*|J*|> ■*' i V Proof: From Theorem 5.4 we know that there exit* % path # in the *mukUon from <«iJ»i> to <*&,> such that 1^*4 lit be a ndnhnal tongth path m N from #, to #* That to, \*Wft*l*& fc^uio*tro»Tlntoni*W trom i|Oi|> i nererore, •zW-WrWl-M 0) Theorem 5J1 atop gives us, bhr<N)Wi - W-i*n>Wi (2) Combining Lines (1) and (2), we have, M-<Mh<N)4ta|. . But PHtIh »"d ^hd^Vl*' **** ^ klg-Oi-WN^d^i^i) 143 From Theorem 5.15(a) we have klg - A z (« 1 ^ 1 ><« 2 ^2 > )- The derired reM,lt fo,tow, • D In the simulation of Figure 5.2, we see that <U> U the third occurrence of Event 1 preceding <4,3>. We have k«3, y(N)«2, and dj^MJ-S. Thus, A(<U>,<43>)-(S-l)x2+3 - 7 This checks with the value of A(<U>.<4,3>) computed earlier in this section. The final results of this section have to do with four functions defined earlier in this chapter. For general event graphs, these functions depend upon the set of initial conditions, but for synchronous event graphs, they are independent of the initial conditions. Property 5J2: For a path m in the synchronous event graph Z-<NJ>, Property 5i3: If * is an event in the synchronous event graph Z-<S,E JJ>, then, * z -<#) - {seS | l^«n(N>. >s A sep A M '-# A ^MnO-M*)} +£{<) - {scS | IjidKN): 'n-4 A S€|» A i- M * A IssHInO'M*)} Property 5J4: If ti and « 2 are events in the synchronous event graph Z-<N4>, then, tgffiltj - (d^^^-KlM^lW ' V(N) Before concluding this section, we should perhaps ay a word about the distinction between 'system time' and 'observer time'. System time is strictly a system-relative concept, and is observer independent Observer time, on the other hand, is relative to a particular observer. In the case of a clocked system, the two notions of time are, for practical purposes, the same However, in the MR-' case of an tmctocke* system, the twnotim ef (kne nif eew Mttk r ste robhmce to one another. For example, It might be possible for Insianet f j to mim^ Instance ft In system time, and for * t to follow ft In observer time, or vke nena* The enlr Ibing we can sty with certainty Is that if there is a causal connection leading from ft to ft, then ft mm precede ft in both system time and observer time. 145 CHAPTER 6 PREDICTION AND POSTDICTION 6.1. Information and Control: In Chapters 4 and 5, we examined separately the two components of system behavior: information and control In this chapter, results from the two areas are brought together to produce a technique for predicting and postdating system behavior. As we showed in Chapter S, for each system simulation there is a corresponding control simulation, and the two are isomorphic Consider a pair of corresponding simulations. Because the control structure is an event graph, the control simulation has the regular properties described in Chapter 5. Since the system simulation is isomorphic to the control simulation, it too has these regular properties. Of course, the system simulation also has certain , irregular , properties, but these are describable using the concepts of information flow. It is the irregular properties of system simulations that are the focus of this chapter. However, in getting our results, we will take advantage of both the properties of information flow and the regular properties of event graph simulations. 6.2. Transactions: Suppose that we have a system simulation and a corresponding control simulation. Within the control simulation, there is a total ordering among occurrences of the same meeting (Corollary S.4). For each such total ordering, there is a corresponding total ordering in the system simulation MS among occurrence of thoie events belonging » uWretosd meeting. These ideas are inustrated in Figures 6.1-6.4. In Figures 61 and M, '***# retreat the lrt n sw»J system mt and the inltiattied control structure for the Mtfrtptkne example of Season 17. In Figures 63 and 6.4 we give a system simulation and the cw tesp en dt ng centre! rtnwterton . We've Indicated In the control simulation the occurrences of Meeting {**}, and weNre wdtawd tt She jpWi sniw l atfcm the occurrences of Events 5 and 6 N«n the otte tt o M I^Ws p nii i ■ :. l* woo » «i*,twO sets of occurrences. TiHt'Wiwe Mia appose 6i Wlenhg^§S^!pn(rJson*^^F ; We adopt this tef iiunotegy: Definition: If. within a system stmtfeHen, the nth occ urrence eesedated with Meeting m exists - •'-" in i mi ii T i in i imifiiii ir»iii I '" um i HUi ii " H ^ If or that ilnunaHenV ^a *m Meve% enreeeweeo*n»e*j»_ For die svstem simulati on fat Event & n the Qrjt transection at Mw Mw tfBff - Event 6 Is the second te an s acrt e n at Mertn i ft*l Event 5 is the third transactional ■MoasMnFwWt ■* Now suppose that q is either a helling or an occurrenre m a system sfamiletion. Then can speak of the n'th transection at Meeting m 'rekttve tee*. flffif ,.>£. /• ; . c. ,v \ ' «'i? ;-:. ;,ft..-4 "I- Definition: If T Is a system rtmulatton, q is an Instance In T, i is an event, I mUa meeting. ^ it Is a noniero integer, then, iff 147 « 5 S to o X2 o n c 8 N •H « •H 4J •H N t *0 4J a § +> n >i CO •0 N •H rH A •H +» •H c H V0 Vi •H Cm 148 a .* 2 •. 7^. 1 •, g • Figure 6.3 A System Simulation 149 Figure 6.4 corresponding control Siattilation no For n<o, the nth occurrence mode** with Mootinrm precedm* o exists and it an occurrence of Evint «. \ For nxj, the nth occurrence associate! with Meeting ro foBwUny « exists and to an ^ o mni u m* of Event*. ! '; Tl , : In the simulation of Figure 6J, If we kt f be the first (and only) occurrence of Event 4 as indicated, then the transactions relative to f are as firm to TeWe*J. Note that for n£-S and for n£S, there are no nth transections relative to f Note else that because an occurrence is considered both to precede itself and to follow use* <see definition in Section fc& Event 4 is both the last transaction and the next transaction at Meeting {M} refcttvt to q. Although thit may not correspond to ordinary usage, it dots make the mafliotjnhi tuiailH. Meetings m {M} {W} {73J Second-to-hut Transactions <o-3) 1 1 '■*, r s none none Last Transactions (n-1) 2 4 5 none Next Transactions (n«l) > ; •4 '. . v 6 S Second Transections (n«2) none ... S 5 1 TaMe&l Tra nsactio n! Retfctjee so q Having introduced the notion of an event being the n't* transaction at some meeting relative to some instance, we can now define the *£of nth titnsactiem relative to en instance. Definition: If T Is a system simulation, q Is an Instance In T, nit a then, t.(f.T) - {««£ | Within T. * Is the nth transection at U^ relative to f] *>■*'"*. . - ■***=*» - « "Vt" "" ■ m If we let T be Hit sfenotatton t« Figaro 6 J and f bt a* dtflned above, then we have the following values for t^f/T). Lg(f.T) - PJJ eY for o&* and for *£& The values of tJf.T) an the things about which we're 'going to do our predicting and PfjffTgWjTltlet* «itf.T) D<9> MHIIBIBH WiiHlW«m» The problem* of predicting and postcllcting system behavior are greatly *n*4tf led If the system simulations under co nsi deration are 'extendible'. ,; ? <iti Definition: A system tkmOukm T is said to be forwards leewards) ntmdlbw iff for each tance f in T and each positive integer k tiNreexb* a teowid syewm stawtetton T (a)?'-* (b) for l£n£k (-kSB£-l) and VmeE*: !.(• '.TOnm * O T" hat an nth transaction relative to f' for every meeting.' (c) t„(e.T) c t.(e'.T'> The set of nth transaction! in T relative to 9 is contained within the set of nth transections « T' relative to .«'.'. m Ex t ondlb ttl ty wiss n oad sto the sa si n ai oT'doidloekVla m a Hill lH ii i ap e mi net We am Hate a necessary condition and seine toff kssnt oandttiam for extepdibiltty. f torn writer work (4l we know that in an event graph, no s v sn t con tami d in a Math circuit can ever occur. Therefore; if any ivstem skmrtatlen to to be eatendeW* either forward! ^backwards, the initialized control structure mutt be fret of Mank cfeeeJts. SssepOtt thet«his U the case. Then the only way for the system net to tang no' in the forwarts ^ifcet J il i ) diwctton as for there to be a pattern of holdings on the input (outpo»Hna»ef H ie s a m Mii g each that no event in the meeting is forwards (backwards) enabled by those hohtop. A> an example of a backwards liang up', consider the simulation in Figure IJ.kln systeai stautatten for the half adder of Figure 115 with States A and f as initial conditions, Becaim die holdings of A and f do iiot backwards enable any event in Meeting {SAW, the rtmetetion Is not backwards extendible. The following are sufficient conditions for an* system ilnwott l en i to bo forwards oEtondjbi (a) Z* hai no blank drcuitt. (b) VmeE*: If a set A consists of exactly one state from each each input Hnk of m, tlMt affRt 4t*A The following are sufficient conditions for aH systsnf stei«**8n* v»be be«kwaids«xtcndible. (a) Z* has no blank circuits. (c) Vme£*: If a set A consists of exactly one state from each output link of m, then 3tem:f*«A *■ '*■'■■'' Except for the situation noted above, the tnttiaHmd systsms in Sections 17 aH satisfy these conditions. i 1 i i 11 • • 13 k . b Figure 6.5 A Seaalattea that U Not Backwards Extend** Metre proceeding, a word about the phine we n o n a* ' dsadkx * ' is m eider. In the past, deadlock in a Petri net has been used to raprwrt thei nwtosn e nding notion Jn an actual system. This approach to net sotted to die theory pimni e d hew. If w toterpret occurrences of events as r e pr es entin g the ps s w gt of time u described mrM*tm U>lfaM 9 lll& M.p%qpfQi.1lt *w M eamspend to tome standl% stiff. Since thti k,«oi.in^lnnn^^|n||HM^ i» a reasonable aewmptton. Butttweuwtton artoe* M to hew the ph ea oimnw of deadlock is to be represented. Sines deadlock Is a VnedV of behavior, there adit pr eh a|rtt3 ho# made (a* defined formally) e^^^u I ejfejtt^ej^B^RdBTanunc anp ^kk&t ■ ae^nejptweejpv^v 'e^une^^emonee'e* 8.4. Prediction Qraohs and PostdicUon Graphs: Our efforts in this chapter are concerned with the fottowing problem. We know that f tt en imtaiim m seiaeeyea^^^^ with the alternative dass c. If we aho knew which chwosnt in e f was an instance of . what would this additional knowtedge tell us about the possible pattern* of transactions prior to e and subsequent to q ? m That additional knowledge allows us to kientif y an aUnpH tram among to alternatives. But this is exactly the aunt thing that our notion of Wtm mMmmt dees. So the Inf ormetion content' of the additional knowledge to ffUvaUnt to the iaf ap mi o n conta* of IN ttonwit htonttfwd. Anything that can be deduced from one can be sii a wd from the other. Our approach to the problem ts to th«rmctertat al the ways in which the information associated with f couM have gotten than (paihhrtiaaj and at tho ways in whkh it could have emanated from there (prediction). mformstton conbjnt canshto of a set of excluded modes. Because information is 'additive', we can treat each mode In the Information content of q separately and then merge the mult. AmMtoMd wtth mfr ii i o amaj a , theraan two suomtu of the simulation containing f Om setjuet tram* Hn mmihii mm mepeavand dm other treses IMnto the future. Then two mama duwmmi aw i mi hammas of thoiraaaaetten* prior to f and fUDseo^iem w g. ■ m 'gonerus/ wwro^nr awwr*ena| wmh ^pp*ie*wewpin* ^jp^m^p^w .^ew^w* w« i " ■• In fact, some or the partial mamrmt'may'heouemnlliifam^ oase.jO^oipnejp »w j an mrtntte nutnoeror ojtsuncf parmn-nmrnfmspeemna moewmw«wjwa!wwaw«s*vw;»e^pijjpfl*»"» there is a f tithe way of cheradorimftg ** a* of hectare** *nd fermard* parted binaries, The cones described in Section U can be umd to 'sm* up' tha sabaam llayaowsraSr ibepartiatlUsjories. This produces a finite sat of litotory •egmentt' as shown in Figure**. This approach is especially advantageous since the n*th transaction* relative to f are de t wmln s d by the occurrences in dm nth history segment relative to f (aw Corollary &ft "Postdkoen traph» T and 'prodktion graphs' reflect the different ways hi which history sagmahu may be < " : In ordeF tfr caneafe^ are roojuirou. 155 'History Segment < A 'Back Cone ' An Exclusion A Front Cone Figure 6.6 Subnets Associated with Excluded Mode m Definition: In a directed graph, a chain U a sequence of am tuch that each arc in the sequence has one endpolnt In common with Its prede c ess or and its other endpotnt hi common with its successor. (The difference b o t we w a path and a chain to that a path most traverse an arc only in the forwards direction, wbtti a chain may traverse an arc in either direction.) The sot of chains of the d a «M graph C is denoted C(C). Definition: If c U a chain in a directed graph and xyt U a «it*eeuence of c, then thU subtequence counts m a forwards (backwards) crossing, of v (y to x) and an ait loading from y te x (H» yi counts as a forwards <to&95& marine of 7 * **• * ■» *■* taadta f f rain * to * Dtf initton: If c to a chain in the directed graph Q and A*a sit of vertices in O. then Hd A is the number of forwards crossing* in e of an elsment A mmus the number of backwards CTowin|i Wc of an dwasnfm A. Definition: For weE* and Mcffl. »-(mX) - {tcE | ipoC(rf): *c - f A c'eja A X.nXsj- p A Mupgriiu) 20} (a) Tor each event * in 9'(nMl there eajsts a chain e from t to an event in n such that c does not intersect the mode M and tht mnnbtr of forwards crossing of states in Ud>2*W by e to gretitr than or equal to dn) nonsW of backwards crossings.' rVM) - {«c£ | 3c«C(N): *ew A c'-f A V*^ A Id up^w)* 0} (b) Tor each event t in 9*{m#tk there exists a chain t form an event in n to t such that c does not intersect the mode M and the numbef of forwards croastngs of states in UeV^st) by c is greater than or equal «»«he nanoW of back wards crosetngs.' v'(m,M) is the set of events that can be contained in a backwards history segment for Meeting m and Mode M. v'tm.M) is the set of events that can be contained in a forwards history segment for Meeting m and Mode M. ' d>z*~(*> to the set of links in the back cone of Meeting ta. 1%»"(m) to the set of states belonging to those links. »7 The requirements given in tht following &nmm*to1mM*mWGI^** l &bl&* the system net that correspond to the history i Definition: For a subnet R of the system net, a meeting m, and a mode M, we define the foHowing requirementi, j. ' (la) + cEp.fi »-(»OI) (lb) d> c E R c *"W*) (2) VoeE*: bnEpJSl r contatot no more than; one event ffoat^eacjiHnneilujg.^ (S) S R - (Tp^WMtj)' •A state it contained in R if f it to ad Jeemt to an event in t and to not OBntained tot the mode M.' WFR-FntSRxEmUEjxSg) *Sbo am of It cenjtot of thqwarato iH^con^e^eineiitoinR.* •Within R. each itattin (S^-Ua^*)) hat ew^ om injnit event and one output event' <8b) Vs^-Ud^^dn)): Ci)i-(i*)i •wnhto R, eaitmaai in (Sjt-U+glmfthas eaaO^one input event and one output event' the functtom contained m the next deruttnen oerrelpend «• tae front and back boundaries of a history segment. 158 Definition: For QcjE, mcE*. and Mcffl. b-(Q,m,M) - 'Q n (U^ z *-(m» fl (S-%) r(am,M) - Q # n (t%*"(nt)) H <S-S M ) b^aw,M) - *Q n (l%*-tm)) n (S-S M > f ^Om,M) - Q* n (U* z *-»(m)) n (S-S M ) We're now ready for postdiction graphs and prediction graphs. Definition: The postdiction graph £or Meeting m and Mode m U the graph <tt"(m,M)^'(m,M)> where, u'(m,M) - {£ R | RcjN and R satisfies Requirements la&3,4 and 5a with respect to w and M} nf(m,M) - {<A,B>e(u"(m t M)J 2 1 r(AjnMW&*M)*+} Definition: The prediction graph for Meeting m and Mode M U the graph <tt 4 (w,M)^ ,, <m,M)> where tt"*(m,M) - {£ R | RsN and R satisfies Requirements lb.2,3,4, and 5b with respect to m and M) w«tm,M) - {<A,B>e<tt1m.M)£ I f -tA^MJ-b^B^M)^} To help clarify these ideas, well work through an example Of the three systems considered above, the circulating bit pipeline is the most interesting from the standpoint of prediction and postdiction. We've redrawn its initialized system net and its initialized control structure in Figure 6.7. (The parts and modes are shown in Figure 3.14.) Let's consider the meeting {5,6}. For m-{5,6}, we have, d.-(m)-{{a}.{d},{h,iMk.l}} and Uf <m)«{a4,h4,k,1} 4^m)-{{b,c},{e/},{g}.{j}} and U**(«Mb,cei,g.j} ■ ■ tv" • ■. • *.. .-.."■»«"' ..-* ; : 159 «M 00 is." « r-1 I ! •H H f' -I .. ft- H »*i-;« ,*t I 5, 1 M H * 04 **» m <*» c ■H « r-l 8 M •H r- t vO ISO Now suppose that M is the mode associated with £vants 2.4J& and ft. Then there are two subnets of the system net satisfying R oo^omonu bOM andla (shewn inUgure 6J(a)) and two subnets satisfying Requirement! m&M, and 8b (fthewn In Agwt «J$g| The resulting postdktfon and prediction graphs are shewn in Figure** <W« use the same graph i ca l l e piientaUo n as for stale graphs.) Our 4ask now is to shew how predta^ graphs Jftd poetd|ction graphs can be used to predict and postdict the patterns of traosaettoru m \$mm m a uHH e n relative to some instance. Of course, we can't say anything about how far tf* syseun stmufetien extends, either forwards or backwards, but we can say that the pettenw of w e n i aiMwt i must be 'consistent* with certain requirements. Definition: ForQcjE, Qtose££onJ||g!t iff ^4^*1^ *-&% 'A set of events is selNnnsisteiit iff it cantata* no more than one event from each meeting. Definition: If ^ and Qj are letf-cocwBttnt sets of «veatt,then, -, QlwQs «* «<i«Q|: ¥«|0% «t*#i*«i«*i We say that £j and Q| am^gtjeftl with one anomitiff Oj^Qj. Two sets of events are cemtoteat with one soother ifV together they contain no more than one event f rim each jiiesU n g. ' Property fcfc If T is a lyitent sirmilanpn, f is an iirtan* m T, en** to a nonaoro integer, then, t»(«,T)ts And, from Req uire me n t (SB, we have the following. 161 (a) Backwards 'History Segments' (b) Forwards 'History Segments Figure 6.8 {>^)6 OW • 5 >Q OW {'.w}Q b {IA7)0 b{ 3 } (a) Postdiction Graph for Meeting {5,6} and Mode {2,4,6,8} (b) Prediction Graph for Meeting {5,6} and Mode {2,4,6,8} Figure 6.9 m Property 6.2: V*t £•: VMiHl VQ#u"(w,M): QUsttf-corolstam VQ#u"*(w,M): Qu self -consistent •Each set of events associated with a node la a patfdfetsen (prediction* graph is self - The next four theorems comprise our results en prodlcthm and p ost dk t s on. Unfortunately, they are quite cu m bersome. They should be repided at only first t o man m stops |n the area of Theorem 6J: (a) If T is a backwtrds-txtendlbte system itm u ssrt o n, f is an occurr en c e in T, w-W*. and McM), then 3Q*sf<*J4): *«<* A tfd,T)*Q and there exists a backwards ex ia ndibh system dmuhHon T' with an oauir en co f ' such that, VneX: ^(fJ^Cf'.TO VaeX*: t.,d',T')ne * s) Q-»-(i*M)nt 4 d'.T') (b) If T U a forwardVextsndible system cfenoltfont f is an occurrence In T, m-Wl^, and MeJW, then aQesfWl): feQ A «4(f,T)'«Q and there exists a forward s -e x tan d i b to system skmibtten T' with an occurrence f ' such that, &' m& Vncl+: t.d.'Ds^d'.TO VeeE*: t^e'.T'Kte 4 Q-e^eOdjnt^f'.TO 163 Proof: We prove just Part (a). Because T is backwards extendible, there exists a system simulation T' with an occurrence g' such that, VneZ": t n ( ? ,T) S t n ( ? ',T') VaeE*: t_|(f '.TOfla + + Now since T is backwards extendible, it must be possible to select T' so that it too is backwards extendible. Let R be the subnet of N defined as follows. E R - xf(m f M)nt_,(? / ,T') s R -CE R uE* R )n<s-s M ) F R - FfKS R xE R UE R xS R ) We can deduce the following about R: (a) 4cE R c»-(m.M) f eE R and def. of E R (b) VaeE*: |anE R |£l ERS-ity'T') (c)S R -CE R UE' R )n(S-S M ) def.ofS R (d) F R -FfXS R xE R UE R xS R ) def. of F R (e) Vs€(S R -UeS z ^'(w)): fife-d V 4 def. of R and Cor. 4.1 In other words, R satisfies Requirements la£5,4, and 5a. Thus E R eu"(m,M). We know that n is an element of both »"(m,M) and t_j(f',T"). and therefore, teE R . Finally, because t-i(?.T) and E R are both subsets of t^'.T'), it follows that t.|(f,T) * E R . □ Theorem 6.2: (a) If T is a backwards-extendible system simulation, A is a holding in T, Mcltf), and m is the unique input meeting of Kl^, then 3Q€a"(m,M): JeXQnm)* A qfoT) » Q and there exists a backwards-extendible system simulation T' with a holding h' such that VneZ": f„(AT) S f„<A'.T') Vc€E*: r.^h'.T) n a + Q-»-(m,M)nr. 1 (h / ,T / ) . ^SS^e^ife^v-^- m (b) If T to » fonwdt- qtttaatbh system e friul s Hsn , A t» » l ie hli n t in T» bUtt&aad w is the unlonc output nmiiif e* *e%t* tJuwuBiH^PMefc MQf)m)*t A ik,T)«Q. and there exists a f orwd»-«ttndJWt sea** HmmnUw T' wJth a hnUtng A' wch that v, •--'"■-•■■■ ^ "■-■? r-a Q.»tWd)rw +l <h',T') Proof: We prove Just Part (a). Because T is backwards extendible, there mi^4tWfffKf^lll^fl^^%^ 9 fi^ fMN N ^ n ( * such that, r-i 0) V*€T: l.<A',T') C» VecE*: l.|(4'.TO f># <•# T W Now since T is backward* exteneibtt, it MUt b«feiettll *#*ete?PP* at that it too is backward* extartdtble Let j be %bi.ipttiy, iipig ■ of a" in T'. Be Line <ft f exim. "Wei " " " '""" " *"" x *"""- "** b*rt*-m«,irt$^m*\}\Kimm *m in In* iwiwxwii m m the pro* ofTW*ntXwei*3QeV*^ > 4 * c * ««x* <o ,.~ --« *«Q and Q-e*<»ad)ni. t <f,T') Because ft (Qnm) end ?•£ fc<Qn«r / (4) Because f initiates A', It follows that, Q-e-(w,ld)ni. 1 (A'J') , <5) And f inaHy, because f „|(e,T) and Q are both subeits of iffitt <X *„1<A.T)-Q <e) 165 Lines 1-6 comprise the desired result Definition: Within the context of a prediction or postdictton graph <«,»>, we write AVB to mean <A, B>€iv. For Aeu, V A - {B|BVA} A V - {B|AVB} Theorem 63 (a) If T is a system simulation, q is an occurrence in T, m - [8) u . Mcl($), QeuimM). A is a negative integer, and there exists a backwards-extendible system simulation T' with an occurrence q' such that, VneZ": t n {q,T)st n iq',T') VaeE*: f k <?',T') n a * t> Q-»-(m,M)nr k ( ? / ,T') then for 7 Q + +, 3Ue v Cfc t kA (q.T) " U and there exists a backwards-extendible system simulation T" with an occurrence q" such that 9" m &' VncZ": r n ( ? ',T') s <„<* ",T") VacE*: t kA {q"J") n a * * U - i;-(m,M)nr k . 1 ( ? ".T") (b) If T is a system simulation, q is an occurrence in T, m-W^, M€l(?X Qeu"*{m,M), * is a positive integer, and there exists a forwards-extendible system simulation T' with an occurrence q / such that VneZ*: ^.Ds^'J') Vo€E*: ( k (?',T')na^ Q-»VM)nr k ( ? ',T') ^,.^y:^m^0^^^^0^»^^^^'Hif^ * - - . **. : then f or Q v * <*.3UoQ v : < k *l<*.T)*U mz** ■ igfupnii V»€l* « B (|'.T')C<.«|".T") VacE* Vl<f"' T "> n « *■♦ u - rtMf>n%4d".T") Proof: We prove Part (a). Because T' It backwards wrtendlbh, theft oUttt a ape* limulattoo T" with an occurrence f" such that, ? * *"-?' «-,: ■■■ t ; .•■■ VnaT: * B (a ',T') C *,£ ",T") ¥«€£♦: l k .,(f".T") a d Because T' is backward* extend**, it omit be paatfbti la ejfta* T" so that It too is backwards extend**. Asmme that tfcfeT} •$ «aft : % #dj^lei'lft»e1» nhmot of N defined atfottawj. E R .»>Mrf)nr k _ I <f'',T'') s R a <' E sl UE l') n ^ s M> ** - rn^iW*!) Now because < k (f 'J") £ ffcCi ",T") and e«B sett caaialft M«*e« from each meeting. / k <j'T'> - t k (f ''T'') Weftowhav*. .•■... ..*.., %. , q - »-<iajK) n r k <*".T") E R - anhM ) n »,.!(•" .to It is a straightforward matter to show that, ns R .*M)-»-<aiia*) 167 Since V Q + <t>, it follows that b-(Q,mM) * ♦ and E R * +. Using the arguments in the proof of Theorem 6.1, we then have, E R e u"(m,M) Thus, E R e v a It remains to be shown that t kA {q,T) * E R . This follows from the fact that f k _i(?.T) and E R are both subsets of < k _i<?",T"). D Theorem 6.4: (a) If T is a system simulation, A is a holding in T, m is the unique input meeting of K3*. Meltf). Qett"(m,M), * is a negative integer, and there exists a backwards- extendible system simulation T' with a holding A' such that, VneT: * B <A,T) S * B (A',T') VaeE*: < k (A',T') o K 4 Q - v'imM) f k (A'.T') then for V Q * *, B U e 7 Ct * k _l<?.T)*U and there exists a backwards-extendible system simulation T" with a holding A" such that, Vn€F: r n (A'.T')£<„<A".T") VacE*: f k .,(A".T") n • * * u-»-(m,M)nr k . 1 (A // ,T' / ) (b) If T is a system simulation, A is a holding in T, m is the unique output meeting of rjfl^, M€l(J), Qett*(m,M) A is a positive integer, and there exists a forwards-extendible system simulation T' with a holding A' such that, VneZ+t I.WDcl.CA'.T') VceE*: t k (A',T')na** Q - »VM) n f k (A'.T') 168 then for Q v +, 3UtQ 7 : and there exists a forwards-extendible system simulation T" with a holding h" such that, V'V VneZ* r > (A'.T')cr 11 (*".T // ) Va«E*: * k+1 (A".T") a k 4 U«»"Wf)ru k ,,(A'',T'') Proof: Similar to that of Theorem S3. As a limited illustration of the preceding results, consider the system of Figure 6.7 and the postdiction graph of Figure 6.9(a). All system simulations are backwards (and forwards) extendible. Consider Event 5. It belongs to Meeting {&£}, and its information content contains Mode {2,4^,6}. Now if q is any occurrence of Event 5 in a system simulation T, then from Theorems 8J(a) and 63(a), we have, r.l(f.T)*{UB} UfoT) * m t4qJ)*{l,s,&) The odd-numbered transactions preceding q are consistent with {1A5}, while the even numbered- transactions preceding f are consistent with {7}. This checks out with the system simulation in Figure 6.10. Here we have, '. S (?.T)-{4,6,7} '-3(?T) - + 169 d • • j *• c Figure 6.10 A System Simulation m CHAPTER 7 CONCLUSIONS 7J. Evaluation: With th« theory lntradvocd in the preceding chapters, we tit now able to trait important kinds of Petri nets that wem previously eiitslde U«e seeps of any theory. Tht nat rapreaanting the half adder it Just one example. From ail indfeiitons, Hie dais of neti contained In our theory Is rich and varied. The theory has the following advantages: (1) The range of concepts expressible within the theory Is extremely broad. Among those concepts are soma that are fenttamsntal "Spaee 1 , fens', mtormetion', and 'causaHty* are the most notable. (2) The theory takes into account the distributed netepe of systems. Concurrency Is the key concept here, and concurrency is embedded in thefabric of the theory. - (S) Because the theory does not rely on the none* of "total system state*, the complexity of a system model Is reduced signlfteamh/. (4) Identifying the system net with tht system "hardware', and die set of initial conditions with tht system 'software* is a step towards an UHagretsd approach to both hardware and software. (5) The techniques of die theory lend themselves to automation. 171 7.2. Future Work: The work that needs to be done falls into two categories: theory and metatheory. The metatheory is concerned with four related topics: (1) foundations, (2) semantics, (S) methodology, and (4) scope. (1) foundations - The theory we've presented depends upon five axioms. We've tried to make those axioms plausible, but clearly more work needs to be done. The goal here should be to reduce those five axioms to another set of axioms that are more or less self-evident (2) semantics - A number of concepts have been introduced in the theory, and we need to understand the meanings of those concepts. The two that are of the most concern are parts and modes. We've said that parts are associated with strictly sequential behavior, and that modes are associated with steady-state behavior. But we need to know much more about these concepts - in particular, how they relate to concepts already familiar to us. (Note that foundations and semantics are intertwined.) (S) methodology - For the theory to be a practical tool, there has to be a methodology for applying the theory. A set of practical examples is necessary in establishing such a methodology. (4) scope - The scope of a theory is the range of problems to which it is suited. We must find out for which problems the above theory is suited and for which it is not suited. In the mathematical development of the theory, there are several areas that deserve attention. (1) For a particular system net, there may be several ways of choosing a covering of parts and a covering of modes. We need to determine precisely the effects of those choices. We already know that the control structure and the information contents of the system elements are, in general, affected. (2) The four theorems of Chapter 6 are quite cumbersome, and are only the first tentative steps in the area of prediction and postdiction. Much more work remains to be done. (In this area, Theorem 4.3 ought to play an important role.) (3) The ability to predict and postdict system behavior should provide the key to answering the following questions about a system. These questions were posed in Section IS. Under what conditions will a certain pattern of behavior be produced? 172 What arc the consequences of a decision within a system? What are the effect* of 1 system modif kation? How does behavior m one part of a HWsni lorlWHW liluu tor tn another part? How do the outputs of a spurn depend upon the inputs? (Le* What i» the 'function' of the system?) A systematic technique needs to be de v e lo p ed for each of these outsttons. (4) Within this thesis, we have net touched A^en HiobabrtbM. coretderattons. This is a major area, and one which witt reejuiro noaiideiihhi effort "EImm ^effort will entail relating the approach present e d here with the ideas of Information Theory. In partfcuhur, ft wi» be neaiojir j m n**timm*m of Htf— niitluii canter* so Shannon's information (5) In Section 5* we hitt o du ot d thffinch^^ property allowed u» to define instants of ttm* It iwisfo bo fcrtoteabej So invosayate other possible constrain* on '-the ""tomm^WmmV^&lmm^ mfr **Mi*J*t space/time trameworu nugnt correspono so twei*eutsuoean spaces.; The success of these efforts wilt determine the fruttfulness of the ideas presented m this thesis. In any eirent, we hope to ha ve stbmtktsd the reader to tthWJ lB | ab o ut the lOMot raised. m REFERENCES 1. Baker, H. G„ Equivalence Problem! of Petri Nets, S.M. Thesis, Department of Electrical Engineering, Massachusetts Institute of Technology, June 1973. Z Berge, C, Graphs and Hvoergraphs, North-Holland Publishing Co, 1971 3. Commoner, F. C, Deadlocks in Petri Nets, Report CA-72Q6-2SH, Applied Data Research, Inc. Wakefield, Mass, June 1972. 4. Commoner, F, A. W. Holt, S. Even, and A Pnueli, "Marked Directed Graphs", journal c£ Computer and System Sciences. Vol 8, October 1971, pp. 511-523. 5. Furtek, F. C, Modular Implementation of Petri Neg, S.M. Thesis, Department of Electrical Engineering, Massachusetts Institute of Technology, September 1971. 6. Furtek, F. C "Asynchronous Push-Down Stacks", Computation Structure* Group Memo 86. Project MAC, Massachusetts Institute of Technology, August 1973. 7. Genrich, H. J, Elnfache Nlcht-seauentielle Proiesse (Simple Nonsequential Processes). Bertcht Nr. 37, Gesetlschaft fur Mathematik und Datenverarbeitung, Bonn. 1971. 8. Hack. M. H. T, Analysis of Production Schemata by. Petri Nets, Technical Report M AC-TR-94, Project MAC, Massachusetts Institute of Technology, February 197a 9. Hack, M. H. T, "Extended State-Machine AUocatable Nets", Computation Structures Group Memo 78-1, Project MAC, Massachusetts Institute of Technology, June 1974. 10." Holt, A. W, et at, Final Report gf the Information System Theory Prgjert, Technical Report No. RADC-TR-68-305, Rome Air Development Center, Grtffis Air Force Base, New York. September 1968. 1L Holt, A. W. and F. G. Commoner, Events and Conditions. Part I Applied Data Research. Inc. New York, 1970. (Chapter I, II and IV appear in Record of the Protect MAC Conference on Concurrent Systems and Parallel Computation, ACM, New York, 1970, pp. 9*) 12. Holt, A. W, Events and Conditions. Part 2. 13. Holt, A. W„ Events and Conditions. Part 3. (Reprinted in Record of the, Protect MAC Conference on Concurrent Systems and Parallel Computation, pp. 33-52.) 14. Holt, A. W„ "Communication Mechanics", Applied Data Research, Inc. Wakefield. Mass., 1974. IN* 15. Holt, A. W, "Information at a System RolMrn Concept", Applied Data Research, Inc. Wakef ieW, Mast, September 1974. > & Jtmtp, J. R, and R,S. ThJefsraJea, X)n the IqolvM ^ of ^ wfrwi o oiw Control Structure*," SIAM Journal of Owt|Hiiatian, Vol t Wo^t.>Mit Mfp f*4?. 17. Paul S. S„ Llmitattcns and CjtnJflJttT 4 ^^ak Jp^ohoji-f^lTot far C oogdAnation i &•**> Mono ff7, pTojean* ACTMasimchusettt amonx IS. Patrt, C. A^C9mn^rtq t tton.yj^^gjoaa^ RADC-TR-65- 377, Vok y Rosa* A* linmimmt Cmm.Pimm Ato Jyca Boss^ N«t Yotk 1^6. [Originally published in Ohsumi iMHMWJJMJBII isfR jyjMlnl lllirlHun illi IT f i r I ^ Westfaltschon btsttaftoi fur ftutwiwinHlli U*m**TWmlM&m*Tffih.HK. 2, 19. Petri, C A, "Fundamentals of a Theory of Aty i whra n eu j Information Flow", Proceedings of ~ fHP#MttflN'Mlk^^ 20. Petri, C. A, "Grundiattttdm sur B o Khreibunf Dbkreter Promat", Colloquium uber 2L Petri, C. A, Series of talks given at Applied Data Retouch, inc. Wakefield, Mast, August 1971 22. Petri, C A, "Concepts o f Net pmn?'- H imtto * ^ Fou ndati ons of Compunr Sdsnce, ofathemslicel bMtlHai of the Slovak Academy of ■:- Hie& TtAmJeaatamer WIV 29. Ramchandaid. C, Anabasi of Awnchronom fifflflfmm Swaum b* Petri Nets. Technical ' PlNlPHMPV yvs-,-*. :-^&^i*^H%3«%!: m INDEX alternative 44 alternative classes 80 alternativeness relation for Part P 44 back cone 113 backwards conflict 97 backwards conflict dunes 97 basic circuit 102 blank circuit 102 boundary 31 causal connection 94 causality relation 90 chain 156 circuit 29 coi n cid en t 91 concurrent 94 consistent 160 control structure SO distance 142 elementary causal connections 91 elementary circuit 26 event co m po ne nt 26 event graph 24 event-graph de c o m po sa ble 26 events 24 extendible 151 flow relation 24 follows 94 forwards conflict 97 forwards conflict classes 97 front cone 119 fundamental circuit 192 holdings 30 image 34 in phase 131 information content 75 initial conditions 24 initiatlud Petri net 24 initiate 31 input events 24 input states 24 instant of time 199 interval of time 09 link 50 meeting 50 net 29 mnsynchronous 129 occurrences w output events 24 output states 24 Petri net 24 phase relation 191 phase transitions 191 phases 131 po stcond itions 24 precedes 34 preconditions 24 self-consistent 160 simulation 30 simultaneity classes 139 simultaneity relation 199 state component 26 state graph 24 state-graph decomposable 26 starts 24 strand 35 subnet 23 synchronic delay 108 synchronic distance 125 synchronous 129 synchronous system 129 176 synchrony property 129 system 40 system space 129 terminate 31 time 139 time interval 136 token loading 102 transaction 146