Pe o mance Bounds o Synch onized
Queueing Ne wo ks
Ja ie Campos Laclaus a
Tesis Doc o al
Depa amen o de Ingenie ´ıa El´ec ica e In o m´a ica
Uni e sidad de Za agoza
Oc obe 1990
i
No es dado a odos a en u a se en la sel a y aza ,
a ue za de ene g´ıa, un camino p ac icable, pe o aun
los m´as humildes podemos ap o echa nos del sende o
abie o po el genio, y a anca , caminando po ´el,
alg´un sec e o a lo desconocido.
San iago Ram´
on y Cajal
Los ´onicos de la olun ad, 1897
ii
Con en s
Lis o figu es ii
Lis o ables xiii
P e ace x
Acknowledgemen s xix
1 Synch onized queueing ne wo ks and Pe i ne s 1
1.1 Queueing ne wo ks wi h synch oniza ions ......... 2
1.1.1 Monoclass queueing ne wo ks ........... 2
1.1.2 Addi ion o synch oniza ion schemes ....... 6
1.2 S ochas ic Pe i ne s .................... 8
1.2.1 In oducing ne s .................. 9
1.2.2 Some e minology .................. 13
1.2.2.1 Ne s uc u e ............... 13
1.2.2.2 Token game ................ 14
1.2.2.3 Basic p ope ies .............. 14
1.2.3 On s ochas ic Pe i ne s .............. 15
1.2.3.1 Timing and fi ing p ocess ........ 15
1.2.3.2 Single e sus mul iple se e seman ics .17
1.2.3.3 E godici y and measu abili y ...... 20
1.3 Mapping be ween monoclass synch onized queueing ne -
wo ks and s ochas ic Pe i ne s .............. 26
1.4 Analy ical echniques o synch onized queueing ne wo ks 28
1.5 An o e iew o pe o mance bounds o s ochas ic Pe i
ne s ............................. 33
iii
i CONTENTS
2 Pe i ne subclasses and bases o quali a i e heo y 37
2.1 FRT-ne s and subclasses .................. 40
2.1.1 FRT-ne s ...................... 41
2.1.1.1 Defini ion ................. 42
2.1.1.2 Algeb aic cha ac e iza ion ........ 44
2.1.1.3 Quali a i e p ope ies .......... 51
2.1.2 Mono-T-semiflow, s uc u ally decision- ee ne s,
and ma ked g aphs ................. 57
2.1.2.1 Mono-T-semiflow ne s .......... 57
2.1.2.2 S uc u ally decision- ee ne s ...... 60
2.1.2.3 Ma ked g aphs .............. 61
2.1.3 F ee choice ne s ................... 64
2.1.4 FRT-ne s communica ing h ough buffe s ..... 69
2.1.4.1 De e minis ic sys ems o sequen ial p o-
cesses .................. 70
2.1.4.2 To ally open de e minis ic sys ems o
sequen ial p ocesses ........... 74
2.2 Pe sis en ne s and beha iou ally ex ended ee choice ne s 84
2.2.1 Pe sis en ne s ................... 84
2.2.2 Beha iou ally ex ended ee choice ne s ...... 88
2.3 Conclusions ......................... 89
3 Bounds o s ongly connec ed ma ked g aphs 91
3.1 Uppe bound o he s eady-s a e h oughpu ...... 94
3.1.1 Li le’s law and P-semiflows ............ 94
3.1.2 Reachabili y o he uppe bound .......... 98
3.1.3 In e p e a ion and de i ed esul s .........100
3.2 Lowe bound o he s eady-s a e h oughpu .......102
3.2.1 Basic esul o 1–li e ma ked g aphs .......103
3.2.2 Ex ension o bounded ma ked g aphs .......105
3.2.3 Reachabili y o he lowe bound ..........109
3.2.4 A polynomial algo i hm o compu e he lowe
bound ........................111
3.3 Ex ending esul s o unbounded ma ked g aphs .....113
3.4 Conclusions .........................120

CONTENTS
4 Bounds o li e and bounded ee choice ne s 123
4.1 Uppe bounds o he s eady-s a e h oughpu ......124
4.1.1 Li le’s law and linea ma king ela ions .....125
4.1.1.1 S uc u al linea ma king ela ions ...126
4.1.1.2 Li le’s law and P-semiflows .......127
4.1.1.3 Li le’s law and aps ...........131
4.1.2 A new pe spec i e: implici places .........134
4.1.2.1 Implici places ..............134
4.1.2.2 Rein e p e a ion o aps using implici
places .................. 136
4.1.2.3 Implici places imp o e aps-based
bounds .................. 138
4.1.3 Mul ise s o ci cui s: de i a ion o a eachable
uppe bound ....................142
4.2 Lowe bounds o he s eady-s a e h oughpu ......161
4.3 Conclusions .........................163
5 Ex ensions o o he ne subclasses 165
5.1 Mono-T-semiflow ne s ...................165
5.1.1 Lowe bound o he mean cycle ime .......167
5.1.2 Uppe bound o he mean cycle ime .......171
5.2 FRT-ne s ..........................173
5.2.1 Lowe bound o he mean cycle ime .......173
5.2.2 Uppe bound o he mean cycle ime .......175
5.3 To ally open de e minis ic sys ems o sequen ial p ocesses176
5.3.1 Cha ac e iza ion o e godici y ...........176
5.3.2 Compu ing he s eady-s a e pe o mance measu es179
5.4 Pe sis en ne s ........................181
5.4.1 Lowe bound o he mean cycle ime .......181
5.4.1.1 A eachable bound ............184
5.4.2 Uppe bound o he mean cycle ime .......185
5.5 Conclusions .........................186
6 Addi ional bounds and imp o emen s 187
6.1 Bounds o o he pe o mance indexes ...........188
6.1.1 Bounds o he mean leng h o queues .......188
6.1.2 Maximum capaci y o queues ...........190
i CONTENTS
6.1.3 O he compu able bounds .............191
6.2 Imp o ing he bounds o Coxian iming .........191
6.2.1 F ee choice case ...................192
6.2.2 Non- ee choice case ................200
6.3 Conclusions .........................201
7 Applica ions o dis ibu ed sys ems 203
7.1 Dis ibu ed compu ing sys ems ..............203
7.1.1 The al e na ing bi p o ocol ............204
7.1.2 A so wa e example .................205
7.1.3 The PADMAVATI a chi ec u e ..........211
7.1.4 A da aflow g aph ..................216
7.2 Manu ac u ing sys ems ...................219
7.2.1 A job-shop sys em .................219
7.2.2 A kanban sys em ..................221
7.2.3 A p oduce -consume sys em ...........225
Conclusions 229
Bibliog aphy 235
Lis o Figu es
1.1 A simple compu e sys em wi h i ual memo y. ..... 3
1.2 Queueing ne wo k model o a mul ip og amming mem-
o y limi ed sys em. ..................... 7
1.3 Queueing ne wo k model o a o k/join mul i asking p o-
cess. ............................. 8
1.4 Typical schemes in he modelling o dis ibu ed sys ems. 10
1.5 Pa ial o del o malism and empo al ealism. ...... 11
1.6 A ne wi h enabling bound g ea e han li eness bound
o ansi ion 1....................... 19
1.7 A i ial weakly bu non-s ongly ma king e godic de-
e minis ic ne . ....................... 21
1.8 A ne wi h home s a es bu possibly non-e godic ma king
p ocess. ........................... 22
1.9 A li e and bounded ne wi hou home s a es. ....... 23
1.10 Reachabili y g aph o he ne in figu e 1.9 ........ 24
1.11 An example o s ochas ic Pe i ne ep esen ing a ne -
wo k o delay s a ions. ................... 26
1.12 A Pe i ne ep esen a ion o a monoclass single-se e
queue. ............................ 27
1.13 A Pe i ne ep esen a ion o a queueing ne wo k. .... 27
1.14 A mo e gene al s ochas ic ne and he co esponding syn-
ch onized queueing ne wo k. ................ 29
1.15 Pe i ne model o a mul ip og amming memo y limi ed
sys em. ........................... 30
1.16 Pe i ne model o a o k/join mul i asking p ocess. ... 30
1.17 Pa hological cases o synch onized queueing ne wo ks. .. 31
ii
iii LIST OF FIGURES
2.1 A ne whose isi a ios depend on he s uc u e, on he
ou ing a conflic s, on he ini ial ma king, and on he
se ice imes. ........................ 38
2.2 Inclusion ela ions among FRT-ne subclasses (∗ hese
a e ma ked ne s). ...................... 41
2.3 A li e and s uc u ally bounded FRT-ne . ........ 44
2.4 In oduc ion o a local schedule a an equali y conflic
se . .............................. 46
2.5 Coun e -example o he con e se o lemma 2.1.1. ..... 47
2.6 The addi ion o a oken o p5kills he ne (sequence
σ= 4leads o a deadlock). ................ 53
2.7 Li e and bounded FRT-ne which is no s uc u ally
bounded. .......................... 54
2.8 A non- e e sible li e and s uc u ally bounded FRT-ne . 55
2.9 A li e and s uc u ally bounded FRT-ne wi hou home
s a es. ............................ 56
2.10 A li e and s uc u ally bounded mono-T-semiflow ne . .58
2.11 A de e minis ic sys em o sequen ial p ocesses. ...... 71
2.12 Subs i u ion o s a e machines by ansi ions in he ne
o figu e 2.11. ........................ 73
2.13 A o ally open de e minis ic sys em o sequen ial p ocesses. 75
2.14 A non-consis en o ally open de e minis ic sys em o
sequen ial p ocesses. .................... 77
2.15 Consis en o ally open de e minis ic sys ems o sequen-
ial p ocesses wi h wo s a e machines and wo buffe s. .78
2.16 S uc u ally ma king non-e godic sys em wi h h ee
s a e machines. ....................... 80
2.17 Regula ion ci cui s be ween ansi ions in global syn-
ch onic dis ance ela ion. .................. 82
2.18 Pe sis en ne . ........................ 85
2.19 Pe sis en and non-pe sis en ne s wi h he same s uc u e. 86
2.20 An unbounded li e pe sis en ne ha ing he di ec edness
p ope y bu wi hou home s a es. ............ 87
2.21 S uc u ally pe sis en bu non-s uc u ally decision- ee
ne . ............................. 89
P e ace
P oduc o m queueing ne wo ks ha e long been used o he pe o -
mance e alua ion o compu e sys ems. Thei success has been due o
hei capabili y o na u ally exp essing sha ing o esou ces and queue-
ing, ha a e ypical si ua ions o adi ional compu e sys ems, as well
as o hei efficien solu ion algo i hms, o polynomial complexi y on
he size o he model. Un o una ely, he in oduc ion o synch oniza-
ion cons ain s usually des oys he p oduc o m solu ion, so ha
gene al concu en and dis ibu ed sys ems a e no easily s udied wi h
his class o models.
Pe i ne s ha e been p o ed specially adequa e o model pa allel
and dis ibu ed sys ems. Mo eo e , hey ha e a well- ounded heo y o
analysis ha allows o in es iga e a g ea numbe o quali a i e p op-
e ies o he sys em.
In he o iginal defini ion, Pe i ne s did no include he no ion o
ime, and ied o model only he logical beha iou o sys ems by de-
sc ibing he causal ela ions exis ing among e en s. This app oach
showed i s powe in he specifica ion and analysis o concu en sys-
ems in a way independen o he concep o ime. Ne e heless he
in oduc ion o a iming specifica ion is essen ial i we wan o use his
class o models o he pe o mance e alua ion o dis ibu ed sys ems.
One o he main p oblems in he ac ual use o imed and s ochas ic
Pe i ne models o he quan i a i e e alua ion o la ge sys ems is he
explosion o he compu a ional complexi y o he analysis algo i hms.
In gene al, exac pe o mance esul s a e ob ained om he nume ical
solu ion o a con inuous ime Ma ko chain, whose dimension is gi en
by he size o he s a e space o he model. S uc u al compu a ion
o exac pe o mance measu es has been possible o some subclasses
o ne s such as hose wi h s a e machine opology. These ne s, unde
x

x i PREFACE
ce ain assump ions on he s ochas ic in e p e a ion a e isomo phic o
Go don and Newell’s ne wo ks, in queueing heo y e minology. In
he gene al case, efficien me hods o he de i a ion o pe o mance
measu es a e s ill needed.
Two complemen a y app oaches o he de i a ion o exac measu es
o he analysis o dis ibu ed sys ems a e he u iliza ion o app oxima-
ion echniques and he compu a ion o bounds. App oxima e alues
o he pe o mance pa ame e s a e in gene al mo e efficien ly de i ed
han he exac ones. On he o he hand, “exac ness” only exis s in
heo y! In o he wo ds, nume ical algo i hms mus be applied in p ac-
ice o he compu a ion o exac alues, he e o e making e o s is
ine i able.
Pe o mance bounds a e use ul in he p elimina y phases o he de-
sign o a sys em, in which many pa ame e s a e no known accu a ely.
Se e al al e na i es o hose pa ame e s should be quickly e alua ed,
and ejec ed hose ha a e clea ly bad. Exac (and e en app oxima e)
solu ions would be compu a ionally e y expensi e. Bounds become
use ul in hese ins ances since hey usually equi e much less compu a-
ion effo .
The compu a ion o uppe and lowe bounds o he s eady-s a e
pe o mance o imed and s ochas ic Pe i ne s is conside ed in his
wo k. In pa icula , we s udy he h oughpu o ansi ions, defined
as he a e age numbe o fi ings pe ime uni . Fo his measu e we
y o compu e uppe and lowe bounds in polynomial ime on he size
o he ne model, by means o p ope linea p og amming p oblems
defined om he incidence ma ix o he ne (in his sense, we de elop
s uc u al echniques). These bounds depend only on he mean alues
and no on he highe momen s o he p obabili y dis ibu ion unc ions
o he andom a iables ha desc ibe he iming o he sys em. The
independence o he p obabili y dis ibu ions can be iewed as a use ul
gene aliza ion o he pe o mance esul s, since highe momen s o he
delays a e usually unknown o eal cases, and difficul o es ima e and
assess.
F om a diffe en pe spec i e, he ob ained esul s can be applied o
he analysis o queueing ne wo ks ex ended wi h some synch oniza ion
schemes. Monoclass queueing ne wo ks can be mapped on s ochas ic
Pe i ne s. On he o he hand, s ochas ic Pe i ne s can be in e p e ed
PREFACE x ii
as monoclass queueing ne wo ks augmen ed wi h synch oniza ion p im-
i i es.
Conce ning he p esen a ion o his manusc ip , i should be men-
ioned ha chap e 1 has been w i en wi h he objec o gi ing he
eade an ou line o he s ochas ic Pe i ne model: i s defini ion, e -
minology, basic p ope ies, and ela ed concep s, oge he wi h i s deep
ela ion wi h o he classic s ochas ic ne wo k models.
Chap e 2 is de o ed o he p esen a ion o he ne subclasses con-
side ed in he es o he wo k. The classifica ion p esen ed he e is
qui e diffe en om he one which is usual in he amewo k o Pe i
ne s. The eason lies on he ac ha ou classifica ion c i e ion, he
compu abili y o isi a ios o ansi ions, is in oduced o he fi s
ime in he field o s ochas ic Pe i ne s in his wo k. The significance o
ha c i e ion is based on he impo an ole ha he isi a ios play in
he compu a ion o uppe and lowe bounds o he pe o mance o he
models. Ne e heless, classical impo an ne subclasses a e iden ified
he e in e ms o he compu abili y o hei isi a ios om diffe en
pa ame e s o he model.
Chap e 3 is conce ned wi h he compu a ion o eachable uppe
and lowe bounds o he mos es ic i e subclass o hose p esen ed
in chap e 2: ma ked g aphs. The explana ion o his ac is easy o
unde s and. The mo e simple is he model he mo e accessible will be
he echniques an ideas o he de elopmen o good esul s.
Chap e 4 p o ides a gene aliza ion o li e and bounded ee choice
ne s o he esul s p esen ed in he p e ious chap e . Quali y o ob-
ained bounds is simila o ha o s ongly connec ed ma ked g aphs:
h oughpu lowe bounds a e eachable o bounded ne s while uppe
bounds a e eachable o 1–bounded ne s.
Chap e 5 conside s he ex ension o o he ne subclasses, like mono-
T-semiflow ne s, FRT-ne s, o ally open de e minis ic sys ems o se-
quen ial p ocesses, and pe sis en ne s. The esul s a e o di e se
colou s. Fo mono-T-semiflow ne s and, he e o e, o gene al FRT-
ne s, i is no possible (so a ) o ob ain eachable h oughpu bounds.
On he o he hand, o bounded o dina y pe sis en ne s, igh h ough-
pu uppe bounds a e de i ed. Mo eo e , in he case o o ally open
de e minis ic sys ems o sequen ial p ocesses he exac s eady-s a e pe -
o mance measu es can be compu ed in polynomial ime on he ne size.
x iii PREFACE
In chap e 6 bounds o o he in e es ing pe o mance measu es a e
de i ed om h oughpu bounds and om classical queueing heo y
laws. A e ha , we explo e he in oduc ion o mo e in o ma ion om
he p obabili y dis ibu ion unc ions o se ice imes in o de o im-
p o e he bounds. In pa icula , o Coxian se ice delay o ansi ions
i is possible o imp o e he h oughpu uppe bounds o p e ious chap-
e s which held o mo e gene al o ms o dis ibu ion unc ions. This
imp o emen shows o be specially ui ul o li e and bounded ee
choice ne s.
Chap e 7 is de o ed o case s udies. Se e al examples aken om
li e a u e in he fields o dis ibu ed compu ing sys ems and manu-
ac u ing sys ems a e modelled by means o s ochas ic Pe i ne s and
e alua ed using he echniques de eloped in p e ious chap e s.
Finally, some concluding ema ks and conside a ions on possible
ex ensions o he wo k a e p esen ed.
Acknowledgemen s
I is a pleasu e o acknowledge a ew o my deb s. Like all Spanish Pe i
ne s’ esea che s, I owe e e y hing o Manuel Sil a; iend, colleague,
and ad iso o his hesis, o whom go my o emos hanks, o his
cons an guidance and help.
I would also like o hank Miguel San Miguel, who fi s a oused my
in e es in applied s ochas ic p ocesses and queueing heo y.
I mus say how g a e ul I am o all he colleagues o he G upo de
Ingenie ´ıa de Sis emas e In o m´a ica o he Uni e sidad de Za agoza,
and especially o Jos´e Manuel Colom, who has offe ed cons uc i e
commen s and discussions du ing he pas yea s.
O he pe sons ha e con ibu ed o he de i a ion o he esul s p e-
sen ed in his manusc ip . Special hanks go o Gio anni Chiola, o
his ui ul coope a ion.
Finally, o my amily and iends. I am e e nally g a e ul o hei
pa ience and suppo .
Ja ie Campos
Za agoza, Oc obe 1990.
xix
xx ACKNOWLEDGEMENTS

Chap e 1
Synch onized queueing
ne wo ks and Pe i ne s
Queueing ne wo k models a e one o he mos popula and classical
ools o he pe o mance e alua ion o compu e sys ems. Wi h he
ad en o complex dis ibu ed sys ems, many p oposals ha e been made
o ex end he modelling powe o queueing ne wo ks by adding a ious
synch oniza ion mechanisms o he basic model. One o he mos im-
po an cha ac e is ics o basic queueing ne wo ks ha de e mined hei
popula i y was he de elopmen o efficien (polynomial complexi y) al-
go i hms, based on hei “p oduc o m solu ion”. Un o una ely, he
in oduc ion o synch oniza ion mechanisms usually des oys his nice
p ope y.
Mo e ecen ly, imed and/o s ochas ic Pe i ne models ha e been
in oduced as a modelling ool capable o na u ally ep esen synch o-
niza ion and concu ency. The in ima e ela ion be ween synch onized
queueing ne wo ks and s ochas ic Pe i ne s is s essed in his chap e .
A e an his o ical ou e h ough he main hi s o queueing ne wo ks
heo y, we jus i y he necessi y o he in oduc ion o synch oniza ion
schemes o he pe o mance e alua ion o dis ibu ed sys ems. Then,
we o mally in oduce he model o Pe i ne s, as well as he diffe -
en implica ions ha he addi ion o a iming in e p e a ion has in he
model. Finally, he close ela ions be ween queueing ne wo ks wi h
synch oniza ion cons ain s and s ochas ic Pe i ne s a e ema ked.
1
2CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
1.1 Queueing ne wo ks wi h synch o-
niza ions
Queueing ne wo k models ha e been used o pe o mance e alua ion
since he ea ly wo k o A. E lang [E l09]. Thei success o he analysis
o compu e sys ems (see, e.g., [Kle76,LZGS84,La 89]) has been due o
hei capabili y o na u ally exp essing sha ing o esou ces and queue-
ing, ha a e ypical si ua ions o adi ional compu e sys ems, as well
as o hei efficien solu ion algo i hms, o polynomial complexi y on
he size o he model.
1.1.1 Monoclass queueing ne wo ks
A queueing ne wo k model o a sys em is a collec ion o se ice cen e s
o s a ions and cus ome s mo ing among hem. The se ice cen e s
ep esen diffe en p ocessing si es while cus ome s ep esen jobs o
p ocesses. Cus ome s can en e he sys em a ce ain poin s; a e ha
hey mo e om one s a ion o ano he , queueing up a each o some
se ice; and ocassionally hey depa om he sys em.
Mo e o mally, a queueing ne wo k is a io SC,R,X
0, whe e
•SC={1,...,m}is he se o se ice cen e s,
•Ris he eal ma ix o ou ing p obabili ies ij ≥0; i, j =1,...,m;
whe e ij is he p obabili y ha a cus ome exi ing cen e igoes
o j, and
•X0is he ec o o ex e nal a i al a es X0i≥0, i=1,...,m,
o s a ions.
I X0i= 0 o all s a ion i, he numbe o cus ome s in he ne wo k
emains cons an , i is deno ed as N, and he sys em is called closed
ne wo k. O he wise, he ne wo k is said o be open.
A queueing ne wo k can be seen as a di ec ed g aph in which se ice
cen e s a e he nodes. An a c om node i o node jis d awn iff ij >
0. As an example, see he closed ne wo k depic ed in figu e 1.1, ha
models a simple compu e sys em wi h i ual memo y [GP87]. In his
CPU
memo y
disc
ρ
1
ρ
2
ρ
3
s12
3
s
s
1.1. Queueing ne wo ks wi h synch oniza ions 3
Figu e 1.1: A simple compu e sys em wi h i ual memo y.
case, i CPU,memo y, and disc a e labelled wi h indexes 1,2, and 3,
espec i ely, we ha e
R=⎛
⎜
⎝
ρ1ρ2ρ3
100
100
⎞
⎟
⎠(1.1)
In ac , since each node in he sys em is a se ice cen e wi h a
s o age oom o queues o o m, a queueing ne wo k can be seen also
as a bipa i e di ec ed g aph. Se ice cen e s and s o age ooms a e
he wo kinds o nodes. An a c exis s om each s o age oom o i s
co esponding se ice cen e . Finally, an a c om he se ice cen e i
o he s o age oom p eceding cen e jis d awn iff ij >0.
The s a e o he ne wo k is defined by a ec o n =(n1,...,n
m)T,
whe e niis he numbe o cus ome s a cen e i(including hose being
se ed and hose wai ing).
In o de o comple ely define he model, he queueing disciplines
a each o he s o age ooms, he in ensi y o a i als om ou side,
he se ice equi emen s o jobs a cen e s, and specially he a e age
se ice ime sio each s a ion imus be specified. When all he abo e
pa ame e s a e “app op ia ely” defined he e olu ion o he sys em can
be modelled by a con inuous ime Ma ko chain [Re 84]. In his case
he limi , o s a iona y, s a e dis ibu ion can be ound, i i exis s,
by sol ing a sys em o linea equa ions, called global balance equa ions,
which, o each s a e, equa es he a e o flow in o o he a e o flow
ou o he s a e. Un o una ely, he numbe o s a es (and he e o e
he dimension o he sys em o equa ions) inc eases quickly when he
numbe o cus ome s and s a ions g ows.
4CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
The ollowing sys em o equa ions [Kle75] can be de i ed om he
global balance p ope y:
X(j)=X0j+
m

