TU
Bra
unsc
hwei
gIn
stitu
t für
Bet
riebs
syst
eme
und
Rec
hner
verb
und
Ver
teilt
e S
yste
me
Pro
f. D
r. S
tefa
n F
isch
er
Kap
itel
9:
Tra
nsa
ktio
nen
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
2
Übe
rblic
k
•E
infü
hrun
g un
d M
otiv
atio
n•
Tra
nsak
tione
n•
Ges
chac
htel
te T
rans
aktio
nen
•S
teue
rung
des
gle
ichz
eitig
en Z
ugrif
fs a
uf
Res
sour
cen
–Lo
cks
–O
ptim
istis
cher
Ans
atz
–V
erw
endu
ng v
on T
imes
tam
ps
•V
erte
ilte
Tra
nsak
tione
n
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
3
Ein
führ
ung
•W
ir ha
ben
im le
tzte
n K
apite
l ber
eits
das
Kon
zept
des
ge
gens
eitig
en A
ussc
hlus
ses
betr
acht
et.
•Z
iel:
eine
bes
timm
te R
esso
urce
sol
l nur
von
ein
em
Clie
nt z
ur s
elbe
n Z
eit b
enut
zt w
erde
n•
Gan
z ge
nere
ll ha
ben
Tra
nsak
tione
n da
ssel
be Z
iel:
Sch
utz
von
Res
sour
cen
vor
glei
chze
itige
m Z
ugrif
f•
Tra
nsak
tione
n ge
hen
jedo
ch n
och
wes
entli
ch w
eite
r:–
Es
ist m
öglic
h, a
uf m
ehre
re R
esso
urce
n in
ein
er e
inzi
gen
atom
aren
Ope
ratio
n zu
zugr
eife
n.
–D
iver
se A
rten
von
Feh
lern
kön
nen
abge
fang
en w
erde
n, s
o da
ss P
roze
sse
in d
en Z
usta
nd v
or B
egin
n de
r A
usfü
hrun
g ei
ner
Tra
nsak
tion
zurü
ckge
setz
t wer
den.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
4
Bei
spie
l für
die
ses
Kap
itel
•W
ir w
olle
n di
e in
die
sem
Kap
itel v
erm
ittel
ten
Kon
zept
e an
hand
ein
es d
urch
gäng
igen
B
eisp
iel e
rläut
ern.
•E
s gi
bt z
wei
Art
en v
on R
esso
urce
n:–
Acc
ount
-Obj
ekte
, die
Abb
uchu
ngen
und
E
inza
hlun
gen
gest
atte
n so
wie
Abf
rage
n un
d Ä
nder
unge
n de
s K
onto
stan
ds–
Bra
nch-
Obj
ekte
, die
ein
e F
ilial
e re
präs
entie
ren
und
es g
esta
tten,
Kon
ten
zu e
rzeu
gen,
Kon
ten
zu
such
en u
nd d
en G
esam
tsta
nd a
ller
Kon
ten
in
dies
er F
ilial
e ab
zufr
agen
.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
5
Sch
nitts
telle
der
Obj
ekte
depo
sit(
amou
nt)
depo
sit a
mou
nt in
the
acco
unt
wit
hdra
w(a
mou
nt)
wit
hdra
w a
mou
nt f
rom
the
acco
unt
getB
alan
ce()
->
am
ount
retu
rn th
e ba
lanc
e of
the
acco
unt
setB
alan
ce(a
mou
nt)
set t
he b
alan
ce o
f th
e ac
coun
t to
amou
nt
crea
te(n
ame)
->
acc
ount
crea
te a
new
acc
ount
wit
h a
give
n na
me
look
Up(
nam
e) -
> a
ccou
ntre
turn
a r
efer
ence
to th
e ac
coun
t wit
h th
e gi
ven
nam
ebr
anch
Tota
l()
-> a
mou
ntre
turn
the
tota
l of
all t
he b
alan
ces
at th
e br
anch
Met
hode
n de
s B
ranc
h-O
bjek
ts
Met
hode
n de
s A
ccou
nt-O
bjek
ts
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
6
Ein
fach
e S
ynch
roni
satio
n
•Im
Acc
ount
-Obj
ektm
üsse
n di
e O
pera
tione
n de
posi
t()
und
with
draw
() a
tom
arau
sgef
ührt
wer
den,
d.h
., si
e dü
rfen
in d
er A
usfü
hrun
g ni
cht u
nter
broc
hen
wer
den.
•
In J
ava
läss
t sic
h da
s au
f ein
fach
e W
eise
unt
er
Ver
wen
dung
des
Sch
lüss
elw
orte
s synchronized
erre
iche
n:public
synchronized
void
deposit(...);
•E
rgeb
nis:
wen
n m
ehre
re T
hrea
dsgl
eich
zeiti
g di
esel
be b
zw. e
ine
ande
re s
ynch
roni
sier
te M
etho
de
dies
es O
bjek
ts b
enut
zen
wol
len,
wird
nur
ein
er
zuge
lass
en; d
ie a
nder
en w
erde
n bl
ocki
ert.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
7
Unt
erst
ützt
es F
ehle
rmod
ell
•La
mps
onfü
hrte
198
1 ei
n F
ehle
rmod
ell,
das
heut
e al
s G
rund
lage
alle
r T
rans
aktio
nsal
gorit
hmen
ver
wen
det w
ird. M
it an
dere
n W
orte
n, e
in A
lgor
ithm
us m
uss
folg
ende
Feh
ler
beha
ndel
n kö
nnen
:–
Feh
ler
beim
Sch
reib
zugr
iff a
uf p
erm
anen
ten
Spe
iche
r–
Ser
ver-
Cra
sh–
Bel
iebi
ge V
erzö
geru
ngen
bei
der
N
achr
icht
enüb
ertr
agun
g
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
8
Tra
nsak
tione
n
•T
rans
aktio
nen
best
ehen
aus
eine
rF
olge
von
Ope
ratio
nen
(Anf
rage
nan
Ser
ver)
, für
die
best
imm
teE
igen
scha
ften
gelte
n–
die
AC
ID-E
igen
scha
ften.
•B
eisp
ielf
ürei
neT
rans
aktio
nin
der
Ban
kanw
endu
ng:
eine
Kun
dew
ill v
ersc
hied
ene
Ope
ratio
nen
auf d
rei
Kon
ten
a, b
und
c a
usfü
hren
. Die
Ope
ratio
nen
solle
noh
neU
nter
brec
hung
ausg
efüh
rtw
erde
n:•
Tra
nsac
tion
T:
a.w
ithdr
aw(1
00);
b.de
posi
t(10
0);
c.w
ithdr
aw(2
00);
b.de
posi
t(20
0);
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
9
Die
AC
ID-E
igen
scha
ften
•A
CID
ist e
in v
on H
ärde
run
d R
eute
r (z
wei
Deu
tsch
e,
imm
erhi
n) v
orge
schl
agen
es A
cron
ym.
•B
edeu
tung
:–
Ato
mic
ity: a
lle O
pera
tione
n de
r T
rans
aktio
n od
er k
eine
–C
onsi
sten
cy: e
ine
Tra
nsak
tion
über
führ
t das
Sys
tem
von
ei
nem
kon
sist
ente
n Z
usta
nd in
den
and
eren
–Is
olat
ion:
jede
Tra
nsak
tion
mus
s vo
n de
r A
usfü
hrun
g an
dere
r T
rans
aktio
nen
unab
häng
ig b
leib
en
–D
urab
ility
: wen
n ei
ne T
rans
aktio
n ab
gesc
hlos
sen
ist,
müs
sen
die
Erg
ebni
sse
auf p
erm
anen
tem
Spe
iche
r ge
sich
ert w
erde
n
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
10
AC
ID(1
): A
tom
icity
und
Dur
abili
ty
•A
tom
icity
und
dura
bilit
yw
ird e
rrei
cht d
urch
die
V
erfü
gbar
keit
wie
derh
erst
ellb
arer
Obj
ekte
. •
Wen
n ei
n S
erve
r-P
roze
ss w
ähre
nd d
er A
barb
eitu
ng
eine
r T
rans
aktio
n ab
stür
zt u
nd d
ann
ein
neue
r P
roze
ss g
esta
rtet
wird
, dan
n m
uss
dies
er d
en a
lten
Zus
tand
der
Obj
ekte
wie
der
lade
n kö
nnen
.•
Wen
n di
e T
rans
aktio
n ab
gesc
hlos
sen
ist,
mus
s da
s O
bjek
t den
neu
en Z
usta
nd r
eprä
sent
iere
n un
d ab
gesp
eich
ert w
erde
n.•
Die
bei
den
ande
ren
Eig
ensc
hafte
n be
trac
hten
wir
etw
as s
päte
r.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
11
Impl
emen
tieru
ng
•F
ür je
de T
rans
aktio
n gi
bt e
s ei
nen
Koo
rdin
ator
, der
de
n A
blau
f ste
uert
.•
Ver
wen
dung
:–
Der
Clie
nt s
tart
et e
ine
Tra
nsak
tion,
wor
aufh
in d
er
Koo
rdin
ator
ein
e T
rans
aktio
ns-I
D a
lloki
ertu
nd z
urüc
kgib
t.–
Dan
n w
erde
n di
e O
pera
tione
n au
sgef
ührt
.–
Am
End
e ru
ft de
r C
lient
ein
clo
seT
rans
actio
n()
auf,
wor
aufh
in d
er K
oord
inat
or a
lle O
bjek
te s
peic
hert
und
ein
e po
sitiv
e od
er n
egat
ive
Abs
chlu
ssm
eldu
ng li
efer
t.–
Der
Clie
nt k
ann
auch
von
sic
h au
s di
e T
rans
aktio
n ab
brec
hen.
•D
ie n
ächs
te F
olie
zei
gt e
in ty
pisc
hes
Inte
rfac
e fü
r ei
nen
solc
hen
Koo
rdin
ator
(m
eist
auc
h al
s T
rans
actio
nM
onito
r be
zeic
hnet
).
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
12
Das
Koo
rdin
ator
-Int
erfa
ce
open
Tra
nsac
tion
() -
> tr
ans;
star
ts a
new
tran
sact
ion
and
deliv
ers
a un
ique
TID
tran
s.
Thi
s id
entif
ier
will
be
used
in th
e ot
her
oper
atio
ns in
the
tran
sact
ion.
clos
eTra
nsac
tion
(tra
ns)
-> (
com
mit
, abo
rt);
ends
a tr
ansa
ctio
n: a
com
mit
retu
rn v
alue
indi
cate
s th
at
the
tran
sact
ion
has
com
mitt
ed; a
n ab
ortr
etur
n va
lue
indi
cate
s th
at it
has
abo
rted
.ab
ortT
rans
acti
on(t
rans
);ab
orts
the
tran
sact
ion.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
13
Bei
spie
l: de
r Ja
va TransactionManager
•F
inde
t sic
h in
java
x.tr
ansa
ctio
n.•
Aus
schn
itt a
us d
er S
chni
ttste
lle:
resume(Transaction tobj)
Res
ume
the
tran
sact
ion
cont
ext a
ssoc
iatio
n of
the
calli
ng th
read
with
the
tran
sact
ion
repr
esen
ted
by
the
supp
lied
Tra
nsac
tion
obje
ct.
void
suspend()
Sus
pend
the
tran
sact
ion
curr
ently
ass
ocia
ted
with
the
calli
ng th
read
and
ret
urn
a T
rans
actio
n ob
ject
that
rep
rese
nts
the
tran
sact
ion
cont
ext b
eing
susp
ende
d.
Transaction
rollback()
Rol
l bac
k th
e tr
ansa
ctio
n as
soci
ated
with
the
curr
ent t
hrea
d
void
getTransaction()
Get
the
tran
sact
ion
obje
ct th
at r
epre
sent
s th
e tr
ansa
ctio
n co
ntex
t of t
he c
allin
g th
read
Transaction
commit()
Com
plet
e th
e tr
ansa
ctio
n as
soci
ated
with
the
curr
ent t
hrea
d
void
begin()
Cre
ate
a ne
w tr
ansa
ctio
n an
d as
soci
ate
it w
ith th
e cu
rren
t thr
ead.
void
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
14
Zus
amm
ensp
iel d
er O
bjek
te
Clie
nt
Clie
nt
Clie
nt
Clie
nt
Koo
rdi-
nato
r
Res
sour
ce(O
bjek
t)
Res
sour
ce(O
bjek
t)
Res
sour
ce(O
bjek
t)
Res
sour
ce(O
bjek
t)
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
15
Impl
emen
tieru
ng d
er T
rans
aktio
ns-I
D
•B
ei je
der
Ope
ratio
n, d
ie e
in C
lient
für
eine
T
rans
aktio
n du
rchf
ührt
, mus
s er
die
T
rans
aktio
ns-I
D a
ngeb
en.
•M
öglic
he Im
plem
entie
rung
en:
–A
ngab
e al
s zu
sätz
liche
r P
aram
eter
in d
en
Ope
ratio
nen,
z.B
.de
posi
t(tr
ans,
am
ount
)–
In M
iddl
ewar
ew
ird d
ie ID
übl
iche
rwei
se im
pliz
it be
i alle
n en
tfern
ten
Auf
rufe
n an
gege
ben,
z.B
. be
im C
OR
BA
Tra
nsac
tion
Ser
vice
. Der
A
nwen
dung
spro
gram
mie
rer
mus
s si
ch d
arum
ni
cht k
ümm
ern.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
16
End
e ei
ner
Tra
nsak
tion
•E
ine
Tra
nsak
tion
kann
in z
wei
Zus
tänd
en
ende
n:–
Com
mitt
ed: d
ie T
rans
aktio
n w
urde
erf
olgr
eich
be
ende
t, al
le O
bjek
te w
urde
n er
folg
reic
h ge
schr
iebe
n–
Abo
rted
: ein
Feh
ler
ist a
ufge
tret
en, d
ie
Tra
nsak
tion
wird
nic
ht e
rfol
grei
ch b
eend
et, a
lle
Obj
ekte
beh
alte
n ih
re Z
ustä
nde
von
vor
dem
B
egin
n de
r T
rans
aktio
n
•F
ehle
r w
erde
n vo
m C
lient
ode
r vo
m S
erve
r au
sgel
öst.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
17
Bei
spie
lefü
rT
rans
aktio
nshi
stor
ien
Suc
cess
ful
Abo
rted
by
clie
ntA
bort
ed b
y se
rver
open
Tra
nsac
tion
open
Tra
nsac
tion
open
Tra
nsac
tion
oper
atio
nop
erat
ion
oper
atio
nop
erat
ion
oper
atio
nop
erat
ion
serv
er a
bort
str
ansa
ctio
nop
erat
ion
oper
atio
nop
erat
ion
ER
RO
Rre
port
ed to
clie
ntcl
oseT
rans
actio
nab
ortT
rans
actio
n
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
18
Ges
chac
htel
te T
rans
aktio
nen
•G
esch
acht
elte
Tra
nsak
tione
n er
wei
tern
das
bis
herig
e (f
lach
e) T
rans
aktio
nsm
odel
l, in
dem
sie
ges
tatte
n,
dass
Tra
nsak
tione
n au
s an
dere
n T
rans
aktio
nen
zusa
mm
enge
setz
t sin
d.•
Die
Tra
nsak
tion
auf d
er h
öchs
ten
Ebe
ne w
ird a
ls to
p-le
velt
rans
actio
nbe
zeic
hnet
, die
and
eren
als
su
btra
nsac
tions
.•
Die
Ver
wen
dung
ges
chac
htel
ter
Tra
nsak
tione
n br
ingt
ei
n ne
ues
Pro
blem
mit
sich
: was
pas
sier
t, w
enn
eine
T
eiltr
ansa
ktio
n ab
gebr
oche
n w
ird?
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
19
Bei
spie
lein
erge
scha
chte
lten
Tra
nsak
tion
T :
top-
leve
l tra
nsac
tion
T 1=
open
Sub
Tra
nsac
tion
T 2=
open
Sub
Tra
nsac
tion
open
Sub
Tra
nsac
tion
open
Sub
Tra
nsac
tion
open
Sub
Tra
nsac
tion
open
Sub
Tra
nsac
tion
T 1:
T 2 :
T 11
: T 1
2:
T 211
:
T 21
:
prov
.com
mit
prov
. com
mit
abor
t
prov
. com
mit
prov
. com
mit
prov
. com
mit
com
mit
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
20
Vor
teile
ges
chac
htel
ter
Tra
nsak
tione
n
•Z
usät
zlic
he N
eben
läuf
igke
it:
–S
ubtr
ansa
ctio
nsau
f der
sel
ben
Hie
rarc
hiee
bene
kön
nen
nebe
nläu
fig a
usge
führ
t wer
den
–B
anke
nbei
spie
l: di
e O
pera
tion
bran
chT
otal
() m
uss
für
säm
tlich
e K
onte
n di
e M
etho
de g
etB
alan
ce()
auf
rufe
n. M
an
könn
te je
den
dies
er A
ufru
fe a
ls U
nter
tran
sakt
ion
star
ten
•U
nabh
ängi
ges
Com
mit
oder
Abo
rt:
–D
adur
ch w
erde
n T
rans
aktio
nen
pote
ntie
ll ro
bust
er (
häng
t vo
n de
r A
nwen
dung
ab)
–D
ie E
ltern
tran
sakt
ion
mus
s je
wei
ls e
ntsc
heid
en, w
elch
e F
olge
ein
Abo
rt d
er U
nter
tran
sakt
ion
habe
n so
ll.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
21
Reg
eln
für
das
Com
mitm
ent
gesc
hach
telte
r T
rans
aktio
nen
•E
ine
Tra
nsak
tion
darf
nur
abg
esch
loss
en w
erde
n,
wen
n ih
r U
nter
tran
sakt
ione
n ab
gesc
hlos
sen
sind
.•
Wen
n ei
ne U
nter
tran
sakt
ion
absc
hlie
ßt,
ents
chei
det
sie
unab
häng
ig, e
ntw
eder
pro
viso
risch
zu
com
itten
oder
end
gülti
g ab
zubr
eche
n.•
Wen
n ei
ne E
ltern
tran
sakt
ion
abbr
icht
, wer
den
auch
al
le S
ubtr
ansa
ktio
nen
abge
broc
hen.
•W
enn
eine
Sub
tran
sakt
ion
abbr
icht
, ent
sche
idet
die
E
ltern
tran
sakt
ion,
was
wei
ter
gesc
hieh
t.•
Wen
n ei
ne E
ltern
tran
sakt
ion
com
mite
dis
t, da
nn
könn
en a
lle p
rovi
soris
ch c
omm
ittet
enU
nter
tran
sakt
ione
n eb
enfa
lls c
omm
ittet
wer
den.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
22
AC
ID (
2): I
sola
tion
und
Con
sist
ency
•D
ie O
pera
tione
n al
ler
Tra
nsak
tione
n m
üsse
n so
syn
chro
nisi
ert
wer
den,
das
s Is
olat
ion
und
Con
sist
ency
erre
icht
wer
den.
•E
infa
chst
e V
aria
nte:
Ser
ielle
Aus
führ
ung
der
Tra
nsak
tione
n
•W
arum
ist d
as n
icht
wün
sche
nsw
ert?
•D
ie P
erfo
rman
ce d
es S
erve
rs w
äre
sehr
sch
lech
t, m
öglic
he
nebe
nläu
fige
Aus
führ
ung
von
Tra
nsak
tione
n w
ürde
nic
ht
berü
cksi
chtig
t.
•Z
ur M
axim
ieru
ng d
er L
eist
ung
wird
des
halb
ver
such
t, di
e N
eben
läuf
igke
it zu
max
imie
ren.
•Z
wei
Tra
nsak
tione
n dü
rfen
neb
enlä
ufig
aus
gefü
hrt w
erde
n,
wen
n di
ese
Aus
führ
ung
dens
elbe
n E
ffek
t hat
wie
die
se
quen
tielle
Aus
führ
ung
–di
e A
usfü
hrun
g he
ißt d
ann
seria
llyeq
uiva
lent
.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
23
Con
curr
ency
Con
trol
•C
oncu
rren
cyC
ontr
olis
t des
halb
die
wic
htig
ste
Auf
gabe
des
Tra
nsak
tions
man
ager
s.•
Auf
gabe
: fin
de m
öglic
hst n
eben
läuf
ige
Abl
aufp
läne
fü
r T
rans
aktio
nen,
ohn
e da
s se
rielle
Ä
quiv
alen
tskr
iteriu
m z
u ve
rletz
en.
•E
s ge
ht a
lso
im w
esen
tlich
en d
arum
, mite
inan
der
in
Kon
flikt
ste
hend
e O
pera
tione
n ko
rrek
t ein
zupl
anen
.•
Zw
ei ty
pisc
he P
robl
eme,
die
ver
mie
den
wer
den
müs
sen:
–Lo
st u
pdat
e
–In
cons
iste
ntre
trie
val
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
24
Das
“lo
st u
pdat
e”-P
robl
em
Tra
nsac
tion
T:
bala
nce
= b
.get
Bal
ance
();
b.se
tBal
ance
(bal
ance
*1.1
);
a.w
ithdr
aw(b
alan
ce/1
0)
Tra
nsac
tion
U:
bala
nce
= b
.get
Bal
ance
();
b.se
tBal
ance
(bal
ance
*1.1
);
c.w
ithd
raw
(bal
ance
/10)
bala
nce
= b
.get
Bal
ance
();
$200
bala
nce
= b
.get
Bal
ance
();
$200
b.se
tBal
ance
(bal
ance
*1.1
);$2
20
b.se
tBal
ance
(bal
ance
*1.1
);$2
20
a.w
ithdr
aw(b
alan
ce/1
0)$8
0
c.w
ithd
raw
(bal
ance
/10)
$280
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
25
Kor
rekt
esIn
terle
avin
g vo
n T
und
U
Tra
nsac
tion
T:ba
lanc
e =
b.g
etB
alan
ce()
b.se
tBal
ance
(bal
ance
*1.1
)a.
wit
hdra
w(b
alan
ce/1
0)
Tra
nsac
tion
U:
bala
nce
= b
.get
Bal
ance
()b.
setB
alan
ce(b
alan
ce*1
.1)
c.w
ithd
raw
(bal
ance
/10)
bala
nce
= b
.get
Bal
ance
()$2
00
b.se
tBal
ance
(bal
ance
*1.1
)$2
20ba
lanc
e =
b.g
etB
alan
ce()
$220
b.se
tBal
ance
(bal
ance
*1.1
)$2
42
a.w
ithd
raw
(bal
ance
/10)
$80
c.w
ithd
raw
(bal
ance
/10)
$278
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
26
Das
“in
cons
iste
nt r
etrie
vals
”-P
robl
em
Tra
nsac
tion
V:
a.w
ithd
raw
(100
)
b.de
posi
t(10
0)
Tra
nsac
tion
W:
aBra
nch.
bran
chT
otal
()
a.w
ithd
raw
(100
);$1
00
tota
l = a
.get
Bal
ance
()$1
00
tota
l = to
tal+
b.ge
tBal
ance
()$3
00
tota
l = to
tal+
c.ge
tBal
ance
()
b.de
posi
t(10
0)$3
00
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
27
Kor
rekt
esIn
terle
avin
g vo
n V
und
W
Tra
nsac
tion
V:
a.w
ithd
raw
(100
);b.
depo
sit(
100)
Tra
nsac
tion
W:
aBra
nch.
bran
chT
otal
()
a.w
ithd
raw
(100
);$1
00
b.de
posi
t(10
0)$3
00
tota
l = a
.get
Bal
ance
()$1
00
tota
l = to
tal+
b.ge
tBal
ance
()$4
00
tota
l = to
tal+
c.ge
tBal
ance
()...
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
28
Kon
flikt
zw
isch
en O
pera
tione
n
•W
as b
edeu
tet e
s, w
enn
zwei
Ope
ratio
nen
zuei
nand
er im
Kon
flikt
ste
hen?
•Ih
r ko
mbi
nier
ter
Effe
kt h
ängt
von
der
R
eihe
nfol
ge a
b, in
der
sie
aus
gefü
hrt w
erde
n.•
Mit
dies
em B
egrif
f läs
st s
ich
serie
lle
Äqu
ival
enz
form
aler
def
inie
ren:
•Z
wei
Tra
nsak
tione
n si
nd g
enau
dan
n se
riell
äqui
vale
nt, w
enn
alle
Paa
re v
on m
itein
ande
r in
Kon
flikt
ste
hend
en O
pera
tione
n de
r be
iden
T
rans
aktio
nen
auf a
llen
betr
offe
nen
Obj
ekte
n in
der
selb
en R
eihe
nfol
ge a
usge
führ
t wer
den.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
29
Art
en v
on O
pera
tione
n
•W
ir be
trac
hten
im fo
lgen
den
vere
infa
chen
d –
Rea
d-O
pera
tione
n(k
eine
Änd
erun
g vo
n D
aten
)–
Writ
e-O
pera
tione
n(Ä
nder
ung
von
Dat
en)
Ope
rati
ons
of d
iffe
rent
tran
sact
ions
Con
flic
tR
easo
n
read
read
No
Bec
ause
the
effe
ct o
f a
pair
of re
adop
erat
ions
does
not
dep
end
on th
e or
der
in w
hich
they
are
exec
uted
read
wri
teY
esB
ecau
se th
e ef
fect
of
a rea
dan
d a
wri
teop
erat
ion
depe
nds
on th
e or
der
of th
eir
exec
utio
nw
rite
wri
teY
esB
ecau
se th
e ef
fect
of
a pa
ir o
f wri
teop
erat
ions
depe
nds
on th
e or
der
of th
eir
exec
utio
n
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
30
Bei
spie
l
•G
egeb
en s
eien
zw
ei T
rans
aktio
nen
wie
folg
t:–
T: x
=re
ad(i)
; writ
e(i,1
0); w
rite(
j,20)
;–
U: y
=re
ad(j)
; writ
e(j,3
0); z
=re
ad(i)
;
•Is
t der
folg
ende
Abl
auf s
erie
ll äq
uiva
lent
? W
arum
bz
w. w
arum
nic
ht?
Tra
nsac
tion
T:
Tra
nsac
tion
U:
x =
rea
d(i)
wri
te(i
, 10)
y =
rea
d(j)
wri
te(j
, 30)
wri
te(j
, 20)
z =
rea
d (i
)
Nic
ht ä
quiv
alen
t!T
gre
ift a
uf i
vor
U z
u,
aber
U g
reift
auf
jvo
r T
zu.
(Bea
chte
: der
Zug
riff
auf e
inze
lne
Obj
ekte
ist j
ewei
lsse
rialis
iert
!)
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
31
Impl
emen
tieru
ng v
on C
oncu
rren
cy C
ontr
ol
•G
ener
al o
rgan
izat
ion
of m
anag
ers
for
hand
ling
tran
sact
ions
.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
32
Alg
orith
men
zur
Con
curr
ency
Con
trol
•E
s ge
ht a
lso
nun
daru
m, e
inen
Abl
aufp
lan
für
zuei
nand
er in
Kon
flikt
ste
hend
e O
pera
tione
n zu
find
en.
•D
rei g
ängi
ge A
nsät
ze:
–Lo
ckin
g–
Opt
imis
ticco
ncur
renc
yco
ntro
l–
Tim
esta
mp
orde
ring
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
33
Lock
ing
•Ä
ltest
e un
d am
wei
test
en v
erbr
eite
te F
orm
der
C
oncu
rren
cyC
ontr
ol•
Ein
fach
ste
Var
iant
e: e
xklu
sive
Loc
ks–
Wen
n ei
n P
roze
ss Z
ugrif
f auf
ein
e R
esso
urce
(ei
n D
aten
obje
kt)
benö
tigt,
bitte
t er
den
Sch
edul
er(ü
ber
den
Tra
nsac
tion
Man
ager
) um
ein
exk
lusi
ves
Lock
–W
enn
er e
s er
halte
n ha
t und
sei
ne A
rbei
t ans
chlie
ßen
d be
ende
t hat
, gib
t er
das
Lock
wie
der
zurü
ck
•A
ufga
be d
es S
ched
uler
s: V
erga
be d
er L
ocks
in e
iner
W
eise
, das
s nu
r se
rielle
äqu
ival
ente
Sch
edul
es
ents
tehe
n•
Bei
spie
l näc
hste
Sei
te: U
mus
s au
f T w
arte
n
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
34
Tra
nsac
tions
Tun
d U
mit
exkl
usiv
enLo
cks
Tra
nsac
tion
T:ba
lanc
e =
b.g
etB
alan
ce()
b.se
tBal
ance
(bal
*1.1
)a.
wit
hdra
w(b
al/1
0)
Tra
nsac
tion
U:
bala
nce
= b
.get
Bal
ance
()b.
setB
alan
ce(b
al*1
.1)
c.w
ithd
raw
(bal
/10)
Ope
rati
ons
Loc
ksO
pera
tion
sL
ocks
open
Tra
nsac
tion
bal =
b.g
etB
alan
ce()
lock
B
b.se
tBal
ance
(bal
*1.1
)op
enT
rans
acti
on
a.w
ithd
raw
(bal
/10)
lock
A
bal =
b.g
etB
alan
ce()
wai
ts f
or T’
slo
ck o
n Bcl
oseT
rans
acti
onun
lock
A, B
lock
B
b.se
tBal
ance
(bal
*1.1
)
c.w
ithd
raw
(bal
/10)
lock
C
clos
eTra
nsac
tion
unlo
ck B
, C
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
35
Tw
o-P
hase
Lock
ing
•B
ekan
nter
Alg
orith
mus
, von
dem
bew
iese
n is
t, da
ss
er s
erie
ll äq
uiva
lent
e S
ched
ules
ers
tellt
, wen
n si
ch
alle
Tra
nsak
tione
n da
ran
halte
n.•
Abl
auf:
–B
ei E
rhal
t ein
er O
pera
tion
op(T
,x):
Prü
fung
ob
Kon
flikt
mit
ande
ren
Ope
ratio
nen,
für
die
scho
n ei
n Lo
ck v
erge
ben
ist.
Fal
ls ja
, wird
op(
T,x
) ve
rzög
ert,
falls
nei
n, b
ekom
mt T
das
Lo
ck fü
r x.
–D
er S
ched
uler
gibt
nie
mal
s ei
n Lo
ck fü
r x
ab, a
ußer
der
Dat
aM
anag
er b
estä
tigt d
ie A
usfü
hrun
g de
r O
pera
tion.
–W
enn
der
Sch
edul
erer
st e
inm
al e
in L
ock
für
T a
bgeg
eben
ha
t, w
ird e
r ni
emal
s ei
n ne
ues
Lock
für
irgen
dein
Dat
um f
ür
T r
eser
vier
en. J
eder
Ver
such
von
T in
die
ser
Hin
sich
t bric
ht
T a
b.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
36
Lock
sbe
im T
wo-
Pha
se L
ocki
ng
•„N
orm
ales
“ T
wo-
phas
e lo
ckin
g: z
uers
t w
erde
n al
le L
ocks
erw
orbe
n un
d da
nn n
ach
und
nach
abg
egeb
en.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
37
Str
ikte
s T
wo-
Pha
se L
ocki
ng
•In
die
ser
Var
iant
e w
erde
n al
le L
ocks
erst
wie
der
abge
gebe
n, w
enn
die
Tra
nsak
tion
been
det i
st.
•V
orte
ile:
–V
on a
nder
en T
rans
aktio
nen
gele
sene
Wer
te s
ind
auf j
eden
F
all e
ndgü
ltig
(d.h
. kei
n sp
äter
es A
bort
meh
r m
öglic
h)
–Lo
ck M
anag
emen
t kan
n un
abhä
ngig
von
der
Tra
nsak
tion
durc
hgef
ührt
wer
den
(bei
nor
mal
em T
wo-
Pha
seLo
ckin
gm
uss
die
Tra
nsak
tion
ents
chei
den,
ob
ein
Lock
frei
gege
ben
wer
den
kann
.
•2P
L un
d S
2PL
könn
enzu
Dea
dloc
ksfü
hren
.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
38
Gra
nula
rität
•Ü
blic
herw
eise
bes
itzt e
in D
aten
serv
er
natü
rlich
ein
e gr
ößer
e M
enge
von
Obj
ekte
n•
Ein
fach
ste
Var
iant
e: e
in e
inzi
ges
Lock
für
alle
D
aten
, Bei
spie
l: ei
n Lo
ck fü
r al
le A
ccou
nts
•O
ffens
icht
lich
kein
e gu
te L
ösun
g•
Gen
erel
l sch
ränk
en e
xklu
sive
Loc
ksdi
e m
öglic
he N
eben
läuf
igke
it zu
seh
r ei
n, w
enn
man
die
Tab
elle
auf
Fol
ie 9
-29
betr
acht
et.
•B
esse
res
Sch
ema:
vie
le k
onku
rrie
rend
e Le
se-
oder
gen
au e
in S
chre
ibzu
griff
(„m
any
read
ers/
sing
lew
riter
“)
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
39
Sha
red
Lock
s
•V
erbe
sser
ung:
bei
rei
nen
read
-Ope
ratio
nen
könn
en
shar
edlo
cks
verw
ende
t wer
den,
die
von
meh
rere
n T
rans
aktio
nen
gete
ilt w
erde
n•
Wen
n nö
tig, k
önne
n re
adlo
cks
zu w
rite
lock
sw
erde
n (p
rom
otio
n), a
llerd
ings
nur
, wen
n si
e ni
cht s
hare
dsi
nd.
•R
egel
n fü
r di
e V
erga
be:
For
one
obj
ect
Loc
k re
ques
ted
read
wri
teL
ock
alre
ady
set
none
OK
OK
read
OK
wai
t
wri
tew
ait
wai
t
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
40
Sha
red
Lock
s in
2P
L
1. W
hen
an o
pera
tion
acc
esse
s an
obj
ect w
ithi
n a
tran
sact
ion:
(a)
If th
e ob
ject
is n
ot a
lrea
dy lo
cked
, it i
s lo
cked
and
the
oper
atio
n pr
ocee
ds.
(b)
If th
e ob
ject
has
a c
onfl
icti
ng lo
ck s
et b
y an
othe
r tr
ansa
ctio
n,th
e tr
ansa
ctio
n m
ust w
ait u
ntil
it is
unl
ocke
d.(c
)If
the
obje
ct h
as a
non
-con
flic
ting
lock
set
by
anot
her
tran
sact
ion,
th
e lo
ck is
sha
red
and
the
oper
atio
n pr
ocee
ds.
(d)
If th
e ob
ject
has
alr
eady
bee
n lo
cked
in th
e sa
me
tran
sact
ion,
the
lock
will
be
prom
oted
if n
eces
sary
and
the
oper
atio
n pr
ocee
ds.
(Whe
re p
rom
otio
n is
pre
vent
ed b
y a
conf
licti
ng lo
ck, r
ule
(b)
isus
ed.)
2. W
hen
a tr
ansa
ctio
n is
com
mitt
ed o
r ab
orte
d, th
e se
rver
unl
ocks
all
obje
cts
it lo
cked
for
the
tran
sact
ion.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
41
Mög
liche
Impl
emen
tieru
ngei
nes
Lock
spu
blic
cla
ss L
ock
{pr
ivat
e O
bjec
t obj
ect;
// th
e ob
ject
bei
ng p
rote
cted
by
the
lock
priv
ate
Vec
tor
hold
ers;
//
the
TID
sof
cur
rent
hol
ders
priv
ate
Loc
kTyp
e lo
ckTy
pe;
//
the
curr
ent t
ype
publ
ic s
ynch
roni
zed
void
acq
uire
(Tra
nsID
tran
s,Lo
ckT
ype
aLoc
kTyp
e){
whi
le(/
*ano
ther
tran
sact
ion
hold
s th
e lo
ck in
conf
licin
gm
ode*
/){
try
{w
ait(
);}c
atch
(In
terr
upte
dExc
epti
one)
{/*.
..*/ }
} if(h
olde
rs.is
Em
pty(
)) {
// n
oT
IDs
hol
d lo
ck
hold
ers.
addE
lem
ent(
tran
s);
lock
Typ
e =
aLoc
kTyp
e;}
else
if(/
*ano
ther
tran
sact
ion
hold
s th
e lo
ck, s
hare
it*/
) ){
if
(/*
this
tran
sact
ion
not a
hol
der*
/)ho
lder
s.ad
dEle
men
t(tr
ans)
; }
else
if (
/* th
is tr
ansa
ctio
n is
a h
olde
r bu
t nee
ds a
mor
e ex
clus
ive
lock
*/)
lock
Typ
e.pr
omot
e();
}}
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
42
Mög
liche
Impl
emen
tieru
ngei
nes
Lock
s
publ
ic s
ynch
roni
zed
void
rel
ease
(Tra
nsID
tran
s ){
hold
ers.
rem
oveE
lem
ent(
tran
s);
// r
emov
e th
is h
olde
r//
setl
ockt
ype
to n
one
noti
fyA
ll()
;}
}
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
43
Dea
dloc
ks
•E
in D
eadl
ock
ist e
in Z
usta
nd, i
n de
m je
des
Mitg
lied
eine
r G
rupp
e vo
n T
rans
aktio
nen
dara
uf w
arte
t, da
ss e
in a
nder
es M
itglie
d ei
n Lo
ck fr
eigi
bt.
•Je
fein
er d
ie G
ranu
larit
ätbe
i der
Con
curr
ency
Con
trol
, des
to g
erin
ger
die
Gef
ahr
von
Dea
dloc
ks.
•F
rage
: kan
n m
an D
eadl
ocks
erke
nnen
bzw
. ve
rhin
dern
?
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
44
Bei
spie
lfür
ein
Dea
dloc
k
Tra
nsac
tion
TT
rans
acti
on U
Ope
rati
ons
Loc
ksO
pera
tion
sL
ocks
a.de
posi
t(10
0);
wri
te lo
ck A
b.de
posi
t(20
0)w
rite
lock
B
b.w
ithdr
aw(1
00)
wai
ts f
or U
’sa.
with
draw
(200
);w
aits
for
T’s
lock
on
Blo
ck o
n A
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
45
Wai
t-F
or-G
raph
•E
in W
ait-
For
-Gra
phw
ird v
erw
ende
t, um
die
W
arte
bezi
ehun
gen
zwis
chen
Tra
nsak
tione
n gr
aphi
sch
zu b
esch
reib
en.
•D
abei
–re
präs
entie
ren
die
Kno
ten
Tra
nsak
tione
n un
d–
die
Kan
ten
die
War
tebe
zieh
unge
n –
es g
ibt e
ine
Kan
te v
on K
note
n T
zu
Kno
ten
U, w
enn
T d
arau
f w
arte
t, da
ss U
ein
Loc
k fr
eigi
bt .
•V
aria
nte:
ste
lle a
uch
die
Lock
sbz
w. O
bjek
te
dar,
auf
die
ein
e T
rans
aktio
n w
arte
t.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
46
Bei
spie
l: W
ait-
For
-Gra
ph fü
r9-
44
BA
Wai
ts fo
r
Hel
d b
y
Hel
d b
y
TU
UT
Wai
ts fo
r
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
47
Allg
emei
n: Z
yklu
sim
Wai
t-F
or-G
raph
•E
s gi
lt: w
enn
im W
ait-
for-
Gra
phei
n Z
yklu
s ex
istie
rt, d
ann
ist d
as S
yste
m in
ein
em
Dea
dloc
k
U
V
T
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
48
Ein
wei
tere
sS
zena
rio
•T
, U u
nd V
teile
n ei
n re
adlo
ck fü
r c,
wäh
rend
W e
in
writ
elo
ck fü
r b
besi
tzt,
auf d
as V
zug
reife
n m
öcht
e.•
Jede
s O
bjek
t war
tet n
ur a
uf e
in O
bjek
t, tr
otzd
em is
t V
in z
wei
Zyk
len.
•Lö
sung
: bre
che
V a
b, d
ann
wer
den
die
Zyk
len
aufg
elös
t
C
T
UV
Hel
d by
Hel
d by
Hel
d by
T
U
V
W
W
B
Hel
d by
Wai
ts fo
r
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
49
Ver
hind
ern
von
Dea
dloc
ks
•E
infa
che
Lösu
ng: e
rwer
be a
m A
nfan
g de
r T
rans
aktio
n di
e Lo
cks
für
alle
ben
ötig
ten
Obj
ekte
•V
erhi
nder
t Dea
dloc
ks, i
st a
ber
zu r
estr
iktiv
•A
ußer
dem
kan
n es
z.B
. bei
inte
rakt
iven
T
rans
aktio
nen
sein
, das
s am
Anf
ang
nich
t be
kann
t ist
, wel
che
Obj
ekte
ben
ötig
t wer
den.
•E
her
selte
n ve
rwen
dete
Lös
ung
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
50
Erk
enne
n vo
n D
eadl
ocks
•D
eadl
ocks
wer
den
am W
ait-
For
-Gra
pher
kann
t: en
thäl
t er
eine
n Z
yklu
s, is
t das
Sys
tem
in e
inem
D
eadl
ock.
•D
azu
kann
der
ent
spre
chen
de S
tand
ard-
Gra
phen
-A
lgor
ithm
us v
erw
ende
t wer
den.
•E
s m
uss
dann
ein
e T
rans
aktio
n he
raus
gesu
cht
wer
den,
der
en A
bbru
ch z
um B
rech
en d
es Z
yklu
s fü
hrt.
•M
öglic
hkei
t: ve
rwen
de T
imeo
uts.
–E
in L
ock
eine
r T
rans
aktio
n is
t für
ein
e be
stim
mte
Zei
t un
verle
tzlic
h; d
anac
h ka
nn e
s ge
broc
hen
wer
den
–E
ine
Tra
nsak
tion
mit
eine
m g
ebro
chen
em L
ock
wird
ab
gebr
oche
n.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
51
Bei
spie
l: T
imeo
ut-E
ntsc
heid
ung
Tra
nsac
tion
TT
rans
acti
on U
Ope
rati
ons
Loc
ksO
pera
tion
sL
ocks
a.de
posi
t(10
0);
wri
te lo
ck A
b.de
posi
t(20
0)w
rite
lock
B
b.w
ithdr
aw(1
00)
wai
ts f
or U
’sa.
with
draw
(200
);w
aits
for
T’s
lock
on B
lock
on A
(tim
eout
ela
pses
)T
’s lo
ck o
n A
beco
mes
vul
nera
ble,
unlo
ck A,
abo
rt T
a.w
ithdr
aw(2
00);
wri
te lo
cks A
unlo
ck A
, B
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
52
Opt
imis
ticC
oncu
rren
cyC
ontr
ol
•E
rken
ntni
s: L
ocki
ngha
t ein
ige
grav
iere
nde
Nac
htei
le:
–Lo
cks
müs
sen
imm
er v
erw
ende
t wer
den,
auc
h w
enn
es g
ar
nich
t nöt
ig w
äre
(z.B
. bei
rei
nen
Rea
ds)
unnö
tiger
O
verh
ead
–G
efah
r vo
n D
eadl
ocks
–R
eduz
ieru
ng d
er N
eben
läuf
igke
it du
rch
spät
es A
bgeb
en v
on
Lock
s
•A
ltern
ativ
e: v
erw
ende
den
opt
imis
tisch
en A
nsat
z,
dass
es
sehr
sel
ten
Kon
flikt
e ge
ben
wird
•A
lle T
rans
aktio
nen
arbe
iten,
als
wär
en s
ie d
ie
einz
igen
.•
Nur
, wen
n ei
n K
onfli
kt a
uftr
itt, m
uss
am E
nde
eine
de
r T
rans
aktio
nen
abge
broc
hen
wer
den
und
dere
n E
rgeb
niss
e ve
rwor
fen
wer
den.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
53
Pha
sen
der
Tra
nsak
tion
1.W
orki
ngP
hase
: di
e T
rans
aktio
n be
sitz
t ein
e ei
gene
Kop
ie d
er
notw
endi
gen
Dat
en u
nd a
rbei
tet a
uf d
iese
n2.
Val
idat
ion
Pha
seN
ach
Abs
chlu
ss d
er O
pera
tione
n de
r T
rans
aktio
n w
ird ü
berp
rüft,
ob
es K
onfli
kte
mit
ande
ren
Tra
nsak
tione
n gi
bt. W
enn
ja, m
üsse
n di
ese
Kon
flikt
e ge
löst
wer
den
3.U
pdat
e P
hase
Wur
de d
ie T
rans
aktio
n va
lidie
rt, w
erde
n di
e D
aten
pe
rman
ent g
emac
ht.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
54
Val
idie
rung
von
Tra
nsak
tione
n
•N
atür
lich
wer
den
auch
hie
r di
e K
onfli
ktre
geln
ve
rwen
det,
um d
ie s
erie
lle Ä
quiv
alen
z m
it al
len
über
lapp
ende
n T
rans
aktio
nen
zu
gara
ntie
ren.
•Ü
berla
ppen
d: T
rans
aktio
nen,
die
noc
h ni
cht
abge
schl
osse
n w
aren
, als
die
neu
e T
rans
aktio
n st
arte
te.
•T
rans
aktio
nen
wer
den
durc
hnum
mer
iert
in
der
Rei
henf
olge
ihre
s E
intr
itts
in d
ie
Val
idie
rung
spha
se. D
as h
eiss
tTige
ht v
or T
j, w
enn
i<j.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
55
Ser
ialis
ierb
arke
itei
ner
Tra
nsak
tion
•D
er V
alid
ieru
ngst
estf
ür e
ine
Tra
nsak
tion
Tv
basi
ert a
uf d
en K
onfli
kten
mit
den
über
lapp
ende
n T
rans
aktio
nen
Ti.
•U
m d
ie S
eria
lisie
rbar
keit
herz
uste
llen,
m
üsse
n di
e fo
lgen
den
Reg
eln
erfü
llt w
erde
n:
Tv
Ti
Rul
e
wri
tere
ad1.
Ti
mus
t not
rea
d ob
ject
s w
ritte
n by
Tv
read
wri
te2.
Tv
mus
t not
rea
d ob
ject
s w
ritte
n by
Ti
wri
tew
rite
3.T
im
ust n
ot w
rite
obj
ects
wri
tten
by T
van
d
Tv
mus
tnot
wri
te o
bjec
ts w
ritte
n by
Ti
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
56
Val
idie
rung
sstr
ateg
ien
•B
ei R
ückw
ärts
valid
ieru
ngw
erde
n di
e R
egel
n
mit
den
Tra
nsak
tione
n üb
erpr
üft,
die
vorh
er in
di
e V
alid
ieru
ngsp
hase
eing
etre
ten
sind
. •
Bei
Vor
wär
tsva
lidie
rung
wer
den
die
Tra
nsak
tione
n ei
nbez
ogen
, die
spä
ter
bego
nnen
hab
en u
nd n
och
aktiv
sin
d.•
Bei
de T
echn
iken
hab
en ih
re A
nwen
dung
en,
mei
st is
t jed
och
Vor
wär
tsva
lidie
rung
vozu
zieh
en.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
57
Tim
esta
mp
Ord
erin
g
•Id
ee: j
ede
Tra
nsak
tion
beko
mm
t ein
en e
inde
utig
enZ
eits
tem
pel t
s(T
)(e
rmitt
elt m
it H
ilfe
von
Lam
port
-Uhr
en)
•Je
de O
pera
tion
eine
r T
rans
aktio
n be
sitz
t die
sen
selb
en
Zei
tste
mpe
l.•
Auß
erde
m b
esitz
t jed
es D
aten
obje
kt e
inen
Le
seze
itste
mpe
l ts R
D(x
) un
d ei
nen
Sch
reib
ezei
tste
mpe
l ts
WR(x
).•
tsR
D(x
) en
thäl
t den
Wer
t ts(
Tl),
wob
ei T
ldi
e T
rans
aktio
n is
t, di
e al
s le
tzte
lese
nd a
uf x
zug
egrif
fen
hat.
•F
ür ts
WR(x
) gi
lt da
ssel
be b
zgl.
der
letz
ten
schr
eibe
nden
T
rans
aktio
n. S
chre
ibzu
griff
e si
nd z
unäc
hst t
enta
tiv, b
is
zum
com
mit.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
58
Kon
flikt
lösu
ng
•S
ituat
ion
1: d
er S
ched
uler
erhä
lt ei
n re
ad(t
,x)
mit
Zei
tste
mpe
l ts.
–W
enn
ts<
tsW
R(x
), d
ann
wur
de d
ie le
tzte
Writ
e-O
pera
tion
nach
dem
Sta
rt v
on T
dur
chge
führ
t T
wird
abg
ebro
chen
–W
enn
ts>
tsW
R(x
), d
ann
darf
das
rea
dst
attfi
nden
. Set
ze
auß
erde
m ts
RD(x
) au
f max
(ts,
tsR
D(x
)).
•S
ituat
ion
2: d
er S
ched
uler
erhä
lt ei
n w
rite(
T,x
) m
it Z
eits
tem
pel t
s.–
Wen
n ts
< ts
RD(x
), d
ann
wird
T a
bgeb
roch
en, d
a ei
ne jü
nger
e T
rans
aktio
n x
gele
sen
hat.
T is
t soz
usag
en z
u sp
ät d
ran.
–W
enn
aber
ts>
tsR
D(x
), d
ann
darf
der
Wer
t von
x g
eänd
ert
wer
den,
da
kein
e jü
nger
e T
rans
aktio
n de
n W
ert g
eles
en h
at.
Set
ze a
ußer
dem
tsW
R(x
) au
f max
(ts,
tsW
R(x
)).
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
59
Bei
spie
l
•D
rei T
rans
aktio
nen
T1,
T2,
T3
•T
1 w
urde
abg
esch
loss
en, b
evor
T2
und
T3
bega
nnen
, d.
h., a
lle r
ead-
und
writ
e-Z
eits
tem
pels
tehe
n au
f ts(
T1)
. •
T2
und
T3
wer
den
nebe
nläu
fig a
usge
führ
t, m
it ts
(T2)
<ts
(T3)
.•
Bet
rach
ten
wir
eini
ge B
eisp
iels
ituat
ione
n (n
ächs
te F
olie
):–
T2
schr
eibt
x, o
hne
dass
T3
bere
its z
ugeg
riffe
n hä
tte (
a) u
nd (
b)–
T2
schr
eibt
x, a
ber
T3
hat v
orhe
r ge
lese
n (c
) od
er g
esch
riebe
n (d
)–
T2
liest
x o
hne
Kon
flikt
(e)
. In
(f)
mus
s T
2 w
arte
n, b
is T
i co
mm
itted
hat.
–T
2 lie
st x
, abe
r T
3 ha
t sch
on c
omitt
ed(g
) bz
w. i
st g
erad
e da
bei
(h)
abor
tT2
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
60
Bei
spie
l
i
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
61
Ver
glei
ch d
er C
oncu
rren
cy-C
ontr
ol-T
echn
iken
•Lo
ckin
g+
Gut
gee
igne
t für
Tra
nsak
tione
n m
it vi
elen
Upd
ates
–B
ei d
omin
iere
nden
Rea
d-O
pera
tione
nis
t Tim
esta
mp
bess
er
•O
ptim
istis
che
Con
curr
ency
Con
trol
+D
eadl
ock-
frei
+M
axim
ale
Aus
nutz
ung
von
Neb
enlä
ufig
keit,
des
halb
seh
r gu
t be
i kon
flikt
frei
en S
ituat
ione
n–
Tra
nsak
tione
n m
üsse
n m
anch
mal
wie
derh
olt w
erde
n (v
or
alle
m s
chw
ierig
unt
er h
oher
Las
t)
•T
imes
tam
ps+
Dea
dloc
k-fr
ei–
Bric
ht T
rans
aktio
nen
auch
ab,
wen
n es
bei
Loc
king
nich
t nö
tig w
äre
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
62
Ver
teilt
e T
rans
aktio
nen
•B
ishe
r ha
ben
wir
Tra
nsak
tione
n be
trac
htet
, di
e au
f Obj
ekte
auf
ein
em e
inzi
gen
Ser
ver
zugr
eife
n.•
Oft
jedo
ch w
erde
n di
e O
bjek
te b
zw.
Ope
ratio
nen
über
meh
rere
Ser
ver
vert
eilt
sein
•B
eisp
iel:
Buc
hung
ein
er R
eise
–F
lug
–H
otel
–
Bus
tran
sfer
s–
Tag
esau
sflü
ge
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
63
Str
uktu
r ve
rtei
lter
Tra
nsak
tione
n
•V
erte
ilte
Tra
nsak
tione
n kö
nnen
wie
deru
m
flach
ode
r ge
scha
chte
lt se
in.
•B
ei e
iner
flac
hen
vert
eilte
n T
rans
aktio
n gr
eift
der
Clie
nt n
ache
inan
der
auf d
ie b
etei
ligte
n S
erve
r zu
.•
Bei
der
Ver
wen
dung
von
Sub
tran
sakt
ione
n ka
nn v
on d
er P
aral
lelit
ät d
er v
ersc
hied
enen
S
erve
r G
ebra
uch
gem
acht
wer
den.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
64
Str
uktu
rve
rtei
lter
Tra
nsak
tione
n
Clie
nt
X Y Z
X Y
M
NT 1 T
2
T 11
Clie
nt
P
TT
12 T 21
T 22
(a)
Fla
t tra
nsac
tion
(b)
Nes
ted
tran
sact
ions
T
T
= P
roze
ss
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
65
Ban
kenb
eisp
iel
a.w
ithdr
aw(1
0)
c.de
posi
t(10
)
b.w
ithdr
aw(2
0)
d.de
posi
t(20
)
Clie
ntA B C
T 1 T2
T3
T4
T
D
X Y Z
T=
open
Tra
nsac
tion
open
Sub
Tra
nsac
tion
a.w
ithdr
aw(1
0);
clos
eTra
nsac
tion
open
Sub
Tra
nsac
tion
b.w
ithdr
aw(2
0);
open
Sub
Tra
nsac
tion
c.de
posi
t(10
);op
enS
ubT
rans
actio
nd.
depo
sit(
20);
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
66
Koo
rdin
atio
n de
r S
erve
r
•Z
ur k
orre
kten
Abw
ickl
ung
der
Tra
nsak
tion
müs
sen
die
Ser
ver
ihre
Akt
ione
n ko
ordi
nier
en.
•D
azu
wird
für
jede
Tra
nsak
tion
ein
Koo
rdin
ator
be
stim
mt (
typi
sche
rwei
se in
ein
em d
er S
erve
r).
•Z
um S
tart
der
Tra
nsak
tion
send
et d
er C
lient
ein
op
enT
rans
actio
n()
an d
en K
oord
inat
or. D
iese
r lie
fert
da
nn e
ine
eind
eutig
e T
rans
aktio
ns-I
D z
urüc
k.•
Der
Koo
rdin
ator
ent
sche
idet
, ob
eine
ver
teilt
e T
rans
aktio
n ab
gebr
oche
n od
er k
orre
kt b
eend
et w
ird.
•E
r ke
nnt a
lle T
eiln
ehm
er, d
ie w
iede
rum
alle
ihn
kenn
en.
•Z
ur K
oope
ratio
n w
ird e
in C
omm
it-P
roto
koll
verw
ende
t.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
67
Bei
spie
lfür
die
Koo
rdin
atio
n
..
Bra
nchZ
Bra
nchX
part
icip
ant
part
icip
ant
C D
Clie
nt
Bra
nchY
BA
part
icip
ant
join
join
join
T
a.w
ithdr
aw(4
);
c.de
posi
t(4)
;
b.w
ithdr
aw(3
);
d.de
posi
t(3)
;
open
Tra
nsac
tion
b.w
ithdr
aw(T
, 3);
clos
eTra
nsac
tion
T =
ope
nTra
nsac
tion
a.w
ithdr
aw(4
);c.
depo
sit(
4);
b.w
ithdr
aw(3
);d.
depo
sit(
3);
clos
eTra
nsac
tion
Not
e: th
e co
ordi
nato
r is
in o
ne o
f the
ser
vers
, e.g
.Bra
nchX
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
68
Com
mit-
Pro
toko
lle
•C
omm
it-P
roto
kolle
gibt
es
seit
den
früh
en
70er
n; d
as b
erüh
mte
Tw
o-P
hase
-Com
mit
wur
de 1
978
von
Jim
Gra
y vo
rges
tellt
(T
urin
g-P
reis
träg
er 1
999)
•A
ufga
be: A
tom
aritä
t der
ver
teilt
en
Tra
nsak
tion
hers
telle
n•
One
-Pha
se C
omm
it-P
roto
kolle
sind
zu
einf
ach;
sie
erla
uben
es
den
bete
iligt
en S
ub-
Tra
nsak
tione
n ni
cht,
eine
n A
bbru
ch a
n de
n K
oord
inat
or z
u m
elde
n, d
er ja
dan
n w
iede
r di
e an
dere
n in
form
iere
n m
üsst
e.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
69
Das
Tw
o-P
hase
-Com
mit-
Pro
toko
ll(2
PC
)
•D
as P
roto
koll
begi
nnt e
rst,
wen
n de
r C
lient
di
e T
rans
aktio
n be
ende
t.•
Auf
teilu
ng d
er P
hase
n–
Pha
se 1
: Der
Koo
rdin
ator
frag
t alle
Bet
eilig
ten,
ob
sie
zum
Com
mit
bere
it si
nd.
–P
hase
2: D
er K
oord
inat
or te
ilt d
en B
etei
ligte
n di
e E
ntsc
heid
ung
(com
mit/
abor
t) m
it un
d fo
rder
t sie
au
f, di
e en
tspr
eche
nden
Maß
nahm
en z
u tr
effe
n.
•B
etra
chte
n w
ir di
e O
pera
tione
n de
s P
roto
kolls
.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
70
Ope
ratio
nen
von
2PC
canC
omm
it?(t
rans
)->
Yes
/ N
oC
all f
rom
coo
rdin
ator
to p
arti
cipa
nt to
ask
whe
ther
it c
an c
omm
it a
tr
ansa
ctio
n. P
artic
ipan
t rep
lies
wit
h it
s vo
te.
doC
omm
it(t
rans
)C
all f
rom
coo
rdin
ator
to p
arti
cipa
nt to
tell
par
tici
pant
to c
omm
it it
s pa
rt o
f a
tran
sact
ion.
doA
bort
(tra
ns)
Cal
l fro
m c
oord
inat
or to
par
tici
pant
to te
ll p
arti
cipa
nt to
abo
rt it
s pa
rt o
f a
tran
sact
ion.
have
Com
mit
ted(
tran
s, p
arti
cipa
nt)
Cal
l fro
m p
arti
cipa
nt to
coo
rdin
ator
to c
onfi
rm th
at it
has
com
mit
ted
the
tran
sact
ion.
getD
ecis
ion(
tran
s) -
> Y
es /
No
Cal
l fro
m p
arti
cipa
nt to
coo
rdin
ator
to a
sk f
or th
e de
cisi
on o
n a
tran
sact
ion
afte
r it
has
vot
ed Y
esbu
t has
sti
ll h
ad n
o re
ply
afte
r so
me
dela
y. U
sed
to
reco
ver
from
ser
ver
cras
h or
del
ayed
mes
sage
s.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
71
Abl
aufd
es P
roto
kolls
Pha
se 1
(vo
ting
pha
se):
1.
The
coo
rdin
ator
sen
ds a
canC
omm
it?
requ
est t
o ea
ch o
f th
e pa
rtic
ipan
ts in
th
e tr
ansa
ctio
n.2.
W
hen
a pa
rtic
ipan
t rec
eive
s a
canC
omm
it?
requ
est i
t rep
lies
wit
h its
vot
e (Y
esor
No)
to th
e co
ordi
nato
r. B
efor
e vo
ting
Yes
, it p
repa
res
to c
omm
it b
y sa
ving
obj
ects
in p
erm
anen
t sto
rage
. If
the
vote
is N
oth
e pa
rtic
ipan
t abo
rts
imm
edia
tely
.P
hase
2 (
com
plet
ion
acco
rdin
g to
out
com
e of
vot
e):
3.
The
coo
rdin
ator
col
lect
s th
e vo
tes
(inc
ludi
ng it
s ow
n).
(a)
If th
ere
are
no f
ailu
res
and
all t
he v
otes
are
Yes
the
coor
dina
tor
deci
des
to c
omm
it th
e tr
ansa
ctio
n an
d se
nds
ado
Com
mit
requ
est
to e
ach
of th
e pa
rtic
ipan
ts.
(b)
Oth
erw
ise
the
coor
dina
tor
deci
des
to a
bort
the
tran
sact
ion
and
send
sdo
Abo
rtre
ques
ts to
all
part
icip
ants
that
vot
ed Y
es.
4. P
artic
ipan
ts th
at v
oted
Yes
are
wai
ting
for
ado
Com
mit
ordo
Abo
rtre
ques
t fr
om th
e co
ordi
nato
r. W
hen
a pa
rtic
ipan
t rec
eive
s on
e of
thes
e m
essa
ges
it
acts
acc
ordi
ngly
and
in th
e ca
se o
f co
mm
it, m
akes
aha
veC
omm
itte
dca
ll a
s co
nfir
mat
ion
to th
e co
ordi
nato
r.P
rof.
Dr.
Ste
fan
Fis
cher
IBR
, TU
Bra
unsc
hwei
gV
erte
ilte
Sys
tem
eK
apite
l 9: T
rans
aktio
nen
9-72
Gra
fisch
eD
arst
ellu
ng
canC
omm
it?
Yes
doC
omm
it
have
Com
mitt
ed
Coo
rdin
ator
1 3
(wai
ting
for
vote
s)
com
mitt
ed
done
prep
ared
to c
omm
it
step
Par
ticip
ant
2 4
(unc
erta
in)
prep
ared
to c
omm
it
com
mitt
ed
stat
usst
epst
atus
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
73
2PC
mit
gesc
hach
telte
n T
rans
aktio
nen
•E
twas
kom
plex
ere
Situ
atio
n:–
Es
gibt
wei
tere
Koo
rdin
ator
en, d
ie d
ie
Unt
ertr
ansa
ktio
nen
verw
alte
n–
Unt
ertr
ansa
ktio
nen
könn
en s
elbs
tänd
ig
ents
chei
den,
ob
ein
AB
OR
T o
der
CO
MM
IT
stat
tfind
et, A
BE
R: d
er je
wei
lige
Koo
rdin
ator
kan
n di
e T
rans
aktio
n au
ch b
ei e
inem
Abb
ruch
ein
er
Unt
ertr
ansa
ktio
n er
folg
reic
h ab
schl
ieß
en
•U
nter
tran
sakt
ione
n fü
hren
des
halb
zun
ächs
t ei
n pr
ovis
oris
ches
Com
mit
aus.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
74
Bei
spie
l(zu
Fol
ie10
-64
(b))
•T
21 u
nd T
22 w
erde
n im
End
effe
kt a
bgeb
roch
en, d
a T
2 ab
gebr
oche
n w
ird.
•W
enn
T e
ntsc
heid
et, t
rotz
dem
zu
com
mitt
en, d
ann
kann
auc
h T
1 un
d da
mit
T12
com
mitt
en.
•E
s w
ird d
ann
ein
2PC
zw
isch
en a
llen
prov
isor
isch
co
mm
ittet
enT
eiln
ehm
ern
ausg
efüh
rt.
1
2
T 11 T 12 T 22T 21
abor
t (at
M)
prov
isio
nal c
omm
it (a
t N)
prov
isio
nal c
omm
it (a
t X)
abor
ted
(at Y
)
prov
isio
nal c
omm
it (a
t N)
prov
isio
nal c
omm
it (a
t P)
T
T
T
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
75
Dis
trib
uted
Dea
dloc
ks
•In
ver
teilt
en T
rans
aktio
nen
wird
auc
h da
s P
robl
em d
er D
eadl
ocks
noch
ein
mal
ein
e S
tufe
sch
wie
riger
ve
rtei
lte D
eadl
ocks
könn
en e
ntst
ehen
.•
Ver
teilt
e D
eadl
ocks
könn
en u
.U. n
icht
am
lo
kale
n W
ait-
For
-Gra
phen
erka
nnt w
erde
n.•
Vie
lmeh
r m
uss
ein
glob
aler
Gra
ph u
nter
such
t un
d di
eser
dan
n au
f Zyk
len
unte
rsuc
ht
wer
den.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
76
Bei
spie
lfür
vert
eilte
sD
eadl
ock
UV
W
d.de
posi
t(10
)lo
ck D
b.de
posi
t(10
)lo
ck B
a.de
posi
t(20
)lo
ck A
at Y
at X
c.de
posi
t(30
)lo
ck C
b.w
ithdr
aw(3
0)w
ait a
t Yat
Z
c.w
ithd
raw
(20)
wai
t at
Z
a.w
ithdr
aw(2
0)w
ait a
t X
A
X
B
YC D
Z
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
77
Der
glob
ale
Wai
t-F
or-G
raph
D
Wai
ts fo
r
Wai
tsfo
r
Hel
d by
Hel
dby
BW
aits
for
Hel
dby
X
Y
Z
Hel
d by
W
UV
AC
W
V
U
(a)
(b)
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
78
Kon
stru
ktio
n de
s gl
obal
en G
raph
en
•D
er g
loba
le W
ait-
For
-Gra
phw
ird a
us d
en lo
kale
n G
raph
en k
onst
ruie
rt.
•E
infa
chst
e Lö
sung
: 1.
Der
zen
tral
e K
oord
inat
or s
amm
elt d
ie lo
kale
n G
raph
en u
nd
kons
trui
ert d
en G
raph
en.
2.A
nsch
ließ
end
unte
rsuc
ht e
r ih
n au
f Dea
dloc
ks.
3.E
r fä
llt e
ine
Ent
sche
idun
g un
d in
form
iert
die
bet
reffe
nden
S
erve
r üb
er d
ie N
otw
endi
gkei
t ein
es
Tra
nsak
tions
abbr
uchs
.
4.G
ehe
zu 1
•N
icht
imm
er g
ut w
egen
der
übl
iche
n P
robl
eme
(Bot
tlene
ck, s
ingl
epo
int o
f fai
lure
)
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
79
Pha
ntom
-Dea
dloc
ks
•E
in P
hant
om-D
eadl
ock
ist e
in e
ntde
ckte
s D
eadl
ock,
da
s in
der
Rea
lität
jedo
ch g
ar n
icht
exi
stie
rt.
•W
oher
kan
n da
s ko
mm
en?
•G
enau
von
dem
Hau
ptpr
oble
m v
erte
ilter
Sys
tem
e,
dass
sic
h ei
n Z
usta
nd z
u ei
nem
geg
eben
en Z
eitp
unkt
ni
cht f
ests
telle
n lä
sst.
•D
as h
eiss
t, de
r W
ait-
For
-Gra
phka
nn e
ine
Mis
chun
g au
s äl
tere
n un
d ne
uere
n D
aten
sei
n; e
in b
ishe
r be
legt
es L
ock
kann
inzw
sich
ensc
hon
wie
der
frei
gege
ben
sein
.•
Kan
n ni
cht p
assi
eren
in 2
PL
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
80
Ver
teilt
e E
rmitt
lung
des
Gra
phen
•E
s gi
bt v
erte
ilte
Alg
orith
men
zur
Erm
ittlu
ng
des
glob
alen
Gra
phen
•A
lgor
ithm
us „
Edg
e C
hasi
ng“
•Id
ee:
–K
onst
ruie
re d
en G
raph
en n
icht
, abe
r ge
be d
en
einz
elne
n S
erve
rn In
form
atio
nen
über
ein
ige
sein
er K
ante
n–
Die
Ser
ver
vers
uche
n Z
ykle
n zu
find
en, i
ndem
sie
„p
robe
s“ e
ntla
ng d
er P
fade
des
Gra
phen
dur
ch
das
Sys
tem
sch
icke
n.–
Ein
e so
lche
Nac
hric
ht e
nthä
lt In
form
atio
nen
über
be
kann
te P
fade
des
Gra
phen
.
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
81
Bei
spie
l
V
Hel
d by
W
Wai
ts fo
rH
eld
by
Wai
tsfo
r
Wai
ts fo
r
Dea
dloc
kde
tect
ed
U
C
A
B
Init
iati
on
W→
U →
V →
W
W→
U
W→
U →
V
Z
Y
X
X w
eiss
, das
s W
auf
U
war
tet.
Er
gibt
die
Inf
o an
Y w
eite
r.
Y f
ügt d
ie I
nfor
mat
ion
hinz
u, d
ass
U a
uf V
w
arte
t. E
r gi
bt d
ie I
nfo
an Z
wei
ter.
Z s
chlie
ßlic
h fü
gt
hinz
u, d
ass
V a
uf
W w
arte
t und
en
tdec
kt d
en
Zyk
lus
Dea
dloc
k!
Pro
f. D
r. S
tefa
n F
isch
erIB
R, T
U B
raun
schw
eig
Ver
teilt
e S
yste
me
Kap
itel 9
: Tra
nsak
tione
n9-
82
Wei
tere
Lite
ratu
r
•P
. Lew
is e
t al:
Dat
abas
esan
d T
rans
actio
nP
roce
ssio
ng–
An
App
licat
ion-
Orie
nted
App
roac
h, A
ddis
on-W
esle
y, 2
001.