i=1
X(i) ij j=1,...,m (1.2)
whe e X(i) is he limi h oughpu o s a ion i, i.e., he a e age numbe
o se ice comple ions pe uni ime a s a ion i.
I he ne wo k is open (i.e., i he e exis s a s a ion jwi h posi-
i e ex e nal a i al a e, X0j>0), hen he abo e mequa ions a e
linea ly independen , and he exac h oughpu s o s a ions can be de-
i ed (independen ly o he se ice imes). This is no he case o
closed ne wo ks. I X0j=0,j=1,...,m, hen only m−1 equa-
ions a e linea ly independen , and hus only a ios o h oughpu s can
be de e mined. These ela i e h oughpu s which a e o en called isi
a ios, deno ed as i o each s a ion i, summa ize all he in o ma ion
gi en by he ou ing p obabili ies ha is necessa y in mos cases o he
compu a ion o he pe o mance measu es. The isi a ios no malized,
o ins ance, o s a ion 1 a e defined as:
(1)
i
de
=X(i)
X(1) i=1,...,m (1.3)
Fo a es ic ed class o ne wo ks, called p oduc o m ne wo ks,
he solu ion o he global balance equa ions can be shown o be a
p oduc o e ms, one o each s a ion, whe e he o m o each e m
is explici ly gi en. This ac occu s when he sys em sa isfies he local
balance equa ions [Cha72]. In o mally, a local balance equa ion asse s
ha o any wo adjacen s a es he effec i e flow om one o he o he
mus be equal o he effec i e flow in he o he di ec ion.
J. Jackson [Jac63] ound he fi s p oduc o m solu ion in a gene al
ne wo k o queues, mo i a ed by manu ac u ing applica ions. J. Jack-
son conside ed open monoclass ne wo ks wi h a Ma ko ian a i al p o-
cess dependen on he o al popula ion o he ne wo k. Se ice disci-
plines a e FCFS (fi s -come fi s -se ed) and se ice imes a e exponen-
ial (wi h queue leng h dependen a es). W. Go don and G. Newell
[GN67] ex ended Jackson’s esul s o co e closed ne wo ks.
The s eady-s a e p obabili y p(n) o s a e n =(n1,...,n
m)Tin a
p1
p2p3
p5
p4
1
2 3
4
p2p5
p3p4
p2p3
p4p5
p1
1
2 3
2
3
4
s + max (s ,s ) + s ≠
1234
s + s + s + s
1234
1.2. S ochas ic Pe i ne s 11
Figu e 1.5: Pa ial o del o malism and empo al ealism.
(see figu e 1.4). In his di ec ion, Pe i ne s imp o e clea ly he mod-
elling powe o classic queueing ne wo ks, o which synch oniza ions
a e difficul o impossible o exp ess, excep o some ex ended o -
malisms (see sec ion 1.1.2).
One aspec o he adequacy o Pe i ne models is hei possibili y
o exp essing all basic seman ics o concu ency, in e lea ing,s ep, and
pa ial o de seman ics, which can be compa ed wi hin he Pe i ne
o malism. In his sense, Pe i ne s a e capable o modelling “ ue
concu ency”. The impo ance o ue concu ency in a pe o mance
o ien ed concu en model can be explained om he empo al ealism
ha p o ides s ep and pa ial o de seman ics o concu en e en s.
Le us b iefly desc ibe hese conside a ions wi h he use o he ne
depic ed in figu e 1.5. Ac i i ies modelled wi h ansi ions 2and 3
a e uly concu en . This means ha he comple ion ime o bo h
is max{γ2,γ
3}i γ2and γ3a e hei espec i e andom se ice imes,
and no γ2+γ3 ha would be ob ained wi h in e lea ing seman ics
(and could be hough a fi s glance om a di ec in e p e a ion o
he eachabili y g aph, which ep esen s a comple e sequen ializa ion
o he beha iou o he model).
Locali y o s a es and ac ions cons i u es ano he aspec o adequacy

12 CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
o he modelling o concu en sys ems. I p o ides he possibili y
o p og essi e modelling by using s epwise efinemen s ( op-down) o
modula composi ion (bo om-up modelling).
As in he case o queueing ne wo k models, he g aphical ep esen-
a ion o Pe i ne s is being c ucial o he inc easing in e es o sys ems
designe s in his model. Howe e , dis ibu ed and concu en sys ems
a e complex and difficul o mas e o designe s by na u e. The e o e,
desi able “good p ope ies” mus be o mally defined and he model
mus be alida ed o hese p ope ies. In his sense, quali a i e anal-
ysis o Pe i ne s is impo an be o e going on he implemen a ion. A
wide ange o echniques o checking synch onic (lead,dis ance,places
bounds,places mu ual exclusions...) and ac i i y p ope ies (deadlock-
eeness,li eness,home s a es. . . ) a e easonably known.
Reachabili y analysis, based on he cons uc ion o he s a e space
o he model, p o ides a comple e knowledge o all i s p ope ies i he
ne is bounded (i.e., i he numbe o eachable s a es is fini e). How-
e e , he exponencial empo al and spa ial compu a ional complexi y
o igina ed om he s a e explosion educes he applicabili y o his
enume a ion echnique.
In o de o a oid he s a e explosion, educ ion/ ans o ma ion and
s uc u al echniques ha e been de eloped. The fi s a e based on he
applica ion o local ules o he simplifica ion o ne s, p ese ing some
o he desi able p ope ies. On he o he hand, s uc u al echniques
allow o conclude abou some p ope ies o he model jus om he ne
s uc u e and using ma hema ical ools aken om g aph heo y,linea
algeb a,con ex geome y,o linea p og amming.
Rega ding quan i a i e analysis o Pe i ne s wi h iming in e p e-
a ion, he mos commonly used echnique consis s on he de i a ion o
exac pe o mance measu es om he eachabili y g aph o he model
(i bounded) which is iden ified wi h a Ma ko chain, unde ce ain as-
sump ions on he s ochas ic specifica ion. As in he case o quali a i e
eachabili y analysis, he explosion o he compu a ional complexi y is
he main p oblem in he ac ual use o his echnique o he pe o mance
e alua ion o la ge models.
Al e na i e me hods o he quan i a i e e alua ion o Pe i ne
models ha e been ied ou . As in he case o queueing ne wo ks, ap-
p oxima ion echniques and he compu a ion o bounds cons i u e an
1.2. S ochas ic Pe i ne s 13
op ion ins ead o exac analysis. The s udy o he second one has been
ou choice!
1.2.2 Some e minology
The pu pose o his sec ion is jus o in oduce some no a ions and
e minology o be ex ensi ely used in he sequel. The eade is assumed
o be amilia wi h basic Pe i ne s concep s.
1.2.2.1 Ne s uc u e
A Pe i ne is a 4- uple N=P, T, P e, Pos , whe e
•Pis he se o places (|P|=n),
•Tis he se o ansi ions (|T|=m,P∩T=∅,P∪T=∅),
•P e(Pos ) is he p e- (pos -) incidence unc ion ep esen ing he
inpu (ou pu ) a cs, P e:P×T→IN = {0,1,2,...}(Pos :P×
T→IN).
A Pe i ne can be seen as a bipa i e di ec ed g aph in which places
and ansi ions a e he wo kinds o nodes. Places a e usually d awn
as ci cles while ansi ions a e depic ed as ba s o boxes.
O dina y ne s a e Pe i ne s whose p e and pos incidence unc ions
ake alues in {0,1}. The incidence unc ion o a gi en a c in non-
o dina y ne s is called weigh o mul iplici y.
The p e- and pos -se s o a ansi ion ∈Ta e defined espec-
i ely as • ={p|P e(p, )>0}and •={p|Pos (p, )>0}.
The p e- and pos -se s o a place p∈Pa e defined espec i ely as
•p={ |Pos (p, )>0}and p•={ |P e(p, )>0}.
The incidence ma ix o he ne C=[cij], i=1,...,n,j=1,...,m,
is defined by cij =Pos (pi,
j)−P e(pi,
j). Simila ly he p e- and
pos -incidence ma ices a e defined as PRE =[aij] and POST =[bij],
whe e aij =P e(pi,
j) and bij =Pos (pi,
j).
14 CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
1.2.2.2 Token game
A unc ion M:P→IN (usually ep esen ed in ec o o m) is called
ma king.Ama ked Pe i ne N ,M
0is a Pe i ne Nwi h an ini ial
ma king M0.
A ansi ion ∈Tis enabled a ma king Miff ∀p∈P:M(p)≥
P e(p, ). A ansi ion enabled a Mcan fi e yielding a new ma king
M( eached ma king) defined by M(p)=M(p)−P e(p, )+Pos (p, )
(i is deno ed by M[ M).
A sequence o ansi ions σ= 1 2... nis a fi ing sequence o
N,M
0iff he e exis s a sequence o ma kings such ha M0[ 1M1[ 2
M2...[ nMn. In his case, ma king Mnis said o be eachable om M0
by fi ing σ, and his is deno ed by M0[σMn. Exp esion M[σdeno es
a fi able sequence σ om ma king M.
The unc ion σ:T→IN is he fi ing coun ec o o Pa ikh ec o
[Pa 66] o he fi able sequence σ, i.e., σ[ ] ep esen s he numbe o
occu ences o ∈Tin σ.I M0[σM, hen we can w i e in ec o o m
M=M0+C·σ, which is e e ed o as he linea s a e equa ion o he
ne . A ma king Mis said o be po en ially eachable iff ∃
X≥0 such
ha M=M0+C·
X≥0.
1.2.2.3 Basic p ope ies
The eachabili y se R(N,M
0) is he se o all ma kings eachable om
he ini ial ma king. Deno ing by PR(N,M
0) he se o all po en-
ially eachable ma kings we ha e he ollowing ela ion: R(N,M
0)⊆
PR(N,M
0). L(N,M
0) is he se o all fi ing sequences and hei su -
fixes in N,M
0:L(N,M
0)={σ|M[σwi h M∈R(N,M
0)}.
A place p∈Pis said o be k–bounded iff ∀M∈R(N,M
0), M(p)≤
k. A ma ked ne N,M
0is said o be (ma king) k–bounded iff each
o i s places is k–bounded. A ne Nis s uc u ally bounded iff ∀M0 he
ma ked ne s N ,M
0a e k–bounded o some k∈IN .
Gi en an ini ial ma king, an implici place is one which ne e is he
unique ha es ic s he fi ing o i s ou pu ansi ions. Le Nbe any
ne and Npbe he ne esul ing om adding an implici place p o N.
The e o e, he fi ing sequences in N,M
0and Np,Mp
0a e iden ical.
A ansi ion ∈Tis li e in N,M
0iff ∀M∈R(N,M
0): ∃M∈
R(N,M) such ha Menables . The ma ked ne N,M
0is li e iff all
1.2. S ochas ic Pe i ne s 15
i s ansi ions a e li e (i.e., li eness o he ne gua an ees he possibili y
o an infini e ac i i y o all ansi ions). A ne Nis s uc u ally li e iff
∃M0such ha he ma ked ne N ,M
0is li e. The ma ked ne N,M
0
is deadlock- ee iff ∀M∈R(N,M
0): ∃ ∈Tsuch ha Menables .A
ma ked ne has a o al deadlock iff i is no deadlock- ee.
Aconsis en componen (o T-semiflow ) is a unc ion ( ec o )
X:T→IN such ha X= 0 and C·X=0. Aconse a i e com-
ponen (o P-semiflow ) is a unc ion ( ec o ) Y:P→IN such ha
Y= 0 and YT·C= 0. The suppo o (T- and P-) semiflows is defined
by ||X|| ={ ∈T|X( )>0}and ||Y|| ={p∈P|Y(p)>0}. A (T-
o P-) semiflow Ihas minimal suppo iff he e exis no o he semiflow
Isuch ha ||I|| ⊂ ||I||. A (T- o P-) semiflow is canonical iff he
g ea es common di iso o i s componen s is 1. A (T- o P-) semiflow
is elemen a y iff i is canonical and has minimal suppo .
A ne Nis consis en iff he e exis s a T-semiflow X≥11. A ne
Nis conse a i e iff he e exis s a P-semiflow Y≥11.
M∈R(N,M
0)isahome s a e iff ∀M∈R(N,M
0):M∈
R(N,M). M∈R(N,M
0)isa ansien s a e iff i is no a home
s a e. A ma ked ne is e e sible iff i s ini ial ma king is a home s a e.
1.2.3 On s ochas ic Pe i ne s
In he o iginal defini ion, Pe i ne s did no include he no ion o ime,
and ied o model only he logical beha iou o sys ems by desc ib-
ing he causal ela ions exis ing among e en s. This app oach showed
i s powe in he specifica ion and analysis o concu en sys ems in a
non-in e lea ed way, independen o he concep o ime. Ne e heless
he in oduc ion o iming specifica ion is essen ial i we wan o use
his class o models o an e alua ion o he pe o mance o dis ibu ed
sys ems [TPN85,PNPM87,PNPM89].
1.2.3.1 Timing and fi ing p ocess
Since Pe i ne s a e bipa i e g aphs, his o ically he e ha e been wo
ways o in oducing he concep o ime in hem, namely, associa ing
a ime in e p e a ion (de e minis ic o s ochas ic) wi h ei he places
[Si 78] o ansi ions [Ram74]. Since ansi ions ep esen ac i i ies ha
16 CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
change he s a e (ma king) o he ne , i seems na u al o associa e a
du a ion wi h hese ac i i ies ( ansi ions). The la e has been ou
choice. In o he wo ds, om a queueing heo y pe spec i e, he se ice
s a ions a e ep esen ed by imed ansi ions, and we deno e by si he
a e age se ice ime o ansi ion i.
In he case o imed ansi ion models, wo diffe en fi ing ules ha e
been defined:
1) “ imed fi ing” o ansi ions in h ee phases which changes he
fi ing ule o Pe i ne s in oducing a imed phase in which he
ansi ion is “wo king” a e ha ing emo ed okens om he in-
pu and be o e adding okens o he ou pu places, o a
2) “ imed enabling” ollowed by an a omic fi ing which does no
affec he usual Pe i ne fi ing ule.
These diffe en iming in e p e a ions ha e diffe en implica ions on
he esolu ion o conflic s [AMBB+89]. On he one hand, using imed
ansi ion models wi h h ee phases fi ing we can define a policy o
conflic esolu ion independen o he ime specifica ion bu we canno
model p e-emp ion. On he o he hand, using imed ansi ion models
wi h single phase fi ing we can model p e-emp ion bu we canno de-
fine conflic esolu ion policies independen o he iming specifica ion
( he conflic s a e usually esol ed in his case wi h ace policy, i.e., he
ansi ion which samples he minimum se ice ime is he one whose
fi ing de e mines he change o ma king).
In o de o a oid he coupling be ween esolu ion o conflic s and
du a ion o ac i i ies, we suppose ha ansi ions in conflic a e im-
media e ( hey fi e in ze o ime). Decisions a hese conflic s a e aken
acco ding o ou ing a es associa ed wi h immedia e ansi ions (gen-
e alized s ochas ic Pe i ne s [AMBC84,AMBCC87a]). In his way, p e-
emp ion canno be modelled. In o he wo ds, each subse o ansi ions
{ 1,...,
k}⊂T ha a e in conflic in one o se e al eachable ma k-
ings a e conside ed immedia e, and he cons an s 1,...,
k∈IN +a e
explici ly defined in he ne in e p e a ion in such a way ha when
1,...,
ka e enabled, ansi ion i(i=1,...,k) fi es wi h p obabili y
(o wi h long un a e, in he case o de e minis ic conflic s esolu ion
policy) i/(k
j=1 j). No e ha he ou ing a es a e assumed o be

1.2. S ochas ic Pe i ne s 17
s ic ly posi i e, i.e., all possible ou comes o any conflic ha e a non-
null p obabili y o fi ing. This ac gua an ees a ai beha iou o he
non-au onomous Pe i ne s ha we conside (a ma ked ne is said o be
ai iff all ansi ions ha a e simul aneously enabled infini ely many
imes will fi e infini ely o en).
In summa y, we model se ice s a ions by means o (de e minis ic
o s ochas ic) imed ansi ions, ou ing by means o immedia e an-
si ions in conflic , and bo h kinds o ansi ions, imed and immedia e,
can be used as o k (spli ) nodes and join (synch oniza ion) nodes.
1.2.3.2 Single e sus mul iple se e seman ics
Ano he possible sou ce o con usion in he defini ion o he imed in e -
p e a ion o a Pe i ne model is he concep o deg ee o enabling o a
ansi ion (o e-en ance). In he case o iming associa ed wi h places,
i seems qui e na u al o define an una ailabili y ime which is indepen-
den o he o al numbe o okens al eady p esen in he place, an his
can be in e p e ed as an infini e-se e policy om he poin o iew
o queueing heo y. In he case o ime associa ed wi h ansi ions, i is
less ob ious a-p io i whe he a ansi ion enabled k imes in a ma king
should wo k a condi ional speed 1 o k imes ha i would wo k in he
case i was enabled only once. In he case o s ochas ic Pe i ne s wi h
exponen ially dis ibu ed se ice imes associa ed wi h ansi ions, he
usual implici hypo hesis is o ha e single-se e seman ics (see, e.g.,
[Mol82,FN85a]), and he case o mul iple-se e is handled as a case o
se ice a e dependen on he ma king; his ick canno wo k in he
case o mo e gene al p obabili y dis ibu ions. This is he eason why
people wo king wi h de e minis ic imed ansi ions Pe i ne s p e e
an infini e-se e seman ics (see, e.g., [RP84,HV85,Zub85]). O cou se
an infini e-se e ansi ion can always be cons ained o a “k–se e ”
beha iou by adding one place ha is bo h inpu and ou pu (sel -loop
wi h mul iplici y 1) o ha ansi ion and ma king i wi h k okens.
The e o e, he infini e-se e seman ics appea s o be he mos gene al
one, and o his eason i is adop ed in his wo k.
The maximum numbe o se e s wo king in pa allel a a gi en
ansi ion will be cha ac e ized wi h he enabling bound concep .
18 CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
Defini ion 1.2.1 (Enabling bound) Le N ,M
0be a ma ked Pe i
ne . The enabling bound o a gi en ansi ion o Nis
E( )de
= max{k|∃M∈R(N,M
0): M≥kPRE[ ]}
Since in his wo k we a e in e es ed in he s eady-s a e pe o mance
o a model, one can ask he ques ion how many se e s a e a ailable
in ansi ions in s eady-s a e condi ion. The answe is he defini ion o
he li eness bound concep .
Defini ion 1.2.2 (Li eness bound) Le N,M
0be a ma ked Pe i
ne . The li eness bound o a gi en ansi ion o Nis:
L( )de
= max{k|∀M∈R(N,M
0),∃M∈R(N,M): M≥kPRE[ ]}
The abo e defini ions allow o gene alize he classical concep s o
enabling and li eness o a ansi ion. In pa icula , a ansi ion is
li e i and only i L( )>0, i.e., i he e is a leas one wo king se e
associa ed wi h i in s eady-s a e condi ions. The ollowing is also
ob ious om he defini ions.
P ope y 1.2.1 Le N,M
0be a ma ked Pe i ne , hen o all an-
si ion o N,E( )≥L( ).
A case o s ic inequali y in his p ope y can be in e p e ed as
a gene aliza ion o he concep o non-li eness: he e exis ansi ions
con aining “po en ial se e s” ha a e ne e used in he s eady-s a e;
hese addi ional se e s migh only be used in a ansien phase, so
hey “die” du ing he e olu ion o he model. See, as an example, he
ne in figu e 1.6. Fo ansi ion 1we ha e: E( 1)=2>L( 1)=1.
Since o any e e sible ne (i.e., such ha M0is a home s a e) he
eachabili y g aph (which is a di ec ed labelled g aph wi h he eachable
ma kings as nodes) is s ongly connec ed, he ollowing can be s a ed:
P ope y 1.2.2 Le N,M
0be a e e sible ma ked Pe i ne , hen
o all ansi ion o N,E( )=L( ).
2
p11 2
3
p2
p3
1.2. S ochas ic Pe i ne s 19
Figu e 1.6: A ne wi h enabling bound g ea e han li eness bound o
ansi ion 1.
The defini ion o enabling bound e e s o a beha iou al p ope y
ha depends on he eachabili y g aph o a Pe i ne . Since we a e look-
ing o compu a ional echniques a he s uc u al le el, we can also
in oduce he s uc u al coun e pa o he enabling bound concep .
S uc u al ne heo y has been de eloped om wo complemen a y
poin s o iew: g aph heo y [Bes87] and ma hema ical p og amming
(o mo e specifically linea p og amming and linea algeb a) [SC88].
Le us in oduce ou s uc u al defini ion om he ma hema ical p o-
g amming poin o iew; essen ially in his case he eachabili y condi-
ion is subs i u ed by he (in gene al) weake (linea ) cons ain ha
ma kings sa is y he ne s a e equa ion: M=M0+C·σ, wi h M,σ≥0.
Defini ion 1.2.3 (S uc u al enabling bound) Le Nbe a Pe i
ne . The s uc u al enabling bound o a gi en ansi ion o Nis
SE( )de
=maximize k
subjec o M=M0+C·σ ≥kPRE[ ]
σ ≥0
(LPP1)
No e ha he defini ion o s uc u al enabling bound educes o he
o mula ion o a linea p og amming p oblem [Mu 83].
Now le us ema k he ela ion be ween beha iou al and s uc-
u al enabling bound concep s ha ollows om he implica ion “M∈
R(N,M
0)⇒M=M0+C·σ ∧σ ≥0”.
P ope y 1.2.3 Le N,M
0be a ma ked Pe i ne , hen o all an-
si ion o N,SE( )≥E( ).
20 CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
1.2.3.3 E godici y and measu abili y
In o de o compu e he s eady-s a e pe o mance o a sys em we ha e
o assume ha some kind o “a e age beha iou ” can be es ima ed on
he long un o he sys em we a e s udying. The usual assump ion in
his case is ha he sys em model mus be e godic [Ros83], meaning
ha a he limi when he obse a ion pe iod ends o infini y, he es i-
ma es o a e age alues end (almos su ely) o he heo e ical expec ed
alues o he (usually unknown) p obabili y dis ibu ion unc ions ha
cha ac e ize he pe o mance indexes o in e es .
This assump ion is e y s ong and difficul o e i y in gene al;
mo eo e , i c ea es p oblems when we wan o include he de e min-
is ic case as a special case o a s ochas ic model, since he exis ence o
he heo e ical limi ing expec ed alue can be hampe ed by he pe i-
odici y o he model. Thus we in oduce he concep o weak e godici y
ha allows he es ima ion o long un pe o mance also in he case o
de e minis ic models.
Defini ion 1.2.4 (Weak and s ong e godici ies)
1. A (no necessa ily s ochas ic) p ocess Zτ, whe e τ≥0 ep esen s
he ime, is said o be weakly e godic (o measu able in long un)
iff he ollowing limi exis s:
lim
τ→∞
1
ττ
0Zudu < ∞(1.7)
2. A s ochas ic p ocess Zτ, whe e τ≥0 ep esen s he ime, is said
o be (s ongly) e godic iff he ollowing condi ion holds:
lim
τ→∞
1
ττ
0Zudu = lim
τ→∞ E[Zτ]<∞(a.s.) (1.8)
Fo s ochas ic Pe i ne s, weak e godici y o he ma king and he
fi ing p ocesses can be defined in he ollowing e ms:
Defini ion 1.2.5 (Weak e godici y o ma king and fi ing) The
ma king p ocess Mτ, whe e τ≥0 ep esen s he ime, o a s ochas ic
ma ked ne is weakly e godic iff he ollowing limi exis s:
Mde
= lim
τ→∞
1
ττ
0Mudu < ∞(1.9)
q
s
e
q1
1
q2
q3
2
3
e1
s2
s3
12
13
1.3. Mapping be ween synch onized QNs and s ochas ic PNs 27
Figu e 1.12: A Pe i ne ep esen a ion o a monoclass single-se e
queue.
Figu e 1.13: A Pe i ne ep esen a ion o a queueing ne wo k.

28 CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
ansi ions model he se ice imes.
On he o he hand, s ochas ic ne s can assume o ms much mo e
complex han he one illus a ed in he example o figu e 1.13. Fig-
u e 1.14 illus a es a mo e gene al s ochas ic Pe i ne ha canno be
mapped on o a p oduc o m queueing ne wo k. In ac , his ne can
be mapped on an ex ended queueing ne wo k [SMK82], in which such
cons uc s as o k, join, and passi e esou ces a e used o map he effec
o he pai s o ansi ions 2– 7and 9– 10, espec i ely. These exam-
ples show how, using a Pe i ne o malism, ex ensions o p oduc o m
queueing ne wo ks a e ep esen ed wi h an analogous le el o s uc u al
complexi y o BCMP ne wo ks.
In sec ion 1.1, ex ended queueing ne wo k models we e p esen ed
o he modelling o a mul ip og amming memo y limi ed sys em (fig-
u e 1.2) and a o k/join mul i asking p ocess (figu e 1.3). The co -
esponding Pe i ne models a e depic ed in figu es 1.15 and 1.16,
espec i ely.
The eade is no iced ha “uncle e ” use o synch oniza ions in
queueing ne wo ks can lead o pa hological cases as unbounded numbe
o cus ome s o o al deadlock (see figu e 1.17), ha need o be ca e ully
s udied.
Finally, le us ema k ha s ochas ic Pe i ne s wi h weigh ed a cs
(i.e., non-o dina y ne s) can be used o he modelling o bulk a i als
and bulk se ices [Kle75], wi h de e minis ic size o ba ches (gi en by
he weigh s o a cs). As an example, ansi ion 3o Pe i ne in fig-
u e 1.6 is a bulk se ice sys em which accep s a ba ch o exac ly wo
okens (cus ome s) om he place p3, and se es hem collec i ely.
1.4 Analy ical echniques o synch o-
nized queueing ne wo ks
One o he main p oblems in he ac ual use o imed and s ochas ic
Pe i ne models o he pe o mance e alua ion o la ge sys ems is he
explosion o he compu a ional complexi y o he analysis algo i hms.
In gene al, exac pe o mance esul s a e ob ained om he nume ical
solu ion o a con inuous ime Ma ko chain [BT81,Mol81,FN85b]. This
exac compu a ion is only possible o bounded ne s (fini e s a e space),
(a) S ochas ic Pe i ne ep esen a ion.
(b) Ex ended queueing ne wo k ep esen a ion.
FJ
R
AF
1
R
2
A
J
C=3
C
1
2
3
4
5
6 7
8
9 10
1.4. Analy ical echniques o synch onized QNs 29
Figu e 1.14: A mo e gene al s ochas ic ne and he co esponding syn-
ch onized queueing ne wo k.
C
M
e minals memo y queue p ocesso
I/O de ices
memo y
pa i ions
30 CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
Figu e 1.15: Pe i ne model o a mul ip og amming memo y limi ed
sys em.
Figu e 1.16: Pe i ne model o a o k/join mul i asking p ocess.
F
(a) A o al deadlock will be eached
soone o la e , e en o q =1/2.
(b) Any in ini e beha iou will lead o
an in ini e numbe o cus ome s.
JF
FJ
1-q
q
1.4. Analy ical echniques o synch onized QNs 31
Figu e 1.17: Pa hological cases o synch onized queueing ne wo ks.
and unde exponen ial assump ion o he se ice ime o ansi ions.
And he wo s o i is ha he dimension o he s a e space o he
embedded Ma ko chain g ows exponen ially wi h he ne size.
The same p oblem a ose in he amewo k o queueing ne wo ks
be o e he wo k o J. Jackson, and i was sol ed by means o he in o-
duc ion o p oduc o m equa ions [Jac63,GN67,BCMP75], and efficien
algo i hms o hei solu ion [Buz73,RK75,RL80,BB80]. Un o una ely,
he gene aliza ion o hese esul s o mo e complex s ochas ic models
wi h synch oniza ion ea u es seems o be e y difficul , and a e y ew
numbe o esul s ha e been al eady published.
Rela ed wi h open ne wo ks, a ma ix p oduc o m solu ion is
known only o s ochas ic Pe i ne s wi h a mos one place unbounded
[FN86]. In [FN89a], G. Flo in and S. Na kin p esen ed he fi s gene al
p oduc o m exp esion in ma ix o m o closed (i.e., bounded) o di-
na y s ochas ic Pe i ne s wi h s ongly connec ed eachabili y g aph.
The g ea diffe ence be ween scala (Go don-Newell esul o closed
queueing ne wo ks) and ma ix p oduc o ms appea s in nume ical
compu a ion. Sol ing synch onized queueing ne wo ks implies much
32 CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
mo e complex algo i hms han classical ones. The p oblem o compu -
ing he no maliza ion cons an in he scala p oduc o m solu ion is
eplaced by he compu a ion o a cons an ec o ob ained sol ing a sys-
em o linea equa ions, which is ill-condi ioned. This is he eason why
he pape o Flo in and Na kin can be conside ed mainly o heo e ical
significance. O he wo ks dealing wi h his p oblem [AMBCD86,LR87]
conside only e y es ic i e subclasses o Pe i ne s. The e o e, effi-
cien compu a ional me hods a e s ill needed.
App oxima ion echniques ha e been de eloped in he amewo k o
non-p oduc o m queueing ne wo ks o o e coming he p ac ical lim-
i a ions o exac solu ions. The “flow equi alen ” se e decomposi ion
me hod is p obably he mos used in p ac ice [La 89]. In his me hod,
a subne wo k is eplaced by a se e wi h exponen ially dis ibu ed
se ice imes and queue leng h dependen se ice a es. The a es a e
ob ained by sol ing he h oughpu o he isola ed subne wo k once o
each possible alue o numbe o cus ome s in he subne wo k. The
agg ega ed sys em consis ing o his flow equi alen se e and he es
o he o iginal ne wo k is hen sol ed.
Two diffe en heo e ical jus ifica ions o he fi ness o he flow
equi alen se e me hod can be gi en. The fi s is ha i yields exac
esul s o single chain p oduc o m ne wo ks [CHW75]. This esul
is called No on’s heo em o p oduc o m queueing ne wo ks due o
i s analogy wi h No on’s heo em o elec ical ci cui s (in which a
subsys em is eplaced by a cu en sou ce and pa allel esis ance ha
a e equi alen o he o iginal subsys em in e ms o hei effec on
he es o he sys em). This exac esul o p oduc o m queueing
ne wo ks sugges s ha he flow equi alen se e me hod may yield
ai ly accu a e app oxima ions o ne wo ks ha a e “almos p oduc
o m”.
The second jus ifica ion o he use o his me hod was pe o med
by P. Cou ois [Cou77] wi hin he amewo k o he compu a ion o
he s eady-s a e solu ion o la ge Ma ko chains in which s a es a e
agg ega ed in o mac os a es o educe he compu a ional complexi y
o he solu ion (nea ly o comple ely decomposable sys ems).
P ac ical expe ience shows ha using decomposi ion echniques o
he solu ion o non-p oduc o m ne wo ks made up o subsys ems ha ,
aken in isola ion, sa is y he p oduc o m condi ions o en yields qui e

1.4. Pe o mance bounds o s ochas ic PNs 33
accep able esul s [AMBC86].
A complemen a y app oach o he app oxima ion echniques o
he analysis o queueing ne wo ks is he compu a ion o bounds. Pe -
o mance bounds a e use ul in he p elimina y phases o he design o
a sys em, in which many pa ame e s a e no known accu a ely. Se -
e al al e na i es o hose pa ame e s should be quickly e alua ed, and
ejec ed hose ha a e clea ly bad. Exac (and e en app oxima e) solu-
ions would be compu a ionally e y expensi e. Bounds become use ul
in hese ins ances since hey usually equi e much less compu a ion
effo .
A la ge numbe o bounding echniques ha e been p oposed o he
pe o mance measu es o queueing ne wo ks. The fi s amily is ha o
asymp o ic bound analysis [Kle76,DB78]. Asymp o ic bounds a e ob-
ained by conside ing wo ex eme si ua ions: (1) no queueing akes
place a any node, and (2) a leas one s a ion is sa u a ed. These
bounds do no equi e he p oduc o m p ope y o hold and hei
compu a ion is e y as , bu hey a e no accu a e in gene al. The
es o bounds ha ha e been in oduced a e igh e bu do equi e
he p oduc o m assump ion. This is he case o balanced job bounds
[ZSEG82,K i84], which a e based on he mean alue heo em [RL80].
Finally, se e al schemes o he cons uc ion o hie a chies o bounds
ha e been de eloped ha gua an ee any le el o accu acy (including he
exac solu ion), by in es ing he necessa y compu a ional effo : pe -
o mance bound hie a chies [ES83,ES86], succesi ely imp o ing bounds
[S i87], gene alized quick bounds [Su 84]. All hese echniques a e de-
i ed om mean alue heo em, hus hey a e alid only o p oduc
o m ne wo ks.
1.5 An o e iew o pe o mance bounds
o s ochas ic Pe i ne s
Many wo ks exis conce ning he pe o mance e alua ion in he case
o de e minis ically imed ne s, mainly o s ongly connec ed ma ked
g aphs [Ram74,Si 78,RH80,Mag84,Mu 85]. We assume all hese esul s,
which can be iden ified as a pa icula case (in ac an “ex eme” case)
o he gene al s ochas ic iming, and we e o mula e hem in a gene al
34 CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
o m which allows efficien compu a ion me hods. Ex ensions o non-
o dina y ne s ha e been p esen ed in he case o de e minis ic iming
[Hil88]. Ou wo k conside s also hese ne s in a unified o mula ion.
In he amewo k o s ochas ic Pe i ne s, only a ew wo ks exis e-
la ed wi h he compu a ion o pe o mance bounds [Mol85,BG85,IA89],
and all o hem a e alid jus o es ic i e assump ions on he ne s.
M. Molloy [Mol85] no ed ha he a e age oken flows in an o dina y
Ma ko ian ne wo k a s eady-s a e a e conse ed. The e o e, a se ies
o flow balance equa ions can be w i en. Token flows a e conse ed in
places so he sum o all flows in o a place equals he sum o all flows ou
o he place. On he o he hand, all oken flows on he inpu and ou pu
a cs o a ansi ion a e equal. These equa ions de e mine he a e age
oken flows in he cycles o he ne o wi hin a cons an . This cons an
canno be de e mined wi hou Ma ko ian analysis a he eachabili y
g aph le el. Howe e , limi flows when he numbe o okens ends
o infini y can be compu ed. In o de o do ha , bo leneck ansi-
ions mus be fi s loca ed. Then, he ac ual flow h ough a bo leneck
ansi ion is (unde sa u a ion condi ions) equal o i s po en ial fi ing
a e.
I is well-known ha he conse a ion o flows p esen ed by M. Mol-
loy is no only alid o Ma ko ian ne s. In ac , some o mos impo an
laws o queueing heo y hold unde e y gene al assump ions. These
gene al si ua ions a e conside ed in ou wo k, and some undamen al
laws aken om queueing heo y (such as Li le’s o mula) a e applied
o s ochas ic Pe i ne models.
S. B uell and S. Ghan a [BG85] de eloped algo i hms o compu -
ing uppe and lowe bounds o he h oughpu o a es ic ed subclass
o gene alized s ochas ic Pe i ne s (wi h immedia e and exponen ially
imed ansi ions). The conside ed ne s include con ol okens o model
a physical es ic ion, such as semapho es, which is no a design pa am-
e e . The es o okens o such ne s, g ouped in classes, co espond o
he no ion o a job o cus ome in a monoclass queueing ne wo k, and
i s numbe is ea ed as a pa ame e o he ne . The uppe and lowe
bounds on h oughpu a e compu ed hie a chically es ima ing maxi-
mum and minimum ime o he pa h ollowed by each class o jobs.
Un o una ely, he abo e ci ed a icle [BG85], which is conside ed
by he au ho s as a “p elimina y wo k”, suffe s om an excessi e in o -
1.5. Pe o mance bounds o s ochas ic PNs 35
mal s yle ha makes con using bo h he cha ac e iza ion o he consid-
e ed ne subclasses and he compu a ion algo i hms. Howe e , in hose
cases in which we ha e been able o applied he echniques p esen ed
in [BG85], he ob ained esul s ag ee wi h he ones ha we ge using
he algo i hms we p esen in his wo k.
In he pape o S. Islam and H. Amma [IA89], me hods o com-
pu e uppe and lowe bounds o he s eady-s a e oken p obabili ies
o a subclass o gene alized s ochas ic Pe i ne s a e p esen ed. The
conside ed ne s a e obliged o admi a ime scale decomposi ion. This
means ha he ansi ions o he ne a e supposed o be di ided in o
wo classes: slow and as ansi ions, wi h se e al o de s o magni ude
o diffe ence in he du a ion o ac i i ies. Mo eo e , he subne s ob-
ained a e emo ing all slow ansi ions wi h hei inpu and ou pu
a cs mus be conse a i e and admi a e e sible ini ial ma king. The
compu a ion is based on nea -comple ely decomposabili y o Ma ko
chains.
Ou app oach is diffe en , and complemen a y, om he one p e-
sen ed in [IA89]. One objec i e o his ex is o p esen algo i hms o
he compu a ion o bounds o s ochas ic Pe i ne s o a bi a y mean
alues o se ice imes o ansi ions and, mo eo e , o a bi a y dis-
ibu ion unc ions o he iming. This main objec i e is a acked in an
unified amewo k conside ing bo h quali a i e and quan i a i e p op-
e ies o s ochas ic Pe i ne s, and laying special emphasis on s uc u e
heo y o ne s. The compu a ion o bo h he uppe and lowe bounds
is based on an efficien calcula ion o he isi a ios o ansi ions,a
concep aken om classical queueing heo y. These isi a ios, o-
ge he wi h he a e age se ice ime o ansi ions, he ne s uc u e,
and he ini ial ma king, a e used o he de i a ion o p ope linea p o-
g amming p oblems whose op imum solu ions a e he desi ed bounds.
In he nex chap e , we ocus on he compu abili y o isi a ios om
diffe en ne pa ame e s, such as he ne s uc u e and he s ochas ic
in e p e a ion. Ne subclasses o which his compu a ion is possible
in polynomial ime a e especially conside ed ( hei cha ac e iza ion, in-
clusion ela ions. . . ), making emphasis on hose quali a i e p ope ies
ha a e in e es ing om a pe o mance poin o iew.
36 CHAPTER 1. Synch onized queueing ne wo ks and Pe i ne s
2.1. FRT-ne s and subclasses 43
1. Xa=Xb,
2. ∃P⊂Psuch ha XaP
∧Xb,o
3. ∃X1,...,X
kT-semiflows o Nand P1,...,P
k+1 ⊂P,k≥1,
such ha Xa
P1
∧X1
P2
∧...Pk
∧Xk
Pk+1
∧Xb.
F om he abo e defini ion he nex p ope y i ially ollows:
P ope y 2.1.1 FR is an equi alence ela ion on he se o T-semi-
flows o a ne .
The in oduc ion o his equi alence ela ion on he se o T-semi-
flows induces a pa i ion in o equi alence classes. FRT-ne s a e defined
as ollows:
Defini ion 2.1.3 (FRT-ne s) We say ha a Pe i ne Nis a ne
wi h eely ela ed T-semiflows (FRT-ne , o sho ) iff he in oduc ion
o he eely ela ion on he se o i s T-semiflows induces only one
equi alence class.
No e ha FRT-ne s a e necessa ily connec ed. The e o e, in wha
ollows, unless o he wise explici ly s a ed, we conside only connec ed
ne s.
As an example, le us conside he ne depic ed in figu e 2.3. I is
a li e and s uc u ally bounded ne . I s minimal T-semiflows a e:
X1=(1,0,0,0,0,0,1,0,0,0,1,0,1,0)T
X2=(0,1,1,0,0,0,0,1,0,0,0,0,1,0)T
X3=(0,0,0,1,1,0,0,0,1,0,0,0,0,1)T
X4=(0,0,0,0,0,1,0,0,0,1,0,1,0,1)T
(2.5)
Then, he ne is an FRT-ne because:
X1
{p1}
∧X2
{p2}
∧X3
{p3}
∧X4(2.6)

p1
p5
p3
p4
p2
1 2 3 4
p6p7p8p9
p10
p11
p12
p13 p14
5 6
7 8 9 10
11 12
13 14
44 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
Figu e 2.3: A li e and s uc u ally bounded FRT-ne .
2.1.1.2 Algeb aic cha ac e iza ion
F om he defini ion o FRT-ne s, i may appea s ha a di ec checking
o he pe enence o a gi en ne o his ne subclass is no a polynomial
p oblem on he ne size. This is because he numbe o T-semiflows o a
ne can g ow exponen ially wi h he numbe o places and ansi ions.
Howe e , i s uc u al li eness and s uc u al boundedness a e assumed,
a nice cha ac e iza ion o he FRT-ne s subclass can be ob ained and
checked in polynomial ime. Be o e he p esen a ion o ha esul , we
in oduce a second equi alence ela ion, now on he se o ansi ions
o he ne .
Defini ion 2.1.4 (Equali y conflic ela ion) [CCS90d] Two an-
si ions aand ba e said o be in equali y conflic ela ion, deno ed by
( a,
b)∈ECR,iffPRE[ a]=PRE[ b].
Since he equali y conflic ela ion is based on he equali y o ec-
o s, he nex p ope y ollows:
2.1. FRT-ne s and subclasses 45
P ope y 2.1.2 ECR is an equi alence ela ion on he se o ansi-
ions.
Each equi alence class will be called equali y conflic se , and de-
no ed as ECS. Le Dbe an ECS, he numbe δD=|D|−1 is called
numbe o non- edundan ee conflic s o D. The eason o he name
lies on he ac ha δDis exac ly he numbe o independen ela ions
among he h oughpu o ansi ions belonging o D ha can be de-
i ed om he ou ing a es defining he esolu ion o he conflic . The
numbe o non- edundan ee conflic s o a ne , deno ed as δ, is he
sum o all δDco esponding o he ECSs o he ne : δ=D∈T/ECR δD.
Theo em 2.1.1 Le Nbe a s uc u ally li e and s uc u ally bounded
ne . Then Nis an FRT-ne i and only i ank(C)=m−δ−1,
whe e Cis he incidence ma ix o N,m=|T|, and δis he numbe
o non- edundan ee conflic s o he ne .
Be o e gi ing he p oo o he abo e heo em, le us s a e an impo -
an conclusion.
Co olla y 2.1.1 I Nis s uc u ally li e and s uc u ally bounded, de-
ciding i Nbelongs o he class o FRT-ne s is polynomial on he ne
size.
S uc u al boundedness o a ne can be always be checked in poly-
nomial ime (iff ∃Y≥11 such ha YT·C≤0 [Mu 89]). Un o una ely,
s uc u al li eness o FRT-ne s canno be decided (so a ) efficien ly.
Ne e heless, a necessa y condi ion o a ne o be s uc u ally li e
s uc u ally bounded and FRT-ne can be checked in polynomial ime,
looking o he consis ency, conse a i eness, and ank condi ion o e
he incidence ma ix, because s uc u al li eness and s uc u al bound-
edness implies consis ency and conse a i eness (see, e.g., [Sil85]).
In o de o p o e heo em 2.1.1 we p e iously p esen some lem-
ma as. The fi s one conce ns a educ ion o he non-de e minism a
equali y conflic s, p ese ing he li eness p ope y, by means o he
me ging o a special class o ne s: local schedule s.
46 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
Figu e 2.4: In oduc ion o a local schedule a an equali y conflic se .
Defini ion 2.1.5 (Local schedule ) [CCS90d] Le D={ i|i=
1,...,δ
D+1}be an ECS o he ne N. A local schedule
o Dis a ne LSDdefined as (see figu e 2.4): LSD=
PLSD,T
LSD,P e
LSD, Pos LSD, such ha TLSD∩T=D,T•
LSD∪
•TLSD=PLSD, and PLSD∩P=∅.
Lemma 2.1.1 Le Nbe a ne and Dan ECS o N.Le LSDbe a
local schedule o D.I Nand LSDa e s uc u ally li e in isola ion,
hen he ne NLSDob ained by me ging he common ansi ions o N
and LSDis s uc u ally li e.
P oo . Le M0and M0LSDbe ini ial ma kings making li e he ne s N
and LSD, espec i ely. Le MLSD
0be an ini ial ma king o NLSDsuch
ha i s p ojec ion on Pis M0and i s p ojec ion on PLSDis M0LSD.
Le MLSD∈R(NLSD,MLSD
0) and be a ansi ion o N. We p o e
ha he e exis s a fi ing sequence, σLSD,inN LSD,MLSD ha yields
o a ma king enabling (i.e., he ne NLSDis li e unde MLSD
0).
The p ojec ion o MLSDon Pis a ma king M∈R(N,M
0) om
which he e exis s a leas one σ∈L(N,M), yielding o a ma king M
ha enables (because he ne Nis li e). F om his ac , h ee cases
a ise:
a) I σdoes no con ain any ansi ion belonging o D hen i is also
fi able in he ne NLSD.
b) I σcon ains one ansi ion a∈D, ha is σ=σ0 aσa, hen he e
exis δD+ 1 fi able sequences om Mo he o m σ0 iσi, i∈D,
(a)
(b)
(c)
p1
p2p3
p6
p7
a b
c d
p1
a b
p2p3
p6
p7
c d
a b
p4
p5
p4
p5
2.1. FRT-ne s and subclasses 47
Figu e 2.5: Coun e -example o he con e se o lemma 2.1.1.
i=1,...,δ
D+1, ha allow o each a ma king enabling . This is
because Nis li e and M[σ0MD;∀ i∈D,MD[ iMi∈R(N,M
0)
and ∀i=1,...,δ
D+1, Mi[σiM
i[ . The e o e, a leas one o
he sequences σ0 iσican be fi ed in NLSD:σ0and σia e fi able
acco ding o he abo e case (a); a leas one i∈Dis fi able
because LSDis a li e ne (e en ually, a e he fi ing o some
in e nal ansi ions o he local schedule in o de o enable i).
c) I σcon ains mo e han one ansi ion o D, we can find a fi able
sequence in N ha is fi able in NLSD. This can be done by
applying epea edly he abo e case (b).
Li eness o ansi ions belonging o LSDcan be p o ed wi h simila
a gumen s. The e o e, he ne NLSDis li e unde MLSD
0and hen
s uc u ally li e.
Un o una ely, he con e se o lemma 2.1.1 is no ue. Le us con-
side , o ins ance, he s uc u ally non-li e ne depic ed in figu e 2.5.a.
The ne o figu e 2.5.b is a s uc u ally li e local schedule o ansi-
ions aand b. The composi ion o he wo ne s is he ne o figu e 2.5.c
ha now is s uc u ally li e.
48 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
In he sequel, we conside a simple class o local schedule s called
egula ion ci cui s. These ne s a e used as a ool o p o e he heo-
em 2.1.1. Ne e heless, hey a e no he unique local schedule s ha
can be used o ha pu pose.
Defini ion 2.1.6 (Regula ion ci cui ) [CCS90d] Le aand bbe
wo ansi ions o Nin equali y conflic ela ion. A egula ion ci cui
o aand bis a ne ab =P ab ,T
ab ,P e
ab , Pos ab , whe e P ab =
{pab,p
ba},T ab ={ a,
b},•pab ={ a},p•
ab ={ b},PRE ab [pab,
b]=
POST ab [pab,
a]=1,•pba ={ b},p•
ba ={ a}, and PRE ab [pba,
a]=
POST ab [pba,
b]=1.
As an example, he local schedule depic ed in figu e 2.5 is a egula-
ion ci cui o aand b. The composi ion o Nand ab (by me ging he
common ansi ions aand b) will be deno ed as N ab . The incidence
ma ix o N ab will be deno ed as C ab .
Le Nbe a ne and D={ i|i=1,...,δ
D+1}be an ECS. The
ne ob ained om Nby adding a egula ion ci cui pe each pai o
ansi ions k,
k+1 ∈D,k =1,...,δ
D, will be deno ed as NRD, and i s
co esponding incidence ma ix as CRD. The ne ob ained by adding
egula ion ci cui s o all ECSs as abo e will be deno ed as NR, and
i s co esponding incidence ma ix as CR.
The ollowing lemma as p esen some p ope ies o NRDde i ed
om he co esponding p ope ies o N.
Lemma 2.1.2 Le Nbe a ne and D={ i|i=1,...,δ
D+1}be an
ECS. I Nis s uc u ally li e and s uc u ally bounded hen NRDis
s uc u ally li e and s uc u ally bounded.
P oo . The se o egula ion ci cui s added o Nis a local schedule o
D. This local schedule is s uc u ally li e in isola ion ( his is ob ious,
pu ing enough okens a each o he egula ion ci cui s). The ne
Nis also s uc u ally li e and hen, by lemma 2.1.1, he ne NRDis
s uc u ally li e.
All places o Na e s uc u ally bounded. Taking in o accoun he
defini ions o p k k+1 and p k+1 ki is easy o see ha CRD[p k k+1 ]+
CRD[p k+1 k] = 0 (i.e., he sum o he ows in he incidence ma ix
co esponding o hese places is ze o). The e o e all new places added o

2.1. FRT-ne s and subclasses 49
Na e also s uc u ally bounded and hen NRDis s uc u ally bounded.
Lemma 2.1.3 Le D={ i|i=1,...,δ
D+1}be an ECS. I Nis
s uc u ally li e and s uc u ally bounded hen
min{m−1,n+2δD−1}≥ ank(CRD)= ank(C)+δD(2.7)
P oo . NRDis s uc u ally li e and s uc u ally bounded
(lemma 2.1.3), hus conse a i e and consis en [Sil85]. The e o e,
ank(CRD)≤min{mRD−1,n
RD−1}, whe e mRD=|TRD|=|T|=m
and nRD=|PRD|=|P|+|P 12 |+···+|P kk+1 |+···+|P δD−1δD|=n+2δD.
So, we ob ain: ank(CRD)≤min{m−1,n+2δD−1}.
Le Np 2 1be a ne ob ained om Nby adding he place p 2 1be-
longing o he egula ion ci cui 1,2.Np 2 1is non-conse a i e be-
cause o all ma king ha enables he ansi ions o Dwe can de-
cide o fi e always he ansi ion 2(i.e., he place p 2 1is s uc u ally
unbounded). Then we can conclude ha he e is no a ec o Y
such ha YT·C=Cp 2 1[p 2 1] (see p oposi ion 2.8 in [CCS90d])
(i.e., he ow ec o Cp 2 1[p 2 1] is linea ly independen wi h espec
o he ow ec o s o he incidence ma ix o he ne N). The e-
o e, ank(Cp 2 1)= ank(C) + 1. I we add he place p 1 2 o he
ne Np 2 1we ob ain he ne N 1,2. This las ne has he same ank
ha he ne Np 2 1because C 1,2[p 2 1]=−C 1,2[p 1 2]. The e o e,
ank(C 1,2)= ank(C)+1.
Le NRk−1be he ne ob ained om Nby adding he egula ion
ci cui s 1,2,...,
k−1,k.NRk−1 e ifies ank(CRk−1)= ank(C)+k−1.
We p o e now ha i we add he egula ion ci cui k,k+1 o he ne
NRk−1 hen ank(CRk)= ank(CRk−1)+1.
We add he place p k+1 kbelonging o he egula ion ci cui k,k+1
o he ne NRk−1. This place is unbounded because o all ma king
ha enables some ansi ion o he se { 1,...,
k}, k+1 is also enabled
a his ma king and hen we can decide o fi e always he ansi ion
k+1. Then he ow ec o CRk[p k+1 k] is linea ly independen wi h
espec o he ow ec o s o he incidence ma ix o he ne NRk−1(by
p oposi ion 2.8 in [CCS90d]). The e o e, ank(CRk)= ank(CRk−1)+1
(because CRk[p k+1 k]=−CRk[p k k+1 ]).
50 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
The numbe o added egula ion ci cui s is δD, hence ank(CRD)=
ank(C)+δD.
Lemma 2.1.4 Le Nbe a s uc u ally li e and s uc u ally bounded
ne . Then ank(C)≤m−δ−1, whe e Cis he incidence ma ix o
N,m=|T|, and δis he numbe o non- edundan ee conflic s o he
ne .
P oo . Nis conse a i e and consis en [Sil85]. I we add a local
schedule pe each ECS o he ne , we ob ain a ne deno ed NR ha
sa isfies: min{m−1,n+2δ−1}≥ ank(CR)= ank(C)+δ. Then,
ank(C)≤min{m−δ−1,n+δ−1}. Taking in o accoun ha he
ne Nis conse a i e and consis en , we also ha e ha ank(C)≤
min{m−1,n−1}. The e o e, combining he wo abo e uppe bounds
o ank(C), we ob ain: ank(C)≤min{m−δ−1,n−1}. Bu , N
being conse a i e, ank(C)≤n−1 and he lemma ollows.
P oo o heo em 2.1.1. The ank equali y condi ion holds iff NR
has a unique minimal T-semiflow. So le us p o e his condi ion.
The numbe o minimal T-semiflows o NRis g ea e han o equal
o 1 because his ne is consis en .
We compu e T-semiflows, X≥0 and C·X= 0, applying he algo-
i hm p esen ed in [CS89b] o he ne NR. To do so, we elimina e fi s
he places p i i+1 ha connec wo ansi ions in equali y conflic ela-
ion (ob iously, i we elimina e p i i+1 we also elimina e p i+1 ibecause
CR[p i i+1 ]=−CR[p i+1 i]). The elimina ion o p i i+1 gene a es a unique
new column ha is a linea combina ion o he columns co esponding
o iand i+1. In o de o elimina e p i+1 i+2 we gene a e again a unique
column ha is a linea combina ion o he abo e added column and
he column o i+2. I we epea his p ocedu e o all places p i i+1 be-
longing o an ECS we ob ain a unique new column in which all en ies
co esponding o places o he local schedule a e ze o. The non-null
en ies o his ow a e •ECS ∪ECS•. Applying his p ocedu e o all
ECS o he ne we ob ain a ma ix in which he e is a new column pe
ECS and all columns in he o iginal ne co esponding o ansi ions
ha do no belong o any ECS. This ma ix can be in e p e ed as he
incidence ma ix o a new ne wi h a mos one minimal T-semiflow iff
he o iginal ne is an FRT-ne . This is because, i he o iginal ne was
2.1. FRT-ne s and subclasses 51
an FRT-ne , all i s T-semiflows would be eely ela ed (by defini ion
o FRT-ne ), hus eely connec ed by pai s. And his occu s iff a e
he applica ion o he abo e p ocedu e (i.e., a e he addi ion o he
egula ion ci cui s) each pai o o iginally eely connec ed T-semiflows
cons i u e a unique T-semiflow.
The e o e, applying he ank o mula o lemma 2.1.3 wi h
ank(CR)=m−1 we ob ain: ank(C)=m−δ−1.
2.1.1.3 Quali a i e p ope ies
The nex esul gi es a me hod o he compu a ion o he ec o o
isi a ios o ansi ions o a s uc u ally li e and s uc u ally bounded
FRT-ne (p o ided li eness), om he knowledge o he ne s uc u e
and he ou ing a es a equali y conflic se s.
Theo em 2.1.2 Le Nbe a s uc u ally li e and s uc u ally bounded
FRT-ne . Le Cbe he incidence ma ix o N, and R he ma ix (wi h δ
independen ows, whe e δis he numbe o non- edundan ee conflic s
o N) ha defines he ela i e a es o ansi ions in equali y conflic
ela ion (i.e., he ou ing a he equali y conflic se s). Then, he ec o
o isi a ios  (j)no malized, o ins ance, o ansi ion jcan be
compu ed om Cand Rsol ing he ollowing linea sys em o equa ions:
C
R· (j)=0,
(j)
j=1 (2.8)
(No e ha his compu a ion only makes sense when infini e beha iou is
possible o he ne om a gi en ini ial ma king, in o he wo ds, when
he ne is deadlock- ee.)
P oo . We only ha e o check ha he abo e sys em has a unique
solu ion. By heo em 2.1.1, he numbe o independen ows o ma ix
Cis m−δ−1. The e o e, he m−δ−1 independen condi ions gi en
by C· (j)= 0 plus he δindependen condi ions gi en by R· (j)=0
plus he no maliza ion condi ion  (j)( j) = 1 a e enough o de e mine
exac ly he mcomponen s o he ec o  (j).
52 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
F om he abo e heo em, as we announced p e iously, o s uc-
u ally li e and s uc u ally bounded FRT-ne s we ha e:
 (j)=ϕ(N,R)(2.9)
and he nex complexi y esul ollows:
Co olla y 2.1.2 The compu a ion o he ec o o isi a ios o an-
si ions o a s uc u ally li e and s uc u ally bounded FRT-ne is poly-
nomial on he ne size.
As an example, le us conside again he ne depic ed in figu e 2.3.
The ec o o isi a ios mus be a igh annulle o he incidence
ma ix, hence a linea combina ion o a basis o T-semiflows:
 (1) =
4

i=1
αiXi(2.10)
whe e Xi,i=1,...,4, a e he minimal T-semiflows (2.5) o he ne .
I 1, 2a e he ou ing a es o 1, 2in he conflic a p1; 3, 4 he
ou ing a es o 3, 4in he conflic a p2; and 5, 6 he ou ing a es
o 5, 6in he conflic a p3, hen  (1) mus sa is y:
2 (1)
1= 1 (1)
2
4 (1)
3= 3 (1)
4
6 (1)
5= 5 (1)
6
(2.11)
And oge he wi h he no maliza ion equi emen :
(1)
1=1 (2.12)
he ou pa ame e s αi,i=1,...,4, can be de e mined.
Ano he in e es ing quali a i e p ope y ollows om heo em 2.1.2,
ha does no hold o gene al ne s:
P ope y 2.1.3 Le Nbe a s uc u ally li e and s uc u ally bounded
FRT-ne . Then Nis li e i and only i i is deadlock- ee.
2.1. FRT-ne s and subclasses 59
X2=X+kX, aking k>0 la ge enough, and his is agains he
hypo hesis o mono-T-semiflow.
F om p e ious heo em, he nex s a emen ollows:
Co olla y 2.1.3 I Nis consis en , deciding i Nbelongs o he class
o mono-T-semiflow ne s is polynomial on he ne size.
Now, we p esen an efficien me hod o he compu a ion o he ec-
o o isi a ios o ansi ions o a s uc u ally li e and s uc u ally
bounded mono-T-semiflow ne (p o ided li eness), om he ne s uc-
u e. I ollows om heo ems 2.1.2 and 2.1.4.
Theo em 2.1.5 Le Nbe a s uc u ally li e and s uc u ally bounded
mono-T-semiflow ne and Ci s incidence ma ix. Then, he ec o
o isi a ios  (j)no malized, o ins ance, o ansi ion jcan be
compu ed om Csol ing he ollowing linea sys em o equa ions:
C· (j)=0,
(j)
j=1 (2.13)
F om he abo e heo em, o s uc u ally li e and s uc u ally
bounded mono-T-semiflow ne s we ha e:
 (j)=ϕ(N)(2.14)
and he nex complexi y esul ollows:
Co olla y 2.1.4 The compu a ion o he ec o o isi a ios o an-
si ions o a s uc u ally li e and s uc u ally bounded mono-T-semiflow
ne is polynomial on he ne size.
Since mono-T-semiflow ne s a e FRT-ne s, he “good” p ope ies
exhibi ed o hese a e inhe i ed by hose. Rela ed wi h he “bad”
esul s p esen ed o gene al FRT-ne s in p ope ies 2.1.4, 2.1.5, 2.1.6,
2.1.7, and 2.1.8, he same can be s a ed o mono-T-semiflow ne s. This
can be seen looking a he FRT-ne s depic ed in figu es 2.6, 2.7, 2.8,
and 2.9, ha we e used as coun e -examples. All o hem a e also
mono-T-semiflow ne s.
In he nex sec ion, we iden i y a subclass o mono-T-semiflow ne s
o which some o he p e ious nega i e esul s change.

60 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
2.1.2.2 S uc u ally decision- ee ne s
Le us in oduce a class o s uc u ally defined ne s o which ne e
exis conflic s, whiche e i is he ini ial ma king.
Defini ion 2.1.9 (S uc u ally decision- ee ne s) [CCS89] A ne
Nis said o be s uc u ally decision- ee iff o all place p:|p•|≤1.
Fo example, he ne depic ed in figu e 2.8 is a li e s uc u ally
bounded and s uc u ally decision- ee ne . Now, we p o e ha all
s uc u ally li e s uc u ally bounded and s uc u ally decision- ee
ne s a e mono-T-semiflow:
P ope y 2.1.10 Le Nbe a connec ed, consis en , and s uc u ally
decision- ee ne . Then Nis mono-T-semiflow.
P oo . Since he ne is consis en , i has a leas a T-semiflow. I has
no mo e han one because i a ansi ion belongs o a T-semiflow X,
all ou pu ansi ions o i s ou pu places mus belong o X(because
he ne is s uc u ally decision- ee). Since he ne is connec ed he e
exis s a mos one T-semiflow.
The e e se o p ope y 2.1.10 is no ue. Fo example he ne
o figu e 2.10 is mono-T-semiflow bu is no s uc u ally decision- ee.
Thus, consis en and s uc u ally decision- ee ne s cons i u e a p ope
subclass o mono-T-semiflow ne s.
We ha e seen ha , in gene al, li e s uc u ally bounded mono-T-
semiflow ne s ha e no home s a e. Howe e he subclass o deadlock-
ee and bounded s uc u ally decision- ee ne s ha e home s a e.
P ope y 2.1.11 Le N,M
0be a deadlock- ee and bounded s uc-
u ally decision- ee ne . Then, i has a home s a e.
P oo . Boundedness o he ne gua an ees a bounded numbe o each-
able ma kings. In his case, he absence o decisions assu es he exis-
ence o home s a e.
As a co olla y, e godici y o he ma king p ocess o such ne s ollows:
Co olla y 2.1.5 Le N,M
0be a bounded s uc u ally decision- ee
ne . Then i s ma king p ocess is weakly e godic. Mo eo e , i he ne
is Ma ko ian, i s ma king p ocess is s ongly e godic.
2.1. FRT-ne s and subclasses 61
2.1.2.3 Ma ked g aphs
In his sec ion, o dina y s uc u ally decision- ee ne s wi hou mul iple
a ibu ions o places a e conside ed: he well-known subclass o em
ma ked g aphs.
Ma ked g aphs can be seen as a gene aliza ion o he classical PERT
ool [MP70]. Wi h PERT model, he ela ionship among he asks o
a p ojec can be ep esen ed by a ne wo k o ac i i ies (a ows) and
e en s (nodes). Timing in e p e a ion can be added o ac i i ies o
he pu pose o e alua ing he comple ion ime o he p ojec . The
ob ained ne wo k is an acyclic g aph, i.e., epe i i e sys ems canno be
modelled.
Wi h ma ked g aphs, cyclic beha iou s can be modelled as well as
many diffe en classes o non sha ed esou ces o he ealiza ion o
ac i i ies ( okens a places o he ne ).
Le us b iefly ecall wha ma ked g aphs a e and some o hei basic
p ope ies. Ma ked g aphs allow o model concu ency and synch o-
niza ion bu no decisions because hey a e s uc u ally decision- ee
ne s.
Defini ion 2.1.10 (Ma ked g aphs) [CHEP71] Ma ked g aphs a e
o dina y Pe i ne s (i.e., p e- and pos -incidence unc ions aking alues
in {0,1}) such ha o all place p:|•p|=|p•|=1.
P ope y 2.1.12 Le Nbe a ma ked g aph.
1. Nis s uc u ally decision- ee.
2. Nis consis en and i s unique minimal T-semiflow is X=11.
3. The ec o o isi a ios o ansi ions o Nis  =11(p o ided
li eness), independen ly o he ini ial ma king and o he a e age
se ice imes associa ed wi h ansi ions.
The e e se o p ope y 2.1.12.1 is no ue. Fo example, he ne
depic ed in figu e 2.8 is s uc u ally decision- ee bu i is no a ma ked
g aph.
Some in e es ing esul s om quali a i e heo y o ma ked g aphs
a e ecalled bellow. In pa icula , checking hei li eness cha ac e iza-
ion is polynomial on he ne size.
62 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
Theo em 2.1.6 [Mu 89] Le N,M
0be a ma ked g aph.
1. The elemen a y P-semiflows o Na e exac ly i s di ec ed ci cui s.
2. N,M
0is li e iff all i s di ec ed ci cui s a e ma ked.
Pu ing an ini ial ma king la ge enough, a e ma king all ci cui s
he sys em will be li e:
Co olla y 2.1.6 Ma ked g aphs a e s uc u ally li e.
Co olla y 2.1.7 The li eness o a ma ked g aph can be decided in poly-
nomial ime on i s size, checking ha he e is no unma ked P-semiflow:
 ∃Y≥
0,Y
T·C=0,Y
T·M0=0 (2.15)
F om he heo em 2.1.6.2, he ollowing li eness mono onici y esul
ollows:
Co olla y 2.1.8 I N,M
0is a li e ma ked g aph and M
0≥M0 hen
N,M
0is li e.
Fo li e ma ked g aphs, boundedness and s uc u al boundedness
a e equi alen p ope ies:
P ope y 2.1.13 [Sil85] Le Nbe a ma ked g aph.
1. The ollowing h ee s a emen s a e equi alen :
i) Nis s uc u ally bounded.
ii) Nis s ongly connec ed.
iii) Nis conse a i e (i.e., ∃Y≥11,YT·C=0).
2. Le N,M
0be li e. Then N,M
0is bounded iff Nis s uc u ally
bounded.
Hope ully, he eachabili y p oblem, i.e., he efficien cha ac e iza-
ion o eachable ma kings, has a sa is ac o y solu ion o li e ma ked
g aphs:
2.1. FRT-ne s and subclasses 63
Theo em 2.1.7 [Mu 77] Le N,M
0be a li e ma ked g aph. The
h ee ollowing s a emen s a e equi alen :
i) M∈R(N,M
0), i.e., Mis eachable om M0.
ii) M=M0+C·σ, wi h M,σ≥0.
iii) B ·M=B ·M0, wi h B he undamen al ci cui ma ix o he
g aph, and M≥0.
Acco ding o he abo e heo em M∈R(N,M
0) i and only i M0∈
R(N,M). In o he wo ds:
Co olla y 2.1.9 Li e ma ked g aphs a e e e sible.
Weak e godici y o he fi ing and he ma king p ocesses o li e and
s ongly connec ed ma ked g aphs ollows ( om co olla y 2.1.5), since
hey a e bounded and s uc u ally decision- ee ne s:
Co olla y 2.1.10 The fi ing p ocess o a li e ma ked g aph is weakly
e godic. I he ne is s ongly connec ed he ma king p ocess is also
weakly e godic. Mo eo e , i he ne is Ma ko ian, i s ma king p ocess
is s ongly e godic.
Finally, he nex in e es ing p ope y o li e ma ked g aphs, can be
deduced:
P ope y 2.1.14 Le N,M
0be a ma ked g aph, and a ansi ion
o N. Then E( )=L( )=SE( ).
P oo . Ma ked g aphs a e e e sible, by co olla y 2.1.9. Then, by
p ope y 1.2.2, E( )=L( ) o all ansi ions . Finally, E( )=SE( ),
by heo em 2.1.7.i and ii.
This allows an efficien compu a ion o enabling and li eness bounds
based on he linea p og amming p oblem (LPP1) ha cha ac e izes
he s uc u al enabling bound o ansi ions.
64 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
2.1.3 F ee choice ne s
Ano he in e es ing subclass o FRT-ne s is ha o ee choice ne s.
F ee choice ne s [Hac72] a e a well-known subclass o o dina y Pe i
ne s ha hold a pa icula ly es ic ed in e play be ween concu ency
and decisions. They a e ich enough o be non- i ial bu es ic ed
enough o allow a numbe o in e es ing esul s ha do no hold in
gene al and ha cons i u e a qui e elegan heo y (see, e.g., [Hac72,
TV84,Bes87,CCS90a,Esp90,ES90]).
F ee choice ne s allow bo h synch oniza ion and conflic bu in a
es ic ed and disciplina ed way. In a ee choice ne , i a place has a
sha ed ou pu ansi ion hen i is he only ou pu ansi ion o his
place. And, equi alen ly, i a ansi ion has a sha ed inpu place hen
i is he only inpu place o his ansi ion.
Defini ion 2.1.11 (F ee choice ne s) [Hac72] F ee choice ne s a e
o dina y Pe i ne s (i.e., p e- and pos -incidence unc ions aking alues
in {0,1}) such ha o all place p:|p•|>1⇒•(p•)={p}.
Since all decisions a e ee in a ee choice ne , all he T-semiflows
a e eely ela ed and he ollowing inclusion holds:
P ope y 2.1.15 F ee choice (connec ed) ne s a e FRT-ne s.
Le us ema k also ha ma ked g aphs, p esen ed in p e ious sec-
ion, a e ee choice ne s.
This sec ion in oduces a minimum o quali a i e esul s om he
la ge body o ee choice ne s heo y. Addi ional quali a i e esul s
a e de i ed om he quan i a i e/pe o mance based app oach in o-
duced in his wo k. This app oach clea ly poin s ou he in e es o
in e lea ing he quali a i e and quan i a i e heo ies.
Le N=P, T, P e, Pos be a Pe i ne and P⊆P.N=
P,T,P e
, Pos is called a P-componen o Niff Nis he subne
o Ngene a ed by P(i.e., T⊆Tand P e, Pos a e he es ic ions
o P e, Pos o Pand T) and ∀ ∈T:|• ∩P|≤1∧| •∩P|≤1.
An impo an esul in he s uc u e heo y o ee choice ne s as-
su es ha each minimal P-semiflow o a s uc u ally li e and s uc-
u ally bounded ee choice ne gene a es a P-componen , and ha
li eness can be assu ed when all he P-componen s a e ma ked:

2.1. FRT-ne s and subclasses 65
Theo em 2.1.8 Le N=P, T, P e, Pos be a s uc u ally li e and
s uc u ally bounded ee choice ne .
1. [ES90] Y≥0is a minimal P-semiflow o Niff he wo ollowing
condi ions hold:
a) ∀p∈P:Y(p)∈{0,1}
b) ∃N
=P,T,P e
, Pos P-componen o Nand ||Y|| =
P
2. [Esp90] I M0is a gi en ini ial ma king o N,N,M
0is li e i
and only i all i s P-componen s a e ma ked.
No e ha he abo e heo em is a gene aliza ion o heo em 2.1.6
(s a ed o ma ked g aphs), o he case o s uc u ally li e and s uc-
u ally bounded ee choice ne s. The cha ac e iza ion o li eness o
such ne s is he same han o ma ked g aphs (co olla y 2.1.7):
Co olla y 2.1.11 The li eness o a s uc u ally li e and s uc u ally
bounded ee choice ne can be decided in polynomial ime on i s size,
checking ha he e is no unma ked P-componen :
 ∃Y≥
0,Y
T·C=0,Y
T·M0=0 (2.16)
F om he p e ious cha ac e iza ion o li eness, a mono onici y esul
i ially ollows o s uc u ally bounded ne s:
Co olla y 2.1.12 I N,M
0is a li e s uc u ally bounded ee choice
ne and M
0≥M0 hen N,M
0is li e.
In ac , s uc u al boundedness is no necessa y in he p e ious
p ope y (since li eness mono onici y can be de i ed om a mo e gen-
e al cha ac e iza ion o li eness o ee choice ne s [Hac72]).
Un o una ely, o gene al (non-s uc u ally bounded) ee choice
ne s, he ollowing “bad” esul has been p o en:
Theo em 2.1.9 [JLL77] Le N,M
0be a ee choice ne . The deci-
sion o non-li eness o N,M
0is NP-comple e.
66 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
As in he mo e gene al case o li e and bounded FRT-ne s, weak
e godici y o he fi ing p ocess is assu ed (and s ong e godici y o
Ma ko ian ne s), and he ec o o isi a ios can be compu ed in
polynomial ime om he ne s uc u e and he ou ing a es a con-
flic s, sol ing he sys em 2.8 p esen ed in sec ion 2.1.1.
A pa icula e sion o he ank heo em o s uc u ally li e and
s uc u ally bounded FRT-ne s (c . heo em 2.1.1) o ee choice ne s
can be s a ed:
Theo em 2.1.10 [CCS90a] Le Nbe a s ongly connec ed s uc u ally
bounded ee choice ne . Then he ne is s uc u ally li e iff ank(C)=
m−1−(a−n), whe e Cis he incidence ma ix o N,m=|T|,n=|P|,
and ais he numbe o inpu a cs o ansi ions.
The impo ance o his s a emen o ee choice ne s lies on he ac
ha se e al key esul s o ee choice heo y appea as co olla ies. Fo
example, he cha ac e iza ion o simul aneous s uc u al li eness and
s uc u al boundedness in ee choice ne s is o polynomial complexi y,
he e o e, om heo em 2.1.8.2, he nex esul ollows:
Co olla y 2.1.13 Le N,M
0be a s uc u ally bounded ee choice
ne . Then i can be decided in polynomial ime on he numbe o a cs
o Ni he ma ked ne is li e, checking he ank cha ac e iza ion o
s uc u al li eness ( heo em 2.1.10) and i all P-componen s a e ma ked
(wi h he algeb aic cha ac e iza ion o co olla y 2.1.11).
The ollowing duali y esul ollows also om heo em 2.1.10:
Co olla y 2.1.14 Le N=P, T, P e, Pos be a ee choice ne . N
is s uc u ally li e and s uc u ally bounded iff he e e se-dual o N,
N d =T, P, Pos , P e, is s uc u ally li e and s uc u ally bounded.
P oo . I Nis connec ed s uc u ally li e and s uc u ally bounded
hen i is s ongly connec ed, consis en , and conse a i e [CCS90d].
Then N d is s ongly connec ed, consis en , and conse a i e, hus
s uc u ally bounded.
Finally, since ank(C)= ank(C d), m d =n,n d =m, and a d =
a,weha em d −1−(a d −n d)=n−1−(a−m)=m−1−(a−n),
i.e., i Nis s uc u ally li e hen N d is also s uc u ally li e.
2.1. FRT-ne s and subclasses 67
Based on [BV84], W. Vogle p o ed in 1989 ha a li e and bounded
ee choice ne has a leas one home s a e.
Theo em 2.1.11 [Vog89] Le N,M
0be a li e and bounded ee
choice ne . Then N,M
0has a home s a e.
The impo ance o he p e ious esul om he pe o mance e alu-
a ion poin o iew is s a ed in he nex co olla y (see sec ion 1.2.3.3):
Co olla y 2.1.15 Le N,M
0be a s ochas ic li e and bounded ee
choice ne . Then i s ma king p ocess is weakly e godic. Mo eo e , i
he ne is Ma ko ian, i s ma king p ocess is s ongly e godic.
As in he case o ma ked g aphs, o li e and bounded ee choice
ne s, i is possible o show ha SB(p)=B(p).
Theo em 2.1.12 [Esp90] Le N,M
0be a li e and bounded ee
choice ne , hen o all place po N:B(p)=SB(p).
In o he wo ds, he s uc u al ma king bound is always eached in
a li e and bounded ee choice ne , and he nex esul ollows:
Co olla y 2.1.16 A li e ee choice ne is bounded iff i is s uc u ally
bounded.
The impo ance o he abo e esul s lies on he ac ha ma king
bounds can be efficien ly compu ed (looking o he s uc u al ones)
and, in pa icula , ha boundedness can be algeb aically cha ac e ized
(∃Y≥11 such ha YT·C≤0 [Mu 89]).
Using heo em 2.1.12, an in e es ing p ope y o li e and bounded
ee choice ne s, ha allows an efficien compu a ion o li eness bound
o ansi ions, can be de i ed:
Theo em 2.1.13 Le N,M
0be a li e and bounded ee choice ne .
Then, o all ansi ion o N:E( )=L( )=SE( ).
68 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
P oo . Le ibe a gi en ansi ion o N. A new li e and bounded
ee choice ne N ,M
0is ob ained by spli ing ansi ion iin o a
ansi ion i1, an unma ked place pi, and ano he ansi ion i2. Then,
o iand pi:SE( i)=SB(pi) and E( i)=B(pi). Since o li e and
bounded ee choice ne s B(pi)=SB(pi) (c . heo em 2.1.12) hen
E( i)=SE( i).
Li e and bounded ee choice ne s a e s uc u ally bounded (co ol-
la y 2.1.16) and li e. Since s uc u ally bounded ne s a e conse a i e
[Sil85], he s uc u al ma king bound coincides wi h he bound ob-
ained om a basis o P-semiflows: SB(pi) = max{M(pi)|BT·M=
BT·M
0,M ≥0}[CS89c].
Le Mhbe a home s a e o N ,M
0(i s exis ence is gua an eed by
heo em 2.1.11). Because Mhis eachable om M
0,BT·Mh=BT·M
0.
Conside ing as a new s a ing ime ha in which Mhis eached o he
fi s ime: SB(pi) = max{M(pi)|BT·M=BT·Mh,M ≥0}.Thus
SB(pi) is eached om a home s a e, and E( i)=L( i).
Now, om he p e ious heo em and aking in o accoun ha o
any ansi ion he compu a ion o he s uc u al enabling bound
SE( ) can be o mula ed in e ms o he p oblem (LPP1), he ollow-
ing mono onici y p ope y o he li eness bound o a ansi ion wi h
espec o he ini ial ma king is ob ained:
Co olla y 2.1.17 I N,M
0is a li e and bounded ee choice ne and
M
0≥M0 hen he li eness bound o in N,M
0is g ea e han o
equal o he li eness bound o in N,M
0.
The p e ious esul appea s o be a gene aliza ion (s a ed o he
pa icula case o bounded ne s) o he classical li eness mono onici y
p ope y o ee choice ne s s a ed in co olla y 2.1.12.
Finally, le us define s a e machines, a well-known subclass o ee
choice ne s:
Defini ion 2.1.12 (S a e machines) S a e machines a e o dina y
Pe i ne s (i.e., p e- and pos -incidence unc ions aking alues in
{0,1}) such ha o all ansi ion :|• |=| •|=1.
p1
1
p1
2
1
1
1
2
b1
b2
b3
3
1
3
2
3
p1
3
p2
2
3
2
2
2
1
2
p1
2
p2
2.1. FRT-ne s and subclasses 75
Figu e 2.13: A o ally open de e minis ic sys em o sequen ial p o-
cesses.
e godic such sys ems a e de i ed. Mo eo e , in chap e 5 we p o e ha
he e godici y cha ac e iza ion and he exac compu a ion o s eady-
s a e pe o mance measu es is possible in polynomial ime on he ne
size o hese ne s (assuming exponen ial iming).
Defini ion 2.1.16 (To ally open de e minis ic sys ems o se-
quen ial p ocesses) [CS89a] A de e minis ic sys em o sequen ial p o-
cesses is called o ally open iff he unde lying ne has no any ci cui
con aining buffe s.
An example o o ally open de e minis ic sys em o sequen ial p o-
cesses is depic ed in figu e 2.13.
Some in e es ing quali a i e esul s can be de i ed om he s uc-
u e o hese ne s. Li eness o o ally open de e minis ic sys ems o
sequen ial p ocesses and unboundedness o he buffe s a e p esen ed in
heo em 2.1.16. In heo em 2.1.17, consis ency (necessa y condi ion o
ma king e godici y o li e Ma ko ian ne s, c . heo em 1.2.3) is shown
o collapse wi h exis ence o home s a e o his subclass o ne s.
Theo em 2.1.16 Le N,M
0be a o ally open de e minis ic sys em
o sequen ial p ocesses. Then N,M
0is li e and all buffe s a e un-
bounded.

76 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
P oo . Le be N ,M
0=P1∪...∪Ps∪B,T1∪...∪Ts, P e, Pos , M0.
All Ni,M
0|i=Pi,T
i,P e|i, Pos |i,M
0|ia e li e in isola ion (by
p ope y 2.1.16, because M0ma ks all he s a e machines by defini-
ion 2.1.14.ii). All ansi ions o hose s a e machines wi hou inpu
buffe s can be fi ed an infini e numbe o imes, independen ly o he
es , so all he ou pu buffe s o hese machines do no es ic he fi -
ing o he o he machines. This a gumen can be epea ed o all he
sys em because o he absence o ci cui s con aining buffe s. Thus, he
ne is li e.
F om he li eness o he sys em and om he ac ha buffe s a e no
con ained in any ci cui , he inpu ansi ions o buffe s can be fi ed an
infini e numbe o imes wi hou fi ing hei ou pu ansi ions. Thus,
all buffe s a e unbounded.
An in e es ing p ope y o li e ma ked g aphs, p esen ed in heo-
em 2.1.7, ha s a es a b idge be ween i s beha iou al and s uc u al
analysis is ha all po en ially eachable ma kings a e eachable. I is
also ue o o ally open de e minis ic sys ems o sequen ial p ocesses:
P ope y 2.1.19 Le N,M
0be a o ally open de e minis ic sys em
o sequen ial p ocesses. Then M∈R(N,M
0)iff M∈PR(N,M
0).In
o he wo ds, each ec o σ ∈IN msuch ha M0+C·σ ≥0co esponds
a leas o one fi able sequence in N om M0.
P oo . Le σ ∈IN mbe such ha M0+C·σ ≥0. All ansi ions
ep esen ed in σ belonging o s a e machines wi hou inpu buffe s
(Ni1,...,Ni ) a e fi able a fi s . Then, ansi ions belonging o s a e
machines whose inpu buffe s a e ou pu o Ni1,...,Ni can be fi ed.
This p ocedu e can be epea ed o all s a e machines since no ci cui s
con aining buffe s exis .
The ollowing heo em ela es, o o ally open de e minis ic sys-
ems o sequen ial p ocesses, a beha iou al p ope y (exis ence o home
s a e) wi h a s uc u al one (consis ency).
Theo em 2.1.17 Le N,M
0be a o ally open de e minis ic sys em
o sequen ial p ocesses. Then Nis consis en iff M0is a home s a e.
1
1
b1
b2
2
2
2
1
2
p12
p2
p1
1p1
2
1
2
1
3
2.1. FRT-ne s and subclasses 77
Figu e 2.14: A non-consis en o ally open de e minis ic sys em o se-
quen ial p ocesses.
P oo . Le us suppose ha he e exis s X∈(IN+)msuch ha C·X=
0 (i.e., he ne is consis en ). Le M∈R(N,M
0) and σsuch ha
M0[σM. Le k∈IN be such ha kX ≥σ. Then, 
δ=kX −σ ≥0,
M0[σM[δM0(fi eabili y o δis deduced om p ope y 2.1.19) and M0
is a home s a e.
Le us suppose ha M0is a home s a e. Since he ne is li e (c . he-
o em 2.1.16), he e exis a ma king M1and a fi ing sequence σ1includ-
ing all ansi ions such ha M0[σ1M1. Since M0is a home s a e,
he e exis s a fi ing sequence σ2such ha M1[σ2M0. Then he ec o
σ1+σ2∈(IN+)mis such ha C·(σ1+σ2) = 0, whe e Cis he incidence
ma ix o he ne . The e o e, Nis consis en .
In heo em 1.2.3, a necessa y condi ion o he ma king e godici y
o a li e Ma ko ian Pe i ne is shown. Now, le us ema k ha he e
exis non-consis en o ally open de e minis ic sys ems o sequen ial
p ocesses (see figu e 2.14: M(b1)−M(b2)=σ( 1
1)−σ( 3
1)=σ( 1
1)−
[σ( 1
1)−σ( 2
1)−M(p1
1)] = M(p1
1)+σ( 2
1). Since he ne is li e, σ( 2
1)→
∞⇒M(b1)−M(b2)→∞⇒s uc u ally ma king non-e godic ne ).
Then, in p ac ice, i is con enien o check consis ency (a polynomial
ime compu a ion) o he unde lying ne be o e compu ing ma king
e godici y condi ions o a gi en Ma ko ian in e p e a ion o he o ally
open de e minis ic sys em o sequen ial p ocesses. Taking in o accoun
he abo e ema k and heo em 1.2.3, he ollowing esul wi h p ac ical
in e es can be s a ed:
b1b2
p1
1
p1
2
1
1
1
2
1
3
2
2
2
2
1
2
p1
p2
2
2
2
1
2
p1
2
p2
1
b
2
b
1
2
1
1
1
p1
1
p2
(a) S uc u ally non-e godic:
(•b ,•b )∉SDR; (b •,b • )∈SDR.
11
22
(b) Po en ially e godic:
(•b ,•b )∈SDR; (b •, b • )∈SDR.
1122
78 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
Figu e 2.15: Consis en o ally open de e minis ic sys ems o sequen ial
p ocesses wi h wo s a e machines and wo buffe s.
Co olla y 2.1.18 The e exis o ally open de e minis ic sys ems o se-
quen ial p ocesses ha a e ma king non-e godic o all iming in e p e-
a ion. In pa icula , non-consis en sys ems a e always ma king non-
e godic.
Un o una ely, i canno be s a ed ha i N,M
0is a consis en
o ally open de e minis ic sys em o sequen ial p ocesses, he e exis s
a Ma ko ian in e p e a ion such ha he s ochas ic ne is ma king e -
godic. The ne in figu e 2.15.a is consis en bu he e does no exis
any Ma ko ian in e p e a ion making i ma king e godic: he case o
(exponen ial) dis ibu ion a es λ2
1=λ3
1(o cou se, only possible in
heo y!) leads o a null ecu en Ma ko p ocess and so non-e godic,
because he ma king p ocess a buffe s b1and b2can be shown o be
isomo phic o a symme ical andom walk [Re 84].
The es o his sec ion is de o ed o he s udy o necessa y and su -
ficien condi ions o he “po en ial ma king e godici y” o sys ems. We
say ha a ne is po en ially ma king e godic iff he e exis s a Ma ko-
ian in e p e a ion (i.e., an assignmen o exponen ial andom iming)
2.1. FRT-ne s and subclasses 79
ha can lead o ma king e godic sys ems.
Fo cha ac e izing he possible exis ence o a Ma ko ian in e p e a-
ion making ma king e godic a gi en o ally open de e minis ic sys em
o sequen ial p ocesses, le us gi e local ules ha will be composed
s ep by s ep o a la ge sys em.
As a fi s s ep, a necessa y and sufficien condi ion o a de e minis-
ic sys em o wo sequen ial p ocesses o be po en ially ma king e godic
in e ms o consis ency o he ne and o some synch onic dis ance e-
la ions among ansi ions is p esen ed.
A e ha , a “ ansi i i y ule” o sys ems composed by h ee s a e
machines is p esen ed. I gi es a necessa y and sufficien condi ion o
such sys ems o be po en ially ma king e godic.
An i e a i e applica ion o he p esen ed ules leads o he de i a-
ion o necessa y and sufficien condi ions o a gene al o ally open
de e minis ic sys em o sequen ial p ocesses o be po en ially ma king
e godic.
Le us now ecall he concep o global synch onic dis ance ela ion.
I wo subse s o ansi ions a e in global synch onic dis ance ela ion
hen i is no possible o fi e an infini e numbe o imes some ansi ion
o he fi s subse wi hou fi ing any ansi ion o he second subse ,
and ice e sa. E en mo e, i wo subse s o ansi ions a e in global
synch onic dis ance ela ion hey beha e like i hey we e included in
a egula ion ci cui (see defini ion 2.1.6). Global synch onic dis ance
ela ion is used below o finding necessa y and sufficien condi ions o
he exis ence o a Ma ko ian in e p e a ion ha makes ma king e godic
a o ally open de e minis ic sys em o sequen ial p ocesses.
Defini ion 2.1.17 (Global synch onic dis ance ela ion) [Sil87]
Le N,M
0be a Pe i ne and T1,T
2subse s o ansi ions. T1and T2
a e in global synch onic dis ance ela ion, deno ed as (T1,T
2)∈SDR,
iff ∃W1,W
2∈IN m ec o s which exp ess he weigh s associa ed wi h he
ansi ions o he subse s T1and T2(i.e., ||W1|| =T1and ||W2|| =T2),
and ∃k∈IN such ha
sup
σ∈L(N,M)
M∈R(N,M0)
|(W1−W2)T·σ|≤k(2.22)
2
2
1
b
2
b
3
p3
3
13
2
3
33
4
3
p1
3
p2
1
3
1
2
1
1
1
p11
p2
2
12
p1
2
p2
80 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
Figu e 2.16: S uc u ally ma king non-e godic sys em wi h h ee s a e
machines.
The fi s esul is a nega i e one. I a gi en s a e machine ecei es
okens om wo diffe en s a e machines, one o hem wi hou inpu
buffe s, he sys em canno be ma king e godic (see figu e 2.16).
Theo em 2.1.18 Le N,M
0=P1∪... ∪Ps∪B,T1∪... ∪
Ts, P e, Pos , M0be a o ally open de e minis ic sys em o sequen-
ial p ocesses such ha o one o hei communica ing s a e machines
Ni,M
0|i=Pi,T
i,P e|i, Pos |i,M
0|i:
a) ∃b1such ha b•
1⊆Ti(i.e., i is an inpu buffe o he machine
Ni,M
0|i) and •b1⊆Tj, whe e Tjis he se o ansi ions o
ano he s a e machine Nj,M
0|jsuch ha  ∃b∈Bsa is ying
b•⊆Tj(i.e., he inpu s a e machine o buffe b1has no inpu
buffe s), and
b) ∃b2such ha b•
2⊆Ti(i.e., ano he inpu buffe o he machine
Ni,M
0|i) and •b2⊆ Tj(i.e., he inpu s a e machine o buffe
b2is no Nj,M
0|j).
Then, he e is no Ma ko ian in e p e a ion such ha he co esponding
s ochas ic ne is ma king e godic.
P oo . The a i al p ocesses o okens o buffe s b1and b2a e Poisson-
like independen s ochas ic p ocesses [Ros83] join by a s a e machine.

2.1. FRT-ne s and subclasses 81
Then, he unde lying Ma ko chain is ansien (in he case in which
he ma king o one buffe ends o infini y wi h ime) o null ecu en
(case os s ochas ic equilib ium, equi alen o a symme ical andom
walk) bu ne e posi i e ecu en .
Now, le us gi e necessa y and sufficien condi ions o he exis ence
o a Ma ko ian iming in e p e a ion ha makes ma king e godic a
sys em composed by wo s a e machines (see figu es 2.14 and 2.15).
Basically, he ne mus be consis en and o each pai o buffe s be-
ween bo h s a e machines, he inpu (ou pu ) ansi ions o one buffe
canno fi e an infini e numbe o imes wi hou fi ing he inpu (ou -
pu ) ansi ions o he o he buffe . In his way, null ecu ency o he
associa ed Ma ko p ocess is disca ded.
Theo em 2.1.19 Le N,M
0=P1∪P2∪B,T1∪T2, P e, Pos , M0
be a o ally open de e minis ic sys em o sequen ial p ocesses composed
by wo s a e machines and a se o buffe s Bsuch ha ∀b∈B:•b⊆
T1,b
•⊆T2. Then, he e exis s a Ma ko ian in e p e a ion making
ma king e godic he sys em i and only i :
i) Nis consis en and
ii) ∀bi,b
j∈B:(•bi,•bj)∈SDR and (b•
i,b
•
j)∈SDR.
P oo . Le us suppose ha he e exis s a Ma ko ian iming mak-
ing ma king e godic he sys em. Then he ne is consis en by heo-
em 1.2.3. I (•b1,•b2)∈ SDR o (b•
1,b
•
2)∈ SDR hen he ma king o
b1and b2canno be linea ly exp essed he one in unc ion o he o he .
These buffe s ha e wo non-equal a i al a es, join by a unique se e
( he s a e machine). Thus, he unde lying Ma ko chain is ansien
o null ecu en , bu ne e posi i e ecu en . The e o e, i is ma king
non-e godic.
Now, le us suppose ha (i) and (ii) hold. Le us conside b1,b
2∈B.
Le us deno e •b1=T11,•b2=T12,b•
1=T21, and b•
2=T22.
Since (T11,T
12)∈SDR and (T21,T
22)∈SDR, he e exis ec o s
W11,W
12,W
21,W
22 ∈IN mwi h ||Wij|| =Tij,i,j =1,2 (see defini-
ion 2.1.17) such ha wo egula ion ci cui s can be added wi hou
changing he beha iou o he ne , as ollows (see figu e 2.17):
s11
s12
s21
s22
b1b2
1
2
2
1
b
•1
b•
1
b
•2
b•
2
1
2
M
M
82 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
Figu e 2.17: Regula ion ci cui s be ween ansi ions in global syn-
ch onic dis ance ela ion.
P
1=P1∪{s11,s
12}wi h s•
11 =•s12 =T11,•s11 =s•
12 =T12,
and P e(s11, )=Pos (s12, )=W11( ),∀ ∈T11,P e(s12, )=
Pos (s11, )=W12( ),∀ ∈T12.
P
2=P2∪{s21,s
22}wi h s•
21 =•s22 =T21,•s21 =s•
22 =T22,
and P e(s21, )=Pos (s22, )=W21( ),∀ ∈T21,P e(s22, )=
Pos (s21, )=W22( ),∀ ∈T22.
Now, om consis ency o he ne : ∃X≥11 such ha C·X=0.
Then, he column ec o s o he incidence ma ix (o he modified ne )
co esponding wi h ansi ions T11,T
12,T
21, and T22 mus be linea ly
independen , o equi alen ly: W11 =W21 and W12 =W22. This im-
plies ha he ma kings o bo h buffe s a e linea ly independen . The
a gumen abo e can be applied o all pai o buffe s o he ne . Then,
he ma king o all o hem can be exp essed in e ms o he ma king
o one buffe and he ma king o he s a e machines. Then, a Ma ko
iming can be associa ed such ha he in e a i al imes o okens o
he buffe s a e g ea e han he “se ice imes” (mean cycle imes o
he ou pu s a e machines, in isola ion).
2.1. FRT-ne s and subclasses 83
No e ha in he case o o ally open de e minis ic sys ems o se-
quen ial p ocesses composed by wo s a e machines, i (i) and (ii) o
heo em 2.1.19 hold hen he ma king o all he buffe s can be always
compu ed om he ma king o one buffe and he ma king o he s a e
machines. Wi h he objec o compu ing e godici y condi ions o a
la ge sys em including Nas a subsys em, i (i) and (ii) hold, om
he pe o mance poin o iew, we can suppose wi hou loss o gene -
ali y ha he wo s a e machines a e communica ing wi h a mos one
buffe .
Le us now gi e he “ ansi i i y ule” o h ee s a e machines
communica ing wi h buffe s like in figu e 2.13. This ule comple es
he s a ing o necessa y and sufficien condi ions o he exis ence o
a Ma ko ian iming ha makes ma king e godic a gi en o ally open
de e minis ic sys em o sequen ial p ocesses.
Theo em 2.1.20 Le N,M
0=P1∪P2∪P3∪{b1,b
2,b
3},T
1∪T2∪
T3, P e, Pos , M0be a o ally open de e minis ic sys em o sequen ial
p ocesses composed by h ee s a e machines and h ee buffe s such ha
•b1⊆T1,b
•
1⊆T3,•b2⊆T1,b
•
2⊆T2,•b3⊆T2, and b•
3⊆T3. Then, he e
exis s a Ma ko ian in e p e a ion making ma king e godic he sys em
iff:
i) Nis consis en and
ii) (•b1,•b2)∈SDR,(b•
2,•b3)∈SDR,(b•
1,b
•
3)∈SDR.
P oo . I (•b1,•b2)∈ SDR o (b•
2,•b3)∈ SDR o (b•
1,b
•
3)∈ SDR hen
he ma king o b1and b3canno be linea ly exp essed he one in unc ion
o he o he . Then, hese buffe s ha e non-equal a i al a es, join by a
unique se e ( he s a e machine). Thus, he unde lying Ma ko chain
is ansien o null ecu en , bu ne e posi i e ecu en . The e o e,
i is ma king non-e godic.
Now, le us suppose ha (i) and (ii) hold. (b•
2,•b3)∈SDR
implies ha b2,N2,M
0|2=P2,T
2,P e|2, Pos |2,M
0|2, and b3
can be subs i u ed by a unique buffe wi hou changing he be-
ha iou o N1,M
0|1=P1,T
1,P e|1, Pos |1,M
0|1and N3,M
0|3=
P3,T
3,P e|3, Pos |3,M
0|3. Then, i he ne is consis en , (•b1,•b2)∈
SDR and (b•
1,b
•
3)∈SDR, and heo em 2.1.19 can be applied.
84 CHAPTER 2. Pe i ne subclasses and quali a i e heo y
I (i) and (ii) o heo em 2.1.20 hold, hen he ma king o b3can
be always compu ed om he ma king o b1,b
2and he ma king o he
s a e machines. As an example, le as conside he sys em depic ed in
figu e 2.13. I e ifies condi ions (i) and (ii) o heo em 2.1.20. And i
can be easily checked ha : M(b3)=M(b1)+M(p2
1)+M(p2
3)−M(b2)−
M(p1
2), o all ma king M, eachable om he ini ial ma king.
Wi h he objec o compu ing condi ions o a la ge sys em includ-
ing Nas a subsys em, i (i) and (ii) hold, he s a e machine M2and
he buffe s b2,b
3can be subs i u ed by a unique buffe .
Theo ems 2.1.19 and 2.1.20 p o ide ules o an i e a i e educ ion
o buffe s o a o ally open de e minis ic sys em o sequen ial p ocesses.
These ules p ese e he possibili y o exis ence o a Ma ko ian iming
ha makes he sys em ma king e godic i he necessa y and sufficien
condi ions (s a ed in he men ioned heo ems) hold.
The e o e he exis ence o a Ma ko ian iming ha makes ma king
e godic a o ally open de e minis ic sys em o sequen ial p ocesses is
cha ac e ized in e ms o pu e s uc u al condi ions ha can be checked
in polynomial ime: consis ency and some global synch onic dis ance
ela ions.
2.2 Pe sis en ne s and beha iou ally ex-
ended ee choice ne s
Pe sis en ne s [LR78] and beha iou ally ex ended ee choice ne s (o
“ ´eseaux `a choix non-impos´e” [B a83]) a e ecalled in his sec ion as be-
ha iou ally defined ne subclasses o which some eachabili y analysis
is needed o he compu a ion o he ec o o isi a ios o ansi-
ions. The e o e, isi a ios do depend no only on he s uc u e and
ou ing bu also on he ini ial ma king.
2.2.1 Pe sis en ne s
Pe sis en ne s [LR78] cons i u e a beha iou ally cha ac e ized sub-
class o Pe i ne s which has a common p ope y wi h li e and bounded
mono-T-semiflow ne s: all hei consis en fi ing coun ec o s a e p o-
po ional o a unique ec o , which is he unique minimal T-semiflow
Chap e 3
Bounds o s ongly
connec ed ma ked g aphs
In his chap e , we ob ain uppe and lowe bounds on he s eady-s a e
pe o mance o ma ked g aphs [CCCS89,CCCS90], a well-known sub-
class o Pe i ne s (see defini ion 2.1.10) ha allow only concu ency
and synch oniza ion bu no choice. In pa icula we de i e bounds o
he h oughpu o ansi ions (see defini ion 1.2.5), defined as he a -
e age numbe o fi ings pe ime uni (o i s in e se, ha we call he
mean cycle ime o ansi ions). F om his quan i y, applying Li le’s
o mula [Li 61] i is possible o de i e o he a e age pe o mance es i-
ma es o he model. Unde hese es ic ions we will show esul s ha
can be compu ed in polynomial ime on he size o he ne model, and
ha depend only on he mean alues and no on he highe momen s
o he p obabili y dis ibu ion unc ions o he andom a iables ha
desc ibe he iming o he sys em. The independence o he p obabili y
dis ibu ion can be iewed as a use ul gene aliza ion o he pe o mance
esul s, since highe momen s o he se ice delays a e usually unknown
o eal cases, and difficul o es ima e and assess. Mo eo e we show
ha bo h uppe and lowe bounds, compu ed by means o p ope lin-
ea p og amming p oblems, a e igh , in he sense ha o any ma ked
g aph model i is possible o define amilies o s ochas ic imings such
ha he s eady-s a e pe o mances o he imed Pe i ne models a e
a bi a ily close o ei he bound.
Figu e 3.1 depic s an example o a li e and 1–bounded ma ked
91

F J
N=1
p1
p2
p3p5
p4
1
2
3
4
92 CHAPTER 3. Bounds o s ongly connec ed ma ked g aphs
Figu e 3.1: Example o a 1–bounded ma ked g aph and i s synch onized
queueing ne wo k coun e pa .
g aph. In he same figu e he equi alen ep esen a ion in e ms o
queueing ne wo k wi h synch oniza ion p imi i es [SMK82] is also de-
pic ed. Acco ding o figu e 3.1, Pe i ne places co espond wi h
queues, while ne ’s ansi ions ep esen se e s and synch oniza ion
cons ain s. I is easily seen ha only sum and “max” ope a o s a e
needed o compu e he pe o mance: indeed he ac ual cycle ime in
his example is he andom a iable γ=τ1+ max{τ2,τ
3}+τ4(whe e
τideno es he enabling ime o ansi ion i, o i s se ice ime, wi h
queueing ne wo ks e minology), he e o e he mean cycle ime is
Γ=E[γ]=E[τ1]+E[max{τ2,τ
3}]+E[τ4]=s1+E[max{τ2,τ
3}]+s4
(3.1)
whe e sideno es he a e age enabling ime o ansi ion i, i.e., i s
a e age se ice ime. Cohen e al. de eloped a special algeb a o o -
malize he p ope ies o his kind o models in he de e minis ic case
[CMQV89]. F. Baccelli e al. ex ended his app oach o he s ochas ic
case [BM89,BBW89].
Ou idea is ha o compu ing as bounds o he h oughpu
o ansi ions based only on he knowledge o he fi s momen s o
p obabili y dis ibu ion unc ions. This can be in ui i ely explained
as ollows. The sum is independen o he p obabili y dis ibu ion
3.0. Uppe bound on h oughpu 93
( o linea i y); since o non-nega i e a iables xi≤maxi{xi}≤
ixi,E[maxi{xi}] can be bounded by maxi{E[xi]}≤E[maxi{xi}]≤
iE[xi]. The e o e o he ne in figu e 3.1 we can w i e:
s1+ max{s2,s
3}+s4≤Γ≤s1+s2+s3+s4(3.2)
In his chap e , we show how linea p og amming p oblems based on
he incidence ma ix o he unde lying Pe i ne s uc u e can be sol ed
o compu e his kind o bounds o ma ked g aphs. In sec ion 3.1, we
ocus ou a en ion on h oughpu uppe bounds o s ongly connec ed
ma ked g aphs. Applying Li le’s o mula [Li 61] o each place o he
ne and using s uc u al in o ma ion aken om P-semiflows, a linea
p og amming p oblem is de i ed whose op imum solu ion (which can
be compu ed in polynomial ime) is a lowe bound o he mean cy-
cle ime o ansi ions (in e se o he a e age h oughpu ). Mo eo e ,
his bound is shown o be eachable o a bi a y ne s uc u e, ini ial
ma king, and mean and a iance o ansi ion se ice imes. F om
he linea p og amming o m o he compu ed bound, some in e es ing
esul s a e de i ed.
A igh lowe bound o he s eady-s a e h oughpu (uppe bound
o he mean cycle ime) is ob ained in polynomial ime in sec ion 3.2,
om he knowledge o he gi en a e age se ice imes and he li eness
bounds o ansi ions, which a e compu ed by sol ing p ope linea
p og amming p oblems. This bound canno be imp o ed unless mo e
in o ma ion om he se ice imes o ansi ions han hei mean alues
a e used.
The case o non-s ongly connec ed (i.e., unbounded) ma ked g aphs
is conside ed in sec ion 3.3. Fo hese ne s, he exac h oughpu o
ansi ions can be de i ed om he knowledge o he exac h oughpu
o he isola ed s ongly connec ed componen s. Since we a e able o
compu e bounds o he h oughpu o he isola ed s ongly connec ed
componen s, bounds o he whole ne can be ob ained. Finally, in
sec ion 3.4, some concluding ema ks a e p esen ed.
94 CHAPTER 3. Bounds o s ongly connec ed ma ked g aphs
3.1 Uppe bound o he s eady-s a e
h oughpu
In his sec ion, uppe bounds on h oughpu o s ongly connec ed
(and hus s uc u ally bounded, by p ope y 2.1.13) ma ked g aphs a e
p esen ed. We ema k ha s ong connec i i y o a g aph is a well-
known p oblem o polynomial ime complexi y.
3.1.1 Li le’s law and P-semiflows
Th ee o he mos significan pe o mance measu es o a closed egion
o a ne wo k in he analysis o queueing sys ems a e ela ed by Li le’s
o mula [Li 61], which holds unde e y gene al (i.e., weak) condi ions:
Q =X R (3.3)
Q is he a e age numbe o cus ome s in he egion, X is he
ou pu a e ( h oughpu ) om he egion (which is equal o he inpu
a e), and R is he a e age ime spen by a cus ome wi hin he egion.
Now, Li le’s esul is applied o each place o a weakly e godic ne .
Deno ing as M(pi) he limi a e age numbe o okens a place pi,X
he limi ec o o ansi ion h oughpu s (see defini ion 1.2.5), and
R(pi) he a e age ime spen by a oken wi hin he place pi(a e age
esponse ime a place pi), he abo e men ioned ela ionship is s a ed
as ollows (see [FN85a]):
M(pi)=(PRE[pi]·X)R(pi)(3.4)
whe e PRE[pi]is hei h ow o he p e-incidence ma ix o he unde -
lying Pe i ne , hus PRE[pi]·Xis he ou pu a e o place pi.
In he s udy o compu e sys ems, Li le’s law is equen ly used
when wo o he ela ed quan i ies a e known and he hi d one is
needed. This is no exac ly he case he e. Now, R(pi) and M(pi) a e
unknown. On he o he hand, he ec o o isi a ios
 (j)=1
X( j)X=Γ
(j)X(3.5)
3.1. Uppe bound on h oughpu 95
no malized o ha ing he j h componen equal 1, can be easily com-
pu ed o impo an ne subclasses (see chap e 2) and, in pa icula ,
o li e ma ked g aphs. Γ(j)is called mean cycle ime o ansi ion j
(in e se o i s a e age h oughpu ).
The a e age esponse imes a places R(pi) a e unknown. In ac ,
hey can be exp essed as sums o he a e age wai ing imes due o
he synch oniza ion schemes and he a e age se ice imes associa ed
wi h ansi ions, and only a e age se ice imes a e known: si,i=
1,...,m. Thus he a e age esponse imes can be lowe ly bounded om
he knowledge o he a e age se ice imes, and he ollowing sys em o
inequali ies can be de i ed om (3.4):
Γ(j)M≥PRE ·
D(j)(3.6)
whe e 
D(j)is he ec o wi h componen s D(j)
i= (j)
isi, a e age se ice
demand (o loading) o each ansi ion io he ne , ha is he a e age
o al se ice ha a oken demands om ansi ion iin all i s isi s o
i . The supe sc ip “(j)” indica es ha he ec o is no malized o
ha ing he j h componen D(j)
jequal o sj(i.e., (j)
i= 1).
Since ma ked g aphs a e consis en ne s and hei unique minimal
T-semiflow is 11, we ha e  (j)=11= o all ansi ion j(c . p op-
e y 2.1.12), hus o all j=1,...,m,Γ
(j)=Γ, 
D(j)=
D=s (whe e s
deno es he ec o wi h componen s si,i=1,...,m), and
ΓM≥PRE ·s (3.7)
F om his inequali y, a lowe bound Γmin o he mean cycle ime
o ansi ions can be de i ed. We ake in o accoun ha Γmin mus be
such ha inequali y (3.7) holds and o some place pi he equali y is
eached:
Γmin =PRE[pi]·s
M(pi)(3.8)
Since he ec o Mis unknown, (3.8) canno be sol ed. Howe e ,
he ollowing s uc u al ma king in a ian can be w i en using a P-
semiflow Y:
YT·M0=YT·M=YT·M, ∀M0∈IN n,∀M∈R(N,M
0)(3.9)
96 CHAPTER 3. Bounds o s ongly connec ed ma ked g aphs
Now, om (3.7) and (3.9):
Γ(YT·M0)≥YT·PRE ·s (3.10)
And a lowe bound o he mean cycle ime in s eady-s a e is:
Γmin = max
Y∈{P−semi low}
YT·PRE ·s
YT·M0
(3.11)
O cou se, an uppe bound o he h oughpu o ansi ions is
1/Γmin.
Le us o mula e he p e ious lowe bound o he mean cycle ime
in e ms o a pa icula class o op imiza ion p oblems called ac ional
p og amming p oblems [Mu 83]:
Γmin = maximize YT·PRE ·s
YT·M0
subjec o YT·C=0
11T·Y>0
Y≥0
(3.12)
The abo e p oblem can be ew i en as ollows:
Γmin = maximize YT·PRE ·s
q
subjec o YT·C=0
11T·Y>0
YT·M0=q
Y≥0
(3.13)
Then, because YT·M0>0 (gua an eed o li e ma ked g aphs, by
co olla y 2.1.7), we can change Y
qby Yand ob ain he linea p og am-
ming o mula ion s a ed in he nex heo em (in which 11T·Y>0is
emo ed because YT·M0= 1 implies 11T·Y>0):

3.1. Uppe bound on h oughpu 97
Theo em 3.1.1 A lowe bound o he mean cycle ime o li e
s ongly connec ed ma ked g aphs can be ob ained by sol ing he ol-
lowing linea p og amming p oblem:
Γmin =maximize YT·PRE ·s
subjec o YT·C=0
YT·M0=1
Y≥0
(LPP3)
The ollowing heo em conce ns a special class o op imum solu ions
o (LPP3) ha will be used la e in he in e p e a ion o his linea
p og amming p oblem: he minimal P-semiflows. Fi s ly, we p esen a
lemma ha will be used in he p oo o he heo em.
Lemma 3.1.1 [MS82] Le Nbe a Pe i ne and Ci s incidence ma ix.
A P-semiflow Yo Nis minimal iff he ca dinal o i s suppo is one
uni highe han he ank o he subma ix made up o he ows lio C
such ha Y(i)is no ze o.
In o de o p o e he heo em, we use he concep o basic easible
solu ion om linea p og amming [Mu 83], and he p oblem (LPP3)
ew i en in he ollowing way:
Γmin = maximize YT·PRE ·s
subjec o YT·[C|M0]=(0|1)
Y≥0
(LPP4)
Le Ybe he se o easible solu ions o (LPP4). I Y∈Y, he
se o ow ec o s o A=[C|M0] ha Yuses is {A[j]|jis such ha
Y[j]>0}. The easible solu ion Y∈Yis said o be a basic easible
solu ion o (LPP4) iff he se o ow ec o s o A ha Yuses is a
linea ly independen se .
Theo em 3.1.2 Unde he condi ions o heo em 3.1.1, i (LPP3) has
an op imum solu ion, hen i has an op imum solu ion which is a min-
imal P-semiflow.
P oo . Taking in o accoun [Mu 83, heo em 3.3], i (LPP4) has an
op imum easible solu ion, hen i has a basic easible solu ion Y ha
98 CHAPTER 3. Bounds o s ongly connec ed ma ked g aphs
is op imum. The e o e, he se o ows ha a e used by Yis linea ly
independen (i.e., ull ank). Conside ing ha YT·C= 0, he numbe
o non-null en ies o ec o Y(i.e., he numbe o ows used by Y)is
equal o he ank o ows o Cused by Yplus one. This las s a emen
is p ecisely he cha ac e iza ion o a minimal P-semiflow, p esen ed in
lemma 3.1.1.
I is well-known ha he simplex me hod o he solu ion o lin-
ea p og amming p oblems gi es good esul s in p ac ice, e en i i
has exponen ial wo s case complexi y. In any case, an algo i hm o
polynomial wo s case complexi y can be ound in [Ka 84].
Theo em 3.1.1 shows ha he p oblem o finding an uppe bound o
he s eady-s a e h oughpu (lowe bound o he mean cycle ime) in a
s ongly connec ed s ochas ic ma ked g aph can be sol ed looking a he
mean cycle ime associa ed wi h each P-semiflow (ci cui s o ma ked
g aphs, see heo em 2.1.6) o he ne , conside ed in isola ion. These
cycle imes can be compu ed making he summa ion o he a e age
enabling imes o all he ansi ions in ol ed in he P-semiflow (se ice
ime o he whole ci cui ), and di iding by he numbe o okens p esen
in i (cus ome s in he ci cui ).
3.1.2 Reachabili y o he uppe bound
The abo e bound ha holds o any s ochas ic in e p e a ion, hap-
pens o be he same ha has been ob ained o s ongly connec ed
de e minis ically imed ma ked g aphs by o he au ho s (see o ex-
ample [Ram74,RH80]), bu he e i is conside ed in a p ac ical linea
p og amming o m. Fo de e minis ically imed ne s, he eachabili y
o his bound has been shown [Ram74,RH80]. Since de e minis ic im-
ing is jus a pa icula case o s ochas ic iming, he eachabili y o he
bound is assu ed o ou pu poses as well. E en mo e, he nex esul
shows ha he p e ious bound canno be imp o ed only on he base o
he knowledge o he coefficien s o a ia ion o he ansi ion se ice
imes.
Theo em 3.1.3 Fo li e s ongly connec ed ma ked g aphs wi h a -
bi a y alues o mean and a iance o ansi ion se ice imes, he
3.1. Uppe bound on h oughpu 99
lowe bound o he mean cycle ime ob ained om (LPP3) canno be
imp o ed.
P oo . We know om [Ram74] ha o de e minis ic iming he bound
is eached. Only “max” and sum ope a o s a e needed o compu e he
cycle ime. The e o e we mus cons uc a amily o andom a iables
wi h a bi a y means and a iances beha ing in he limi like de e -
minis ic iming o bo h ope a o s (max and sum).
This is he case o he ollowing amily o andom a iables, o
a ying alues o he pa ame e α∈[0,1):
Xsi,σi(α)=siαwi h p obabili y 1 −i
si(α+1−α
i) wi h p obabili y i(3.14)
whe e
i=s2
i(1 −α)2
s2
i(1 −α)2+σ2
i
(3.15)
These a iables a e such ha E[Xsi,σi(α)] = si,Va [Xsi,σi(α)] = σ2
i,
and hey e i y:
lim
α→1E[max{Xsi,σi(α),X
sj,σj(α)}] = max{si,s
j}(3.16)
and, o cou se, o all αsuch ha 0 ≤α<1: E[Xsi,σi(α)+Xsj,σj(α)] =
si+sj.
Then, i andom a iables Xsi,σi(α) a e associa ed wi h ansi ions
i,i=1,...,m, aking αclose o 1, he mean cycle ime ends o he
bound gi en by (LPP3).
A polynomial compu a ion o he minimal cycle ime o de e -
minis ically imed s ongly connec ed ma ked g aphs was p oposed in
[Mag84], sol ing he ollowing linea p og amming p oblem:
Γmin = minimize γ
subjec o −C·z+γM0≥POST ·s
γ, z ≥0
(LPP5)
100 CHAPTER 3. Bounds o s ongly connec ed ma ked g aphs
To in es iga e he ela ionship be ween (LPP3) and (LPP5) le us
conside he dual p oblem [Mu 83] o (LPP5):
Γmin = maximize YT·POST ·s
subjec o YT·C≤0
YT·M0≤1
Y≥0
(LPP6)
Since s ongly connec ed ma ked g aphs a e conse a i e (p op-
e y 2.1.13), he e does no exis Y≥0 such ha YT·C≤
/0 and hen he
cons ain YT·C≤0 o (LPP6) becomes YT·C= 0 (i.e., he cons ain
o (LPP3)). Fo all Ysuch ha YT·C=0: YT·POST =YT·PRE.
Fo li e ma ked g aphs, ∀Y∈IN n,Y= 0 such ha YT·C= 0 hen
YT·M0≥1 (co olla y 2.1.7). Thus he cons ain YT·M0≤1 o (LPP6)
becomes YT·M0= 1 o li e ne s (i.e., he cons ain o (LPP3)).
Hence o li e s ongly connec ed ma ked g aphs, he p oblem
(LPP3) is equi alen o (LPP5) o mula ed in [Mag84] o de e min-
is ic sys ems.
3.1.3 In e p e a ion and de i ed esul s
Linea p og amming p oblems gi e an easy way o de i e esul s and
in e p e hem. Jus looking a he objec i e unc ion o he p ob-
lem (LPP3) he ollowing mono onici y p ope y is ob ained: he lowe
bound o he mean cycle ime does no inc ease i s dec eases o i M0
inc eases.
P ope y 3.1.1 Le N,M
0be a li e s ongly connec ed ma ked g aph
and s he ec o o a e age se ice imes.
1. Fo a fixed s,i M
0≥M0(i.e., inc easing he numbe o ini-
ial esou ces) hen he lowe bound o he mean cycle ime o
N,M
0,sis less han o equal o he one o N,M
0,s(i.e.,
Γmin≤Γmin).
2. Fo a fixed M0,i 
s≤s (i.e., o as e esou ces) hen he lowe
bound o he mean cycle ime o N,M
0,
sis less han o equal
o he one o N,M
0,s(i.e., Γmin≤Γmin).
p1
p2p3
p5
p4
1
2 3
4
p1
p2p3
p5
p4
1
2 3
4
p6
p1
p3
p5
p4
1
2 3
4
p6
a) O iginal ne wi h
and concu en .
2
3
b) T ans o med ne :
and sequen ialized
and p made implici .
2
2
3
c) Elimina ion o implici places.
Main loop: p , p , p , p .
Mino cycle: p , p , p .
1
1
3
3
4
5
6
3.2. Lowe bound on h oughpu 107
Figu e 3.2: Example o s uc u al sequen ializa ion.
An example o applica ion o he lemma ollows, in o de o cla i y
he p ocedu e. Conside he ne depic ed in figu e 3.2.a. This ne
con ains only wo cycles, namely 1,
2,
4, and 1,
3,
4; we can hen
add ei he he cycle 1,
2,
3,
4o 1,
3,
2,
4; figu e 3.2.b depic s he
esul ing ne in case we choose o add he second cycle. In his case
only place p6( om 3 o 2) needs o be added o ob ain he longe
cycle, and i should be ma ked wi h one oken, so ha he new cycle
comp ising places p1,p
3,p
6,p
4con ains wo okens, as he o iginal cycle
p1,p
2,p
4(while he o he o iginal cycle p1,p
3,p
5con ained only one).
In ou example, we need no o i e a e he p ocedu e since we al eady
ha e ob ained a cycle con aining all ansi ions o he ma ked g aph.
A his poin we can iden i y and elimina e he implici places ha ha e
been c ea ed du ing he cycles in e lea ing p ocedu e. In he p esen
example, we can easily see ha place p2becomes implici in figu e 3.2.b,
so ha i can be emo ed, finally leading ou sel es o he ma ked g aph
depic ed in figu e 3.2.c.
I should be e iden ha he ma ked g aph ans o med by applying
he abo e lemma has a mean cycle ime which is g ea e han o equal
o he mean cycle ime o he o iginal one, since some addi ional con-

108 CHAPTER 3. Bounds o s ongly connec ed ma ked g aphs
s ain s ha e been added o he enabling o ansi ions: hence he mean
cycle ime o he ans o med ma ked g aph is a lowe bound o he
pe o mance o he o iginal one. Now i NM= max ∈TL( ) = 1 in he
abo e lemma, we e-find he lowe bound o heo em 3.2.1. In he case
o NM>1 we can show ha he mean cycle ime o he ans o med
ne canno exceed Γmax o equa ion 3.21 as ollows.
Theo em 3.2.2 Fo any li e and bounded ma ked g aph wi h a spec-
ifica ion o he a e age se ice ime sj o each ansi ion ji is no
possible o assign p obabili y dis ibu ion unc ions o he ansi ion se -
ice imes such ha he mean cycle ime is g ea e han
Γmax =
m

j=1
sj
L( j)(3.22)
independen ly o he opology o he ne (and hus independen ly o he
po en ial maximum deg ee o pa allelism in insic in he ma ked g aph).
P oo . Wi hou loss o gene ali y, assume ha ansi ions in he ne
esul ing om he applica ion o lemma 3.2.1 a e pa i ioned in wo
classes C2and C1, wi h li eness bounds K2=NM>1 and K1<N
M,
espec i ely ( he p oo is easily ex ended o he case o mo e han wo
classes). Cons uc a new model con aining only K1 okens in he main
cycle; a his poin all ansi ions beha e as K1–se e s, so ha he
mean cycle ime is gi en by he sum o he fi ing imes o all ansi ions,
di ided by he o al numbe o cus ome s in he main loop K1; mo eo e
he delay ime o he ansi ions belonging o class C1is simply gi en
by S1= j∈C1sj. Now i we inc ease he numbe o okens in he main
loop om K1 o K2, he delay ime o C1canno inc ease, so ha he
con ibu ion o C1 o he mean cycle ime canno exceed S1 o each o
he fi s K1 okens. Unde he hypo hesis ha he h oughpu o he
sys em is gi en by he in e se o Γmax (i.e., assuming X=1/Γmax),
he a e age numbe o okens o he main loop compu ed using Li le’s
o mula canno exceed N1=XS1, he e o e he a e age numbe o
okens a ailable o fi e ansi ions in C2canno be lowe han
N2=K2−N1=K2
K2−K1
K1 j∈C1sj+ j∈C2sj
 j∈C2sj+K2
K1 j∈C1sj
(3.23)
3.2. Lowe bound on h oughpu 109
On he o he hand, we need only
N2=XS2=K2
S2
 j∈C2sj+K2
K1 j∈C1sj
(3.24)
okens o sus ain h oughpu Xin subne C2, so ha we a e assuming
a delay in C2
S2≤K2−K1
K1
j∈C1
sj+
j∈C2
sj(3.25)
Now we claim ha his is he ac ual maximum delay because he
fi s K1 okens can p oceed a he maximum speed in he whole ne ,
hus expe iencing only delay  j∈C2sjin subne C2, while he emain-
ing K2−K1 okens can also queue up o a elling h ough C1, hus
expe iencing an addi ional delay o 1
K1 j∈C1sjeach.
Now, aking in o accoun ha he li eness bound o a ansi ion o
a ne Ndoes no change in he e e se ne N−1, an analogous esul
o p ope y 3.1.3 o he lowe bound on h oughpu can be de i ed.
P ope y 3.2.1 Le Nbe a s ongly connec ed ma ked g aph and N−1
i s e e se ne . Then, he lowe bounds on h oughpu ob ained o bo h
ne s as in heo em 3.2.2 a e he same.
3.2.3 Reachabili y o he lowe bound
The lowe bound in pe o mance gi en by he compu a ion o 1/Γmax as
defined in heo em 3.2.2 can be shown o be eachable o any ma ked
g aph opology and o some assignemen o p obabili y dis ibu ion
unc ions o he se ice ime o ansi ions, exploi ing he eachabili y
o he i ial bound shown in heo em 3.2.1 o 1–li e ma ked g aphs.
Theo em 3.2.3 Fo any s ongly connec ed ma ked g aph wi h a spec-
ifica ion o he a e age se ice ime sj o each ansi ion j, and o
all 0<≤1, i is possible o assign p obabili y dis ibu ion unc ions
o he ansi ion se ice imes such ha he mean cycle ime is:
Γmax =
m

j=1
sj
L( j)−O()(3.26)
110 CHAPTER 3. Bounds o s ongly connec ed ma ked g aphs
independen ly o he opology o he ne (and hus independen ly o he
po en ial maximum deg ee o pa allelism in insic in he ma ked g aph).
P oo . By cons uc ion, in a e y simila way han in he case o
heo em 3.2.1. The only echnical diffe ence is ha now, wi hou any
loss o gene ali y, we assume fi s o all o enume a e ansi ions in
non-inc easing o de o li eness bound, i.e., ename he ansi ions in
such a way ha ∀ i,
j∈T,i>j =⇒L( i)≤L( j). Then, as in he
case o heo em 3.2.1, we can show ha he associa ion o he amily o
andom a iables xj−1
sj() wi h each ansi ion j∈Tyields exac ly he
mean cycle ime Γmax claimed by he heo em. To gi e he p oo we
conside a sequence o models o de ed by he index o ansi ions, in
which he q h model o he sequence has ansi ions 1,
2,...,
q imed
wi h he andom a iables xj−1
sj(), and all o he ansi ions immedia e
(fi ing in ze o ime); he |T| h model in he sequence ep esen s he
esul ing model ha is expec ed o p o ide he example o eachabili y
o he lowe bound. By induc ion we p o e ha he q h model in he
sequence has a mean cycle ime
Γq=
q

j=1
sj
L( j)−O()(3.27)
Base: q= 1: T i ial since he epe i i e cycle ha cons i u e he
s eady-s a e beha iou o he ma ked g aph con ains only one (L( 1)–
se e ) de e minis ic ansi ion wi h a e age fi ing ime Γ1=s1/L( 1).
Induc ion s ep: q>1: Taking he limi →0, each se e o he
newly imed ansi ion qwill fi e mos o he imes wi h ime ze o,
hus no mally no con ibu ing o he compu a ion o he mean cycle
ime, ha will be jus
Γq−1=
q−1

j=1
sj
L( j)−O()(3.28)
(as in he case o model q−1) wi h p obabili y 1 −q−1. On he o he
hand, each o he se e s o he newly imed ansi ion has a ( e y
small) p obabili y q−1o delaying i s fi ing o a ime sq/q−1, which
is a leas o de o 1/ bigge han any o he fi ing ime in he cycle.
Now i L( q) = 1, hen he p oo is comple ed, since also ∀j>q,
3.2. Lowe bound on h oughpu 111
L( j) = 1 by hypo hesis, and we educe o he induc ion s ep o he
p oo o heo em 3.2.1. Ins ead i L( q)>1 hen we can conside L( q)
consecu i e fi ings o q, and compu e he a e age fi ing ime as he
o al ime o fi e L( q) imes he ansi ion, di ided by L( q). Now i
we conside mconsecu i e fi ings o ins ances o ansi ion qwe ob ain
an a e age delay:
m−1

j=0
(1 −q−1)j(q−1)(m−j)(m−j)sq
(q−1) =sq(1 + O()) (3.29)
The e o e he mean cycle ime o he q h model will be
Γq=(1−O(q−1))Γq−1+sq
L( q)(1+O()) =
q

j=1
sj
L( j)−O().(3.30)
3.2.4 A polynomial algo i hm o compu e he
lowe bound
Fi s o all we ecall (c . p ope y 2.1.14) ha in he case o li e ma ked
g aphs he li eness bound equals he enabling and he s uc u al en-
abling bounds o each ansi ion; hus we p esen a cha ac e iza ion o
he p oblem o he de e mina ion o he s uc u al enabling bound in
e ms o a linea p og amming p oblem, which is known o be sol able
in polynomial ime.
Fo any ansi ion ∈T, he compu a ion o he s uc u al en-
abling bound SE( ) is o mula ed in defini ion 1.2.3, in e ms o p ob-
lem (LPP1). In ha p oblem we can obse e ha he ec o Mis
edundan in he sys em o linea inequali ies, so ha we can emo e
i , ob aining:
SE( ) = maximize k
subjec o M0+C·σ ≥kPRE[ ]
M0+C·σ ≥0,σ≥0
(LPP9)
Al e na i ely, we can swi ch o he dual linea p og amming p ob-
lem:
112 CHAPTER 3. Bounds o s ongly connec ed ma ked g aphs
SE( ) = minimize YT·M0
subjec o YT·C≤0
YT·PRE[ ]=1
Y≥0
(LPP10)
Ma ked g aphs a e consis en ne s wi h a single minimal T-semiflow
which is he ec o 11 (p ope y 2.1.12), so ha he cons ain σ ≥0 can
be elaxed in he p imal p oblem. The effec on he dual p oblem o his
elaxa ion is he ans o ma ion o he fi s cons ain in o YT·C=0.
In o he wo ds, he dual p oblem o he compu a ion o SE( ) can be
ew i en as ollows:
SE( ) = minimize YT·M0
subjec o YT·C=0
YT·PRE[ ]=1
Y≥0
(LPP11)
This linea p og amming p oblem is less complex o sol e wi h he
simplex algo i hm han he o iginal dual p oblem because i in ol es
he in oduc ion o ewe slack a iables.
Fo all s ongly connec ed ma ked g aph he e exis s an elemen a y
P-semiflow o which he op imum o he objec i e unc ion is achie ed,
as shown in heo em 3.1.2. In case o ma ked g aphs, hese elemen a y
P-semiflows can only be elemen a y cycles, so ha we can gi e he
ollowing in e p e a ion o he linea p og amming p oblem (LPP11) in
ne e ms: he li eness bound o a ansi ion o a s ongly connec ed
ma ked g aph is gi en by he minimum numbe o okens con ained in
any cycle o places con aining ansi ion . In a non-s ongly connec ed
ma ked g aph he e can be no such cycle, so ha his numbe can be
infini e.
As final ema ks we can s a e he ollowing:
P ope y 3.2.2 Le N,M
0be a ma ked g aph.
1. Li eness o N,M
0can be a byp oduc o a mo e gene al (poly-
nomial complexi y) compu a ion: N ,M
0is a li e ma ked g aph
i and only i o all ansi ion ,SE( )>0.

1 2
3
4
5
p1
p2
p3
p4
p5
p6
(a)
1 2
4
5
p1
p2
p34 p5
p6
(b) (c)
p3
p4
T3
T12
T45
3.2. Unbounded ma ked g aphs 113
Figu e 3.3: Non-s ongly connec ed ma ked g aphs.
2. I N,M
0is li e and ∃ ∈Tsuch ha SE( )=1, hen ∀ ∈T
belonging o he same cycle deno ed by Yin (LPP11), SE( )=1.
No e ha he applica ion o p ope y 3.2.2.2 educes he compu a-
ional complexi y o he s uc u al enabling bound o all ansi ions.
3.3 Ex ending esul s o unbounded
ma ked g aphs
In he li e a u e on de e minis ically imed ma ked g aph models he
case o non-s ongly connec ed ne s is usually conside ed a i ial ex en-
sion o be le o he imagina ion o he eade [RH80,Mag84]. In his
sec ion we a gue ha he ques ion is less i ial han one can pe cei e
a fi s glance, and in ac we shall de i e some examples ha show
ha “di ec ” ex ensions o he esul s ob ained in he case o s ongly
connec ed ma ked g aphs, in gene al, make no sense. In ac , o he
uppe bound on h oughpu , we ob ain a esul simila o ha p oposed
by F. Baccelli e al. [BBW89], e en hough hei wo k is si ua ed in a
qui e diffe en amewo k.
Example 1. Le us fi s conside as an example he non-s ongly
connec ed ma ked g aph in figu e 3.3.a. Fi s o all we can see ha
114 CHAPTER 3. Bounds o s ongly connec ed ma ked g aphs
ansi ion 3has an infini e li eness bound, so ha in s eady-s a e i
should no con ibu e o he compu a ion o he mean cycle ime. In-
deed, suppose ha 3has a de e minis ic se ice ime o 1000 ime
uni s, while ansi ions 1and 2ha e a de e minis ic se ice ime o
1 ime uni ; hus he cycle 1– 2s a s gene a ing okens a a a e o
one oken e e y 2 ime uni s, so ha ini ially okens accumula e in
place p3. A ime 1001 e en ually he fi s ins ance o ansi ion 3
fi es, and a ha poin we each he s eady-s a e condi ion in which
499 ins ances o fi ing o 3a e concu en ly enabled, wi h a emaining
enabling ime shi ed o wo ime uni s be ween each pai o subsequen
fi ing ins ances. As we can see, he ac ual fi ing a e in s eady-s a e o
ansi ion 3is 1/2 fi ings pe second, i.e., i is de e mined by he mean
cycle ime o ansi ions 1– 2comple ely independen o he se ice
ime o 3i sel . The e o e, om he s eady-s a e pe o mance poin o
iew, ansi ion 3beha es as i i we e an immedia e ansi ion, and
i can be educed by using places p3and p4in o a single place p34,as
shown in figu e 3.3.b.
Now le us conside he beha iou o he o he wo ansi ions 4and
5. Thei ac ual fi ing a e is de e mined bo h by hei own se ice imes
and he a e wi h which he cycle 1– 2is able o p oduce he okens ha
a e consumed by 4 om place p34. Thus he mean cycle ime in s eady-
s a e condi ion o ansi ions 4– 5is gi en by he maximum be ween
he mean cycle ime o 1– 2and he sum o he se ice imes o 4and
5( his sum would be he mean cycle ime o he subne gene a ed by
4and 5i i we e conside ed in isola ion, i.e., he po en ial mean cycle
ime o 4– 5). In he case in which he mean cycle ime o 1– 2we e
g ea e han he one o 4– 5, he numbe o okens a place p34 would
emain bounded and he fi ing a e o 4– 5would be he in e se o he
mean cycle ime o 1– 2. On he o he hand, in he case in which he
mean cycle ime o 1– 2we e less han he one o 4– 5, place p34 would
accumula e okens and ma king p ocess o his place would no be (e en
weakly) e godic. Howe e , fi ing a e o ansi ions 4– 5would be, in
ha case, equal o he in e se o hei po en ial mean cycle ime. In he
case o equali y be ween mean cycle ime o 1– 2and 4– 5, ma king
e godici y a place p34 depends on he p obabili y dis ibu ion o se ice
ime o ansi ions. In he pa icula case o de e minis ic iming, he
ma king p ocess is weakly e godic, while in he case o exponen ially
p1
p2p3p6
p5
p4
p7p10 p11
p8
p9p12
1 2 3 4
5
6 7 8 9
(a) (b)
p3p6
p7p10
T12 T34
T5
T67 T89
3.3. Unbounded ma ked g aphs 115
Figu e 3.4: A mo e gene al non-s ongly connec ed ma ked g aph.
dis ibu ed se ice imes he ma king p ocess is non-e godic (because
he embedded Ma ko p ocess is null- ecu en ).
Example 2. Le us conside he mo e gene al example shown in fig-
u e 3.4.a. Also in his case i is easy o unde s and ha ansi ion 5
gi es no con ibu ion o he s eady-s a e cycle ime because i has an
infini e li eness bound (i beha es as an immedia e ansi ion). How-
e e in his case we canno jus dele e i because o he synch oniza ion
cons ain ha is due o i s mul iple inpu places (p3and p6). On
he o he hand, i is clea ha he wo subne s composed o 1– 2and
3– 4beha e comple ely independen ly o each o he and o he es
o he ne . I he mean cycle imes o hese wo subne s a e no ex-
ac ly equal (le us assume wi hou loss o gene ali y ha he mean
cycle ime o 1– 2is g ea e han ha o 3– 4), hen one o he inpu
places o 5(p6wi h ou assump ion) accumula es an infini e numbe
o okens in s eady-s a e (in o he wo ds, he ma king p ocess a his
place is no e godic); hus i becomes edundan (in s eady-s a e) since
i canno cons ain he enabling condi ion o 5, and i can be dele ed
wi hou al e ing he beha iou o he ne . In he case o exac ly equal
mean cycle imes o he wo subne s ( 1– 2and 3– 4), ma king e god-
ici y depends on he dis ibu ion unc ions associa ed wi h ansi ions.
Fo ins ance, o de e minis ic iming he ma king p ocess a p3and
116 CHAPTER 3. Bounds o s ongly connec ed ma ked g aphs
p6 emains bounded (i.e., i is weakly e godic). On he o he hand,
o exponen ial iming, he ma king o bo h places is a null- ecu en
Ma ko p ocess, hus non-e godic. Dele ing all he places ha become
unbounded in s eady-s a e due o he a e age ansi ion fi ing imes,
we ob ain ha he ne is pa i ioned in disconnec ed subne s ha can
be s udied independen ly o one ano he . O cou se, no only he inpu
bu also he ou pu places o 5(p7and/o p10) may accumula e an
infini e numbe o okens in s eady-s a e, p o ided ha he po en ial
mean cycle imes o hei ou pu ansi ions ( espec i ely, 7and 8) a e
g ea e han he ac ual fi ing ime o 5. In his case, also he ou pu
places become edundan and can be dele ed, and we may s udy he
s eady-s a e beha iou s o he ou disconnec ed subne s in isola ion.
F om he analysis o he abo e examples we can d aw wo consid-
e a ions.
Fi s : Ma king e godici y is no assu ed in he case o non-s ongly
connec ed ma ked g aphs. Places ha ing non-e godic ma k-
ing p ocess can be ound among s uc u ally unbounded places
(places do no belonging o any s ongly connec ed componen )
in wo cases: (1) a e he compa ison be ween he ac ual inpu
fi ing a e and he po en ial fi ing a e o he ou pu s ongly
connec ed componen (example 1), o (2) a e he compa ison
among he ac ual fi ing a e o all s ongly connec ed compo-
nen s being synch onized by a gi en ansi ion (example 2). In
o he wo ds, s ongly connec ed componen s o he ma ked g aph
can be seen as p oduce s o pa s (o da a) o o he componen s
and consume s o pa s ha a e p oduced by o he componen s.
Connec ions among hese p oduce s/consume s a e modelled by
means o places (o buffe s). A place is ma king e godic i he
h oughpu o he co esponding p oduce is less han he se ice
a e o he consume .
Second: The e exis s a pa ial o de ela ion “” among subse s o
ansi ions defined as TiTjiff he fi ing delay o ansi ions in
Tican affec he ac ual fi ing a e o ansi ions in Tjbu no ice
e sa. This pa ial o de ela ion can be compu ed by applying
a s anda d algo i hm o he de i a ion o a condensa ion o he
o iginal ne , as we explain below.
Chap e 4
Bounds o li e and bounded
ee choice ne s
The esul s p esen ed in his chap e ( ha include pa o hose
in [CCS90a] and [CCS90b]) a e an ex ension o li e and bounded
ee choice ne s (see defini ion 2.1.11) o he pe o mance bounds o
s ongly connec ed ma ked g aphs de eloped in he p e ious chap e .
The idea is ha se e al consis en fi ing coun ec o s can be ep o-
duced in s eady-s a e, bu decisions, eely done a ce ain places, a e
comple ely go e ned by he s ochas ic in e p e a ion (in pa icula , by
he ou ing a es) o he ne , and he ec o o isi a ios o ansi ions
can be defined independen ly o he ma king and he se ice imes (see
sec ion 2.1).
In sec ion 4.1 we ocus ou a en ion on h oughpu uppe bounds
o li e and bounded ee choice ne s. Using Li le’s law like in p e ious
chap e and s uc u al linea ma king ela ions, linea p og amming
p oblems a e de i ed whose op imum solu ions a e lowe bounds o
he mean cycle ime o ansi ions. These p oblems include s uc u al
in o ma ion o he ne by means o he (p e-, pos -) incidence ma ices.
All pa ame e s defining s ochas ic in e p e a ion a e summa ized in
he ec o o a e age se ice demands o ansi ions (p oduc s o isi
a ios by a e age se ice imes), which can be efficien ly compu ed o
li e and bounded ee choice ne s (see sec ion 2.1).
Lowe bounds o he s eady-s a e h oughpu a e conside ed in
sec ion 4.2. These bounds a e compu ed om he li eness bounds o
123

124 CHAPTER 4. Bounds o li e and bounded ee choice ne s
ansi ions (ob ained om linea p og amming p oblems in he case o
li e and bounded ee choice ne s) and om he a e age se ice demands
o ansi ions.
The h oughpu uppe bound is shown o be eachable o 1–
bounded ne s o some dis ibu ion unc ions o se ice imes wi h a -
bi a y mean alues and o some conflic esolu ion policy, wi h a bi-
a y long un a es. The lowe bound on h oughpu is eachable o
1–bounded ne s.
4.1 Uppe bounds o he s eady-s a e
h oughpu
The compu a ion o uppe bounds o he h oughpu o ansi ions,
defined as he a e age numbe o fi ings pe ime uni , is conside in
his sec ion, o li e and bounded ee choice ne s.
In sec ion 4.1.1, Li le’s law and s uc u al linea ma king ela ions
a e applied o he de i a ion o linea p og amming p oblems, analo-
gous o ha p esen ed in sec ion 3.1. The bounds ob ained using P-
semiflows (sec ion 4.1.1.2) can be imp o ed aking in o accoun o he
ma king in a ian s de i ed om he concep o ap (sec ion 4.1.1.3),
o a e he addi ion o some implici places o he ne (sec ion 4.1.2).
The bounds de i ed in sec ions 4.1.1 and 4.1.2 a e non- eachable,
in gene al. A eachable h oughpu uppe bound o he case o 1–
bounded ne s is ob ained in sec ion 4.1.3. The idea is he ollowing: a
eachable bound o s ongly connec ed ma ked g aphs was compu ed
in p e ious chap e using he ci cui s o he ne . Such ci cui s can
be in e p e ed in algeb aic e ms o ma ked g aphs as elemen a y P-
semiflows (see heo em 2.1.6.1). This is he eason why we y o de i e
bounds o ee choice ne s om P-semiflows in sec ion 4.1.1.2. O he
na u al ex ension o ci cui s o ma ked g aphs o he case o ee choice
ne s can be ound in he amewo k o g aph heo y: mul ise s o ci -
cui s. F om his app oach, a eachable h oughpu uppe bound can
be de i ed o 1–bounded ne s.
4.1. Uppe bounds on h oughpu 125
4.1.1 Li le’s law and linea ma king ela ions
Le us ecall he sys em o inequali ies (3.6) p esen ed in chap e 3:
Γ(j)M≥PRE ·
D(j)(4.1)
whe e Γ(j)is he mean cycle ime o ansi ion j(i.e., he in e se o i s
h oughpu ), Mis he ec o o limi a e age ma kings, PRE is he
p e-incidence ma ix o he ne , and 
D(j)is he ec o o a e age se ice
demands o ansi ions, wi h componen s 
D(j)
i= (j)
isi,i=1,...,m.
We ema k ha ec o 
D(j)can be efficien ly compu ed o li e and
bounded ee choice ne s, i a e age se ice imes sia e gi en, because
he ec o o isi a ios  (j)can be de i ed o such ne s by sol ing
a linea sys em o equa ions ( ee choice ne s a e FRT-ne s; he e o e,
heo em 2.1.2 can be used).
A goal o his sec ion is he compu a ion o lowe bounds o he
mean cycle ime o ansi ions, based on he inequali y (4.1). Since he
limi a e age ma king Mis unknown, linea ma king ela ions de i ed
om he unde lying ne will be conside ed o achie e his goal:
ZT·M≤k, ∀M∈R(N,M
0),wi h Z≥
0(4.2)
Linea i y is equi ed in he abo e ela ion because, aking in o ac-
coun he defini ion o he limi a e age ma king, a simila inequali y
can be de i ed o M:
ZT·M= lim
τ→∞
1
ττ
0ZT·Mudu ≤lim
τ→∞
1
ττ
0kdu=k(4.3)
In his case, he (unknown) ec o Mcan be subs i u ed in (4.1),
p emul iplied by Z, ob aining:
Γ(j)≥ZT·PRE ·
D(j)
k(4.4)
and so a lowe bound o he mean cycle ime o j.
An addi ional ad an age can be aken o he use o linea ela ions,
since his linea i y will lead, in mos cases, o polynomial complexi y cal-
cula ions, based on linea algeb a and linea p og amming echniques.
126 CHAPTER 4. Bounds o li e and bounded ee choice ne s
4.1.1.1 S uc u al linea ma king ela ions
Since he limi a e age ma king Mis unknown, we can use he app ox-
ima ion gi en by linea ela ions e ified by all eachable ma kings. A
fi s amily o linea ma king ela ions is ob ained conside ing hose be-
ing s uc u ally cha ac e ized. These a e s onge condi ions han hose
exp essed by inequali y (4.2) (beha iou ally defined), bu hey p o ide
easie and mo e efficien echniques o hei manipula ion. S uc u al
linea ma king ela ions can be exp essed using he incidence ma ix C
o he ne :
YT·C=0,Y ≥0=⇒YT·M=YT·M0,∀M∈R(N,M
0),∀M0(4.5)
YT·C≤
/0,Y ≥0=⇒YT·M≤YT·M0,∀M∈R(N,M
0),∀M0(4.6)
YT·C≥
0,Y ≥0=⇒YT·M≥YT·M0,∀M∈R(N,M
0),∀M0(4.7)
Le us conside fi s ly he case o equali y ela ion gi en by equa-
ion (4.5). Vec o s Y≥0 e i ying his equa ion a e o en called con-
se a i e componen s o P-semiflows (see sec ion 1.2.2), and hey ha e
been used o he compu a ion o h oughpu uppe bounds o s ongly
connec ed ma ked g aphs, in sec ion 3.1.1, by p emul iplying he in-
equali y (4.1). The ob ained esul s using P-semiflows as well as hei
limi a ions o he compu a ion o eachable (i.e., igh ) bounds o li e
and bounded ee choice ne s a e summa ized in he nex sec ion.
Rega ding s uc u al linea inequali y ela ions o he eachable
ma kings o a ma ked Pe i ne , ec o s Y≥0 e i ying (4.6) could
be conside ed. P emul iplying he linea s a e equa ion o he ne by
such ec o s, he ollowing sequence o inequali ies is ob ained o each
sequence o successo ma kings, and o all ini ial ma king M0:
YT·M0≥···≥YT·Mi−1≥YT·Mi≥YT·Mi+1 ≥··· (4.8)
Mo eo e , YT·C= 0 implies ha he e exis s (a leas ) a ansi ion
jsuch ha YT·C[ j]<0, and i Mi[ jMi+1 hen YT·Mi>YT·Mi+1
in he sequence o inequali ies (4.8) (i.e., s ic inequali y). Bu in his
case he ne canno be li e (because i i was li e hen ansi ion j
could be fi ed an infini e numbe o imes, an infini e numbe o s ic
4.1. Uppe bounds on h oughpu 127
inequali ies would appea in (4.8), and his is impossible i he ini ial
ma king is fini e). Thus, linea inequali ies o he o m YT·C≤
/0 a e
no use ull o us.
Non-nega i e ec o s sa is ying he inequali y (4.7): ZT·C≥
0
canno be used di ec ly o he subs i u ion o Min (4.1) (because
hey gi e inequali ies in he opposi e di ec ion). P-semiflows Ycould
be conside ed such ha Y−Z≥0, hus:
(Y−Z)T·C=YT·C
  
0
−ZT·C≤
/0(4.9)
Bu he exis ence o such ec o s Y−Z≥0, (Y−Z)T·C≤
/0,
is no possible o conse a i e ne s (and s uc u ally li e s uc u ally
bounded ne s a e conse a i e; see, e.g., [Sil85]).
Al e na i ely, o he linea ma king inequali ies o he o m YT
Θ·M≥
1, o all (non- ansien ) ma king Mcan be de i ed conside ing ec o s
YΘ≥0 ha ing a ap Θ as suppo . T aps a e se s o places which e-
main ma ked once hey ha e gained a leas one oken. This s uc u al
concep can be used o imp o e he h oughpu uppe bound compu ed
by means o Li le’s law and P-semiflows, and will be explained la e .
4.1.1.2 Li le’s law and P-semiflows
P-semiflows Ya e non-nega i e le annulle s o he incidence ma ix
C(i.e., YT·C=0, husYT·M=YT·M0 o all eachable ma king
M). Now, using ela ion (4.4), he ollowing lowe bound o he mean
cycle ime o a gi en ansi ion jcan be de i ed:
Γ(j)≥max
Y∈{P−semi low}
YT·PRE ·
D(j)
YT·M0
(4.10)
The p e ious lowe bound can be o mula ed in e ms o a ac-
ional p og amming p oblem and la e , a e some conside a ions (see
sec ion 3.1.1), ans o med in o a linea p og amming p oblem:
Theo em 4.1.1 Fo any ne , a lowe bound o he mean cycle ime
o ansi ion jcan be compu ed by he ollowing linea p og amming
128 CHAPTER 4. Bounds o li e and bounded ee choice ne s
p oblem:
Γ(j)≥ΓPS
(j)=maximize YT·PRE ·
D(j)
subjec o YT·C=0
YT·M0=1
Y≥0
(LPP12)
I he solu ion o he p oblem (LPP12) is unbounded, since i is a
lowe bound o he mean cycle ime o ansi ion j, he non-li eness
can be assu ed (infini e cycle ime). I he isi a ios o all ansi-
ions a e non-null, hen 
D(j)>0, and he unboundedness o he abo e
p oblem implies ha a o al deadlock is eached by he ne . This esul
has he ollowing in e p e a ion: i he p oblem (LPP12) is unbounded
hen he e exis s an unma ked P-semiflow, and he ne is non-li e ( e-
call co olla y 2.1.11).
Co olla y 4.1.1 The p oblem (LPP12) has unbounded solu ion iff
∃Y≥
0such ha YT·M0=0and YT·C=0. Mo eo e , i his
occu s, he ne is non-li e.
In o de o in e p e he esul p esen ed in heo em 4.1.1, le us
conside he pa icula case o he s a e machine (see defini ion 2.1.12)
depic ed in figu e 4.1.a. Assume ha s1=1,s2=s3=0,s4=1,
and s5= 2 a e he a e age se ice imes o 1, 2, 3, 4, and 5, e-
spec i ely, and ha ou ing a es sol ing he conflic a place p2a e
2= 3=1/2 o he fi ing o ansi ions 2and 3. In his case, he
ec o o isi a ios o ansi ions is  (1) =(1,1/2,1/2,1/2,1/2)T,
hus he ec o o a e age se ice demands is 
D(1) =(1,0,0,1/2,1)T.
The unique elemen a y P-semiflow is Y1=(1,1,1,1)T, and i is such
ha YT
1·M0= 3. The e o e, he applica ion o heo em 4.1.1 gi es he
alue ΓPS
(1) =(1+1/2+1)/3=0.8333. In ac , in his case he ob ained
alue is he exac mean cycle ime o ansi ion 1, independen ly o he
p obabili y dis ibu ion o se ice imes. As we ema ked in chap e 1,
s a e machines a e he Pe i ne coun e pa o classical queueing ne -
wo ks. Since we assume infini e se e seman ics o ansi ions, he ne
o figu e 4.1.a is isomo phic o a queueing ne wo k wi h delay s a ions,
and in his case he cycle ime is easily ob ained as he sum o all he

p1
1p2
2
3
p3
p4
4
5
p1
1
p3
p4
4
5
p2
p5
p6
2
3
(a) (b)
4.1. Uppe bounds on h oughpu 129
Figu e 4.1: Queueing ne wo ks wi h: (a) only delay nodes and (b) delay
and single-se e nodes, ep esen ed by means o (a) a s a e machine
and (b) a ee choice ne .
a e age se ice demands di ided by he numbe o cus ome s, because
no queueing akes place a any node.
Now, le us conside he ne o figu e 4.1.b, in which s a ions ep-
esen ed by ansi ions 4and 5a e single-se e s ins ead o delay
nodes (wi h queueing e minology) o , in o he wo ds, ha e hei li e-
ness bounds limi ed o one (wi h ou no a ion). In his case, he ele-
men a y P-semiflows a e Y1=(1,1,1,1,0,0)T,Y2=(0,0,0,0,1,0)T,
and Y3=(0,0,0,0,0,1)T, wi h YT
1·M0=3,YT
2·M0= 1, and
YT
3·M0= 1. The e o e, he p oblem (LPP12) gi es he alue
ΓPS
(1) = max{(1+1/2+1)/3,1/2,1}= max{0.8333,0.5,1}= 1, and
i s in e se, which is he h oughpu uppe bound, is also 1. In a queue-
ing heo y amewo k, he ob ained bound is known as he asymp o ic
h oughpu uppe bound [Kle76,DB78] and is ob ained as he minimum
be ween (a) he bound compu ed assuming ha no queueing akes place
a any node (0.8333, in his case), and (b) he maximum h oughpu
o he bo leneck s a ion ( ansi ion 5in he figu e) which canno ha e
an u iliza ion a e g ea e han 1.
In he gene al ee choice ne s case, he bound p esen ed in heo-
em 4.1.1 can be in e p e ed as he maximum among he asymp o ic
bounds ob ained o he isola ed subne s gene a ed by all he elemen-
1 2
3 4
5
p1
p2p3
p4p5
q1-q
130 CHAPTER 4. Bounds o li e and bounded ee choice ne s
Figu e 4.2: The h oughpu uppe bound gi en by (LPP12) is
non- eachable.
a y P-semiflows o he ne .
Linea p og amming p oblems gi e an easy way o de i e esul s
and in e p e hem. Jus looking a he p oblem (LPP12) he ollow-
ing mono onici y p ope y is ob ained, analogous o ha ob ained o
ma ked g aphs (p ope y 3.1.1).
Co olla y 4.1.2 Le N,M
0be a li e and bounded ee choice ne and
s he ec o o a e age se ice imes.
i) Fo a fixed s,i M
0≥M0(i.e., inc easing he numbe o ini-
ial esou ces) hen he lowe bound o he mean cycle ime o
N,M
0,sis less han o equal o he one o N,M
0,s(i.e.,
ΓPS
(j)≤ΓPS
(j)).
ii) Fo a fixed M0,i 
s≤s (i.e., o as e esou ces) hen he lowe
bound o he mean cycle ime o N,M
0,
sis less han o equal
o he one o N,M
0,s(i.e., ΓPS
(j)≤ΓPS
(j)).
Pe o mance mono onici y does no hold o non- ee choice ne s
inc easing he numbe o ini ial esou ces, as was shown wi h he li e
ne in figu e 2.6 ( o which he addi ion o one oken makes i non-li e).
Fo s ongly connec ed ma ked g aphs, he bound de i ed om he-
o em 4.1.1 has been shown o be eachable o a bi a y mean alues
and coefficien s o a ia ion associa ed wi h ansi ion se ice imes
4.1. Uppe bounds on h oughpu 131
( heo em 3.1.3). Un o una ely, his is no he case o li e and bounded
ee choice ne s. Le us conside , o ins ance, he li e and 1–bounded
ee choice ne depic ed in figu e 4.2. Le s3and s4be he a e age se -
ice imes associa ed wi h 3and 4, espec i ely. Le 1, 2, and 5be
immedia e ansi ions (i.e., hey fi e in ze o ime). Le q,1−q∈(0,1)
be he ou ing p obabili ies defining he esolu ion o conflic a place
p1. The ec o o isi a ios no malized o 5is
 (5) =(q,1−q,q,1−q,1)T(4.11)
The elemen a y P-semiflows a e
Y1=(1,1,0,0,1)T
Y2=(1,0,1,1,0)T(4.12)
Then, applying he p oblem (LPP12) o his ne , he ollowing lowe
bound o he mean cycle ime o ansi ion 5is ob ained:
Γ(5) ≥max{qs3,(1 −q)s4}(4.13)
while he ac ual cycle ime o his ansi ion is
Γ(5) =qs3+(1−q)s4(4.14)
independen ly o he highe momen s o he p obabili y dis ibu ion
unc ions associa ed wi h ansi ions 3and 4. The e o e, he bound
gi en by heo em 4.1.1 is non- eachable o he ne in figu e 4.2.
In he nex sec ion, we conside o he linea ma king ela ions, de-
i ed om he s uc u al concep o ap, ha can be used o imp o e
he bound o heo em 4.1.1.
4.1.1.3 Li le’s law and aps
A ap in a Pe i ne Nis a subse o places Θ ⊆Psuch ha Θ•⊆•Θ.
A well-known p ope y o hese s uc u al elemen s is ecalled below.
Theo em 4.1.2 [Hac72] Le N,M
0be a ma ked Pe i ne and Θ∈P
a ap. I Θis ini ially ma ked, hen Θis ma ked h oughou he ne ’s
e olu ion.
132 CHAPTER 4. Bounds o li e and bounded ee choice ne s
This p ope y can be exp essed in algeb aic e ms conside ing he
ec o YΘassocia ed wi h a gi en ap Θ, and defined as YΘ(p)=χΘ(p),
o all place p(we deno e χΘ he cha ac e is ic unc ion o he se Θ,
i.e., χΘ(p)=1i p∈Θ, and χΘ(p) = 0 o he wise). I YT
Θ·M0≥1
hen YT
Θ·M≥1 o all ma king M eachable om M0.
Now le us conside he ec o YΘassocia ed wi h a gi en ap Θ o
a ne , and a P-semiflow Ysuch ha Y−YΘ≥0 (i always exis s o
conse a i e ne s). The ollowing linea ela ion can be de i ed:
(Y−YΘ)T·M≤YT·M0−1(4.15)
o all ma king M eachable om M0( hus he same ela ion holds o
M). P emul iplying inequali y (4.1) by Y−YΘ, he ollowing lowe
bound o he mean cycle ime o a ansi ion 1is de i ed:
Theo em 4.1.3 Fo any ne Nand o any ap Θo N, a lowe
bound o he mean cycle ime Γ(j)o ansi ion jis gi en by:
Γ(j)≥ΓΘ
(j)=maximize (Y−YΘ)T·PRE ·
D(j)
YT·M0−1
subjec o YT·C=0
Y−YΘ≥0
YΘ(p)=χΘ(p),∀p∈P
(4.16)
In he nex sec ion we de i e a linea p og amming p oblem o he
compu a ion o an imp o emen o he p e ious bound based on he
concep o implici place.
Going back o he ne in figu e 4.2, he unique minimal ap diffe en
om he P-semiflows is
Θ={p1,p
4,p
5}(4.17)
Conside ing he P-semiflow
Y=(2,1,1,1,1)T(4.18)
we ha e
Y≥YΘ=(1,0,0,1,1)T(4.19)
Bibliog aphy
[AMBB+89] M. Ajmone Ma san, G. Balbo, A. Bobbio, G. Chi-
ola, G. Con e, and A. Cumani. The effec o execu-
ion policies on he seman ics and analysis o s ochas ic
Pe i ne s. IEEE T ansac ions on So wa e Enginee ing,
15(7):832–846, July 1989.
[AMBC84] M. Ajmone Ma san, G. Balbo, and G. Con e. A class
o gene alized s ochas ic Pe i ne s o he pe o mance
e alua ion o mul ip ocesso sys ems. ACM T ansac-
ions on Compu e Sys ems, 2(2):93–122, May 1984.
[AMBC86] M. Ajmone Ma san, G. Balbo, and G. Con e. Pe o -
mance Models o Mul ip ocesso Sys ems. MIT P ess,
Camb idge, USA, 1986.
[AMBCC87a] M. Ajmone Ma san, G. Balbo, G. Chiola, and G. Con e.
Gene alized s ochas ic Pe i ne s e isi ed: Random
swi ches and p io i ies. In P oceedings o he In e na-
ional Wo kshop on Pe i Ne s and Pe o mance Models,
pages 44–53, Madison, WI, USA, Augus 1987. IEEE-CS
P ess.
[AMBCC87b] M. Ajmone Ma san, G. Balbo, G. Chiola, and G. Con e.
Modeling he so wa e a chi ec u e o a p o o ype pa al-
lel machine. In P oceedings o he 1987 SIGMETRICS
Con e ence, Banff, Albe a, Canada, May 1987. ACM.
[AMBCD86] M. Ajmone Ma san, G. Balbo, G. Chiola, and S. Do-
na elli. On he p oduc - o m solu ion o a class o
235

236 BIBLIOGRAPHY
mul iple-bus mul ip ocesso sys em models. Jou nal o
Sys ems and So wa e, 6(1,2):117–124, May 1986.
[BB80] S. C. B uell and G. Balbo. Compu a ional Algo i hms
o Closed Queueing Ne wo ks. Else ie Science Pub-
lishe s B.V. (No h Holland), New Yo k, 1980.
[BBW89] F. Baccelli, N. Bambos, and J. Wal and. Flow analysis
o s ochas ic ma ked g aphs. In P oceedings o he IEEE
Con e ence on Decision and Con ol, 1989.
[BCMP75] F. Baske , K. M. Chandy, R. R. Mun z, and F. Palacios.
Open, closed, and mixed ne wo ks o queues wi h diffe -
en classes o cus ome s. Jou nal o he ACM, 22(2):248–
260, Ap il 1975.
[Bes87] E. Bes . S uc u e heo y o Pe i ne s: The ee choice
hia us. In W. B awe , W. Reisig, and G. Rozenbe g,
edi o s, Ad ances in Pe i Ne s’86 - Pa I, olume 254
o LNCS, pages 168–205. Sp inge -Ve lag, Bad Honne ,
Ge many, Feb ua y 1987.
[BG85] S. C. B uell and S. Ghan a. Th oughpu bounds o gen-
e alized s ochas ic Pe i ne models. In P oceedings o
he In e na ional Wo kshop on Timed Pe i Ne s, pages
250–261, To ino, I aly, July 1985. IEEE-CS P ess.
[BM89] F. Baccelli and A. Makowski. Queueing models o sys-
ems wi h synch oniza ion cons ain s. P oceedings o
he IEEE, 77(1):138–161, Janua y 1989.
[B a83] G. W. B ams. R´eseaux de Pe i: Th´eo ie e P a ique.
T.1. h´eo ie e analyse. Masson, Pa is, 1983. In F ench.
[BT81] A. Be oni and M. To elli. P obabilis ic Pe i ne s and
semi-Ma ko sys ems. In P oceedings o he 2nd Eu o-
pean Wo kshop on Pe i Ne s, pages 59–78, Bad Honne ,
Ge many, Sep embe 1981.
BIBLIOGRAPHY 237
[Buz73] J. P. Buzen. Compu a ional algo i hms o closed queue-
ing ne wo ks wi h exponen ial se e s. Communica ions
o he ACM, 16(9):527–531, Sep embe 1973.
[BV84] E. Bes and K. Voss. F ee choice sys ems ha e home
s a es. Ac a In o ma ica, 21:89–100, 1984.
[CCCS89] J. Campos, G. Chiola, J. M. Colom, and M. Sil a.
Tigh polynomial bounds o s eady-s a e pe o mance
o ma ked g aphs. In P oceedings o he 3 d In e na-
ional Wo kshop on Pe i Ne s and Pe o mance Models,
pages 200–209, Kyo o, Japan, Decembe 1989. IEEE-CS
P ess.
[CCCS90] J. Campos, G. Chiola, J. M. Colom, and M. Sil a. P op-
e ies and pe o mance bounds o imed ma ked g aphs.
Technical epo , Dp o. de Ingenie ´ıa El´ec ica e In-
o m´a ica, Uni e sidad de Za agoza, Spain, July 1990.
[CCS89] J. Campos, G. Chiola, and M. Sil a. P ope ies and
s eady-s a e pe o mance bounds o Pe i ne s wi h
unique epe i i e fi ing coun ec o . In P oceedings o
he 3 d In e na ional Wo kshop on Pe i Ne s and Pe -
o mance Models, pages 210–220, Kyo o, Japan, Decem-
be 1989. IEEE-CS P ess.
[CCS90a] J. Campos, G. Chiola, and M. Sil a. P ope ies and
pe o mance bounds o closed ee choice synch onized
monoclass queueing ne wo ks. Resea ch Repo GISI-
RR-90-2, Dp o. de Ingenie ´ıa El´ec ica e In o m´a ica,
Uni e sidad de Za agoza, Spain, Janua y 1990.
[CCS90b] J. Campos, J. M. Colom, and M. Sil a. Imp o -
ing h oughpu uppe bounds o synch onized queue-
ing ne wo ks. Technical epo , Dp o. de Ingenie ´ıa
El´ec ica e In o m´a ica, Uni e sidad de Za agoza, Spain,
June 1990.
238 BIBLIOGRAPHY
[CCS90c] J. Campos, J. M. Colom, and M. Sil a. Pe o mance
e alua ion o epe i i e au oma ed manu ac u ing sys-
ems. In P oceedings o he Rensselae ’s Second In e na-
ional Con e ence on Compu e In eg a ed Manu ac u -
ing, pages 74–81, Rensselae Poly echnic Ins i u e, T oy,
New Yo k, May 1990. IEEE-CS P ess.
[CCS90d] J. M. Colom, J. Campos, and M. Sil a. On li eness anal-
ysis h ough linea algeb aic echniques. In P oceedings
o Design Me hods Based on Ne s, ESPRIT Basic Re-
sea ch Ac ion 3148, W.G.3, Pa is, F ance, June 1990.
Deli e ables co e ing he pe iod June 1989 o June 1990.
[CCS91] J. Campos, G. Chiola, and M. Sil a. E godici y and
h oughpu bounds o Pe i ne s wi h unique consis en
fi ing coun ec o . IEEE T ansac ions on So wa e En-
ginee ing, Feb ua y 1991. To appea .
[Cha72] K. M. Chandy. The analysis and solu ions o gene al
queueing ne wo ks. In P oceedings o he Six h Anual
P ince on Con e ence on In o ma ion Sciences and Sys-
ems, pages 224–228, P ince on, NJ, USA, Ma ch 1972.
[CHEP71] F. Commone , A. Hol , S. E en, and A. Pnueli. Ma ked
di ec ed g aphs. Jou nal o Compu e and Sys em Sci-
ence, 5(5):511–523, Oc obe 1971.
[Chi87] G. Chiola. A g aphical Pe i ne ool o pe o mance
analysis. In P oceedings o he 3 d In e na ional Wo k-
shop on Modeling Techniques and Pe o mance E alua-
ion, Pa is, F ance, Ma ch 1987. AFCET.
[CHW75] K. M. Chandy, U. He zog, and L. S. Woo. Pa ame -
ic analysis o queueing ne wo ks. IBM Jou nal o Res.
De elop, 19(1):36–42, Janua y 1975.
[Cia89] G. Cia do. Analysis o La ge S ochas ic Pe i Ne Mod-
els. PhD hesis, Depa men o Compu e Science, Duke
Uni e si y, Du ham, NC, 1989.
BIBLIOGRAPHY 239
[CMQV89] G. Cohen, P. Molle , J. P. Quad a , and M. Vio . Al-
geb aic ools o he pe o mance e alua ion o disc e e
e en sys ems. P oceedings o he IEEE, 77(1):39–58,
Janua y 1989.
[Cou77] P. J. Cou ois. Decomposabili y: Queueing and Com-
pu e Sys em Applica ions. Academic P ess, New Yo k,
1977.
[Cox55] D. R. Cox. A use o complex p obabili ies in he heo y
o s ochas ic p ocesses. P oceedings o he Camb idge
Philosophical Socie y, 51(2):313–319, Ap il 1955.
[CS89a] J. Campos and M. Sil a. S eady-s a e pe o mance e al-
ua ion o o ally open sys ems o Ma ko ian sequen ial
p ocesses. In M. Cosna d and C. Gi aul , edi o s, De-
cen alized Sys ems, pages 427–438. No h-Holland, Am-
s e dam, 1990.
[CS89b] J. M. Colom and M. Sil a. Con ex geome y and semi-
flows in P/T ne s. A compa a i e s udy o algo i hms
o compu a ion o minimal p-semiflows. In P oceedings
o he 10 h In e na ional Con e ence on Applica ion and
Theo y o Pe i Ne s, pages 74–95, Bonn, Ge many, June
1989.
[CS89c] J. M. Colom and M. Sil a. Imp o ing he linea ly based
cha ac e iza ion o P/T ne s. In P oceedings o he 10 h
In e na ional Con e ence on Applica ion and Theo y o
Pe i Ne s, pages 52–73, Bonn, Ge many, June 1989.
[DA84] M. Diaz and P. Azema. Pe i ne based models o he
specifica ion and alida ion o p o ocols. In G. Rozen-
be g, H. Gen ich, and G. Roucai ol, edi o s, Ad ances in
Pe i Ne s 1984, olume 188 o LNCS, pages 101–121.
Sp inge -Ve lag, Be lin, Ge many, 1984.
[DB78] P. J. Denning and J. P. Buzen. The ope a ional analysis
o queueing ne wo k models. ACM Compu ing Su eys,
10(3):225–261, Sep embe 1978.
240 BIBLIOGRAPHY
[Deo74] N. Deo. G aph Theo y wi h Applica ions o Enginee ing
and Compu e Science. P en ice-Hall, Englewood Cliffs,
NJ, USA, 1974.
[DLT90] Y. Dalle y, Z. Liu, and D. Towsley. Equi alence, e-
e sibili y and symme y p ope ies in o k/join queue-
ing ne wo ks wi h blocking. Technical epo , MASI 90-
32, Uni e si y Pa is 6, 4 Place Jussieu, Pa is, F ance,
June 1990.
[DMFDD89] M. Di Mascolo, M. Y. F ein, Y. Dalle y, and R. Da id.
Modeling o kanban sys ems using Pe i ne s. In
K. S ecke and R. Su i, edi o s, P oceedings o he
3 d ORSA/TIMS Con e ence on Flexible Manu ac u -
ing Sys ems, pages 307–312. Else ie Science Publishe s
B.V. (No h Holland), 1989.
[E l09] A. K. E lang. The heo y o p obabili ies and ele-
phone con e sa ions. Ny Tidssk i Ma ema ik, 20:33–
39, 1909.
[ES83] D. L. Eage and K. C. Se cik. Pe o mance bound hi-
e a chies o queueing ne wo ks. ACM T ansac ions on
Compu e Sys ems, 1(2):99–115, May 1983.
[ES86] D. L. Eage and K. C. Se cik. Bound hie a chies o
mul iple-class queueing ne wo ks. Jou nal o he ACM,
33(1):179–206, Janua y 1986.
[ES90] J. Espa za and M. Sil a. On analysis and syn hesis o
ee choice sys ems. Technical epo , GISI-RR-90-10,
Dp o. de Ingenie ´ıa El´ec ica e In o m´a ica, Uni e sidad
de Za agoza, Spain, June 1990.
[Esp90] J. Espa za. S uc u e Theo y o F ee Choice Ne s. PhD
hesis, Dp o. de Ingenie ´ıa El´ec ica e In o m´a ica, Uni-
e sidad de Za agoza, Za agoza, Spain, June 1990. Re-
sea ch Repo GISI-90-03.

BIBLIOGRAPHY 241
[FN85a] G. Flo in and S. Na kin. Les ´eseaux de Pe i s ochas-
iques. Technique e Science In o ma iques, 4(1):143–
160, Feb ua y 1985. In F ench.
[FN85b] G. Flo in and S. Na kin. Les ´eseaux de Pe i s ochas-
iques, 1985. Thesis de Doc o a d’E a , Uni e si ´e
Pie e e Ma ie Cu ie, Pa is (in F ench).
[FN86] G. Flo in and S. Na kin. One-place unbounded s ochas-
ic Pe i ne s: E godici y c i e ia and s eady-s a e solu-
ions. Jou nal o Sys ems and So wa e, 6(1,2):103–115,
May 1986.
[FN89a] G. Flo in and S. Na kin. Ma ix p oduc o m solu ion
o closed synch onized queuing ne wo ks. In P oceed-
ings o he 3 d In e na ional Wo kshop on Pe i Ne s
and Pe o mance Models, pages 29–37, Kyo o, Japan,
Decembe 1989. IEEE-CS P ess.
[FN89b] G. Flo in and S. Na kin. Necessa y and sufficien e god-
ici y condi ion o open synch onized queueing ne wo ks.
IEEE T ansac ions on So wa e Enginee ing, 15(4):367–
380, Ap il 1989.
[GN67] W. J. Go don and G. F. Newell. Closed queueing sys-
ems wi h exponen ial se e s. Ope a ions Resea ch,
15:254–265, 1967.
[GN72] R. S. Ga finkel and G. L. Nemhause . In ege P og am-
ming. John Wiley & Sons, 1972.
[GP87] E. Gelenbe and G. Pujolle. In oduc ion o Queuing Ne -
wo ks. John Wiley & Sons, 1987.
[Hac72] M. H. T. Hack. Analysis o p oduc ion schema a by
Pe i ne s. M. S. Thesis , TR-94, M.I.T.,Bos on, USA,
1972.
242 BIBLIOGRAPHY
[Hil88] H. P. Hillion. Timed Pe i ne s and applica ion o mul i-
s age p oduc ion sys ems. In P oceedings o he 9 h Eu-
opean Wo kshop on Applica ions and Theo y o Pe i
Ne s, pages 164–182, Venice, I aly, June 1988.
[HL84] P. Heidelbe ge and S. S. La enbe g. Compu e pe o -
mance e alua ion me hodology. IEEE T ansac ions on
Compu e s, 33(12):1195–1220, Decembe 1984.
[HP89] H. P. Hillion and J. M. P o h. Pe o mance e alua ion
o job-shop sys ems using imed e en -g aphs. IEEE
T ansac ions on Au oma ic Con ol, 34(1):3–9, Janua y
1989.
[HT83] P. Heidelbe ge and K. S. T i edi. Analy ic queueing
models o p og ams wi h in e nal concu ency. IEEE
T ansac ions on Compu e s, 32:73–82, Janua y 1983.
[HV85] M. A. Holliday and M. K. Ve non. A gene alized imed
Pe i ne model o pe o mance analysis. In P oceed-
ings o he In e na ional Wo kshop on Timed Pe i Ne s,
pages 181–190, To ino, I aly, July 1985. IEEE-CS P ess.
[IA89] S. M. R. Islam and H. H. Amma . On bounds o o-
ken p obabili ies in a class o gene alized s ochas ic Pe i
ne s. In P oceedings o he 3 d In e na ional Wo kshop
on Pe i Ne s and Pe o mance Models, pages 221–227,
Kyo o, Japan, Decembe 1989. IEEE-CS P ess.
[Jac63] J. R. Jackson. Jobshop-like queueing sys ems. Manage-
men Science, 10(1):131–142, Oc obe 1963.
[JLL77] N. Jones, L.H. Landwebe , and Y. Lien. Complexi y
o some p oblems in Pe i ne s. Theo e ical Compu e
Science, 4:277–299, 1977.
[Ka 84] N. Ka ma ka . A new polynomial ime algo i hm o
linea p og amming. Combina o ica, 4:373–395, 1984.
BIBLIOGRAPHY 243
[KBB86] K. M. Ka i, B. P. Buckles, and U. N. Bha . A o mal
defini ion o da aflow g aph models. IEEE T ansac ions
on Compu e s, 35(11):940–948, No embe 1986.
[KBB87] K. M. Ka i, B. P. Buckles, and U. N. Bha . Isomo -
phisms be ween Pe i ne s and da aflow g aphs. IEEE
T ansac ions on So wa e Enginee ing, 13(10):1127–
1134, Oc obe 1987.
[Kel76a] T.W. Kelle . Compu e Sys em Models wi h Passi e
Resou ces. PhD hesis, Uni e si y o Texas a Aus in,
Aus in, TX, USA, 1976.
[Kel76b] F. P. Kelly. Ne wo ks o queues. Ad ances on Applied
P obabili y, 8:416–432, 1976.
[Kle75] L. Klein ock. Queueing Sys ems Volume I: Theo y.
John Wiley & Sons, New Yo k, NY, USA, 1975.
[Kle76] L. Klein ock. Queueing Sys ems Volume II: Compu e
Applica ions. John Wiley & Sons, New Yo k, NY, USA,
1976.
[K i84] J. K iz. Th oughpu bounds o closed queueing ne -
wo ks. Pe o mance E alua ion, 4:1–10, 1984.
[Lau87] K. Lau enbach. Linea algeb aic calcula ion o deadlocks
and aps. In K. Voss, H. Gen ich, and G. Rozenbe g,
edi o s, Concu ency and Ne s, pages 315–336. Sp inge -
Ve lag, Be lin, 1987.
[La 89] S. S. La enbe g. A pe spec i e on queueing models o
compu e pe o mance. Pe o mance E alua ion, 10:53–
76, 1989.
[LB86] J.Y. Le Boudec. A BCMP ex ension o mul ise e s a-
ions wi h concu en classes o cus ome s. In P oceed-
ings o PERFORMANCE’86 and ACM SIGMETRICS,
Raleigh, NC, USA, May 1986.
244 BIBLIOGRAPHY
[Li 61] J. D. C. Li le. A p oo o he queueing o mula L=λW.
Ope a ions Resea ch, 9:383–387, 1961.
[LR78] L. H. Landwebe and E. L. Robe son. P ope ies o
conflic - ee and pe sis en Pe i ne s. Jou nal o he
ACM, 25(3):352–364, Ap il 1978.
[LR87] A. A. Laza and T. G. Robe azzi. Ma ko ian Pe i
ne p o ocols wi h p oduc o m solu ion. In P oceed-
ings o he Con e ence on Compu e Communica ions,
pages 1054–1062, Washing on, DC, USA, 1987. IEEE-
CS P ess.
[LZGS84] E. D. Lazowska, J. Zaho jan, G. S. G aham, and K. C.
Se cik. Quan i a i e Sys em Pe o mance. P en ice-
Hall, Inc., Englewood Cliffs, NJ, USA, 1984.
[Mag84] J. Mago . Pe o mance e alua ion o concu en sys-
ems using Pe i ne s. In o ma ion P ocessing Le e s,
18:7–13, 1984.
[Mai87] D. Mailles. Files d’A en e Desc ip i es pou la Modeli-
sa ion de la Synch onisa ion dans les Sys emes In o ma-
iques. PhD hesis, Labo a oi e MASI, Uni . P. e M.
Cu ie, Pa is, F ance, Sep embe 1987. Technical Repo
202 (in F ench).
[MB86] M. Minoux and G. Ba nik. G aphes, Algo i hmes, Logi-
ciels. Dunod In o ma ique, Pa is, F ance, 1986.
[Mol81] M.K. Molloy. On he In eg a ion o Delay and Th ough-
pu Measu es in Dis ibu ed P ocessing Models. PhD
hesis, UCLA, Los Angeles, CA, USA, 1981.
[Mol82] M. K. Molloy. Pe o mance analysis using s ochas ic
Pe i ne s. IEEE T ansac ion on Compu e s, 31(9):913–
917, Sep embe 1982.
[Mol85] M.K. Molloy. Fas bounds o s ochas ic Pe i ne s.
In P oceedings o he In e na ional Wo kshop on Timed