hig ， tak

「マルチメディア通信と分散処理ワークショップJ 平成 1
1年 1
2月
AsynchronousRecoveryPr~tocol i
nDistribut~d ObJect-sased
Systems
KatsuyaTanaka，HiroakiHigaki，and MakotoTakizawa
“
TokyoDenkiUn
i
v
e
r
s
i
t
y
h
i
g，
tak
i}@t
句a
k
凶
i
i
日
l
a
b
.
k
.
d
e
吋
nd討
a
i
.
a
c
.
j
E-mail{katsu，
Wed
i
s
c
u
s
showt
ω
o凶 k
ec
h
e
町c
k
卯
po
i
n
旬i
泊
no
，
凶
b
j
e
c
t
ι
もb
a
嗣
.
s
e
ds
y
s
t
e
m
s
.l
fsomeo
b
j
e
c
ti
sf
a
叫t
y
，
n
o
to
n
l
yt
h
eo
b
j
e
c
tb
u
t
a
.
l
s
oo
t
h
e
ro
b
j
e
c
旬 w
hichh
a
v
er
e
c
e
i
v
e
dm
e
s
s
a
g
e
sfromもh
eo
b
j
e
c
ta
r
e
'r
e
q
u
i
r
e
d色ober
o
l
l
e
dba
.
c
kt
o出 ec
h
e
c
k
p
o
i
n
t
s
.
b
j
e
c
t
・
Weh
a
v
ebeeni
n
t
r
o
d
u
c
e
dac
o
n
c
e
p
to
fobjed-basedc
h
e
c
k
p
o
i
n
t
swhicha
r
es
e
m
a
n
t
i
c
a
l
l
yc
o
n
s
i
s
t
e
n
ti
n出 eo
ba
.
s
edsystemw
h
i
l
ei
n
c
o
n
s
i
s
t
e
I
叫 w
i
t
ht
h
et
r
a
d
i
t
i
o
n
a
lm
e
s
s
a
g
e
b
a
s
e
dd
e
f
i
n
i
t
i
o
n
.l
nt
h
i
sp
a
p
e
r，
wep
r
e
s
e
n
七a
n
a
s
y
n
c
h
r
o
n
o
u
sa
.
lg
o
r
i
t
h
mf
o
rt
a
k
i
n
go
b
j
e
c
t
・b
a
s
e
dc
h
e
c
k
p
o
i
n
t
s剖 nongo
b
j
e
c
t
s
. We8
o
l
s
oshowar
e
s
t
配色i
n
gp
r
o
も
o
c
o
l
も
もh
ecomput8ot
i
o
na
s
y
n
c
h
r
o
n
o
u
s
l
yw
i
ぬo
t
h
e
ro
b
j
e
c
旬.
wheree
a
c
ho
b
j
e
c
tcanr
e
s
t
a
r
1 I
n
t
r
o
d
u
c
t
i
o
n
D
i
s
t
r
i
b
u
t
e
d8
0
p
p
l
i
c
a
もi
o
n
s8
0
r
ecomposedo
fm
u
l
t
i
p
l
eo
b
j
e
c
t
sc
o
o
p
e
r
a
t
i
n
g by e
x
c
h
a
n
g
i
n
g mess8og~s t
h
r
o
u
g
h
communica
.
t
i
o
nn
e
t
w
o
r
k
s
. Theo
b
j
e
c
tp
e
r
f
o
r
mmetho
d
sont
h
eb剖 i
so
fもheremotep
r
o
c
e
d
u
r
ec
8
o
l
l
. On
.r
e
q
u
e
s
tm
e
s
s
8
0
g
ew
i
t
h8
0methodD
p
， o
p
r
e
c
e
i
p
to
fa
i
sp
e
r
f
o
r
m
e
don8
0
no
b
j
e
c
t0 a
J
l
d_
8
0r
e
s
p
ol
!
s
e_
m
e
s
s
a
g
e
w
i
t
ht
h
er
e
s
u
l
to
fopi
ss
e
n
tb8
o
c
k
.Themethodopm
8
0
y
，
no
t
h
e
ro
b
j
e
c
t
s，
.
ie
.i
n
v
o
c
叫i
o
n
so
f
i
n
v
o
k
emethodso
methodsa
r
en
e
s
t
e
d
. Thec
o
n
f
t
i
c
t
i
n
gr
e
l
8
o
t
i
o
n8
o
mong
e
m
a
n
t
i
c
so
fもh
e
t
h
emethodsi
sd
e
f
i
n
e
db槌 edon七hes
o
b
j
e
c
t0 [
4，
1
5
]
.I
fap~ir o
fmethodsOPlandOP2 c
o
n
f
l
i
c
t，
七h
es
t
8
0
t
eo
f0 o
b
t
a
i
n
e
dbyp
e
r
f
o
r
m
i
n
gOPl 叩 d
OP2d
ependsont
h
ecomput8ot
i
o
no
r
d
e
ro
fDplandOP2・
Anapproacht
omakingもhesystemf
a
u
l
t
t
o
l
e
r8
o
n
t
h出 品 e
a
.
chobject0 t80kesacheckpointwherethe
同t
ei
ss
8
0
v
e
di
nもhes
t
a
b
l
es
t
o
r
a
g
el
o
go
fo
.l
f0 i
s
s
，
0i
sr
o
l
l
e
db
a
c
kt
ot
h
ec~ec~l?oint an4出 回 出e
f
a
u
l
t
y
computationon0 i
sr
e
s
t
8
0
r
もe
d
. l
f0 i
sr
o
l
l
e
db8ock，
o
b
j
e
c
t
swhichh
8
0
v
er
e
c
e
i
v
e
dm
e
s
s
8
0
g
e
ss
e
n
tby0h8
o
v
.
e
t~
b
e
-r
o
l
l
e
dbacks
ot
h
8
0
tt
h
e
r
ei
snoorpk
，
anm
essage[
2
]，
.
i
e
.m
e
s
s
8
0
g
e
ss
e
n
tbynoo
b
j
e
c
tb
u
tr
e
c
e
i
v
e
dbysome
o
b
j
e
c
も
.
P
a
p
e
r
s[
1，
2，
7，
9
1
1，
1
4
)d
i
s
c
u
s
showm
u
l
t
i
p
l
eo
b
j
e
c
t
st
a
k
eg
l
o
b
a
l
l
yc
o
n
s
i
s
t
e
n
tc
h
e
c
k
p
o
i
n
t
s
. Kooand
司 presentsynchronousprotocolsf
o
r色
胞
a
k
i
n
Toueg [
町c
k
p
o
i
n
七
旬
sandr
o
l
l
i
n
gbackp
r
o
c
e
s
s
e
s
. Leongand
c
h
e
Agrawal[
9
]p
r
e
s
e
n
tt
h
ec
o
n
c
e
p
t
.o
fs
i
g
n
棋c
a
n
tr
e
q
u
e
s
t
s，
i
.e
. もhes
t
a
t
eo
f8
0
no
b
j
e
c
ti
schangedbyp
e
r
f
o
r
m
i
n
g
eo
b
j
e
c
t0 i
sr
o
l
r
e
dback，
o
n
l
y0か
t
h
er
e
q
u
e
s
t
.l
f吐l
j
e
c
t
swhichh
8
0
v
er
e
c
e
i
v
e
ds
i
g
n
i
f
i
c
a
n
tr
e
q
u
e
s
t
ss
e
n
tby
o8
0
r
e8
o
l
s
or
o
l
l
e
db8
o
c
k
. Thus，叫l
enumbero
fo
b
j
e
c
t
s
i
nt
h
e
t
ober
o
l
l
e
db
8
0
c
kc
8
0
nber
e
d
u
c
e
d
. However，
・b
剖 e
ds
y
s
t
e
m
s，
d
i
f
f
e
r
e
n
tt
y
p
e
so
fmess
8
o
g
e
s，
i
.e
.
o
b
j
e
c
t
r
e
q
u
e
s
tandr
e
s
p
o
n
s
em
e
s
s
8
0
g
e
s8
0
r
ee
x
c
h
8
0
n
g
e
d8omong
七h
eo
b
j
e
c
t
s
. l
nt
h
ep
a
p
e
r[
9
]，出et
r
a
n
s
m
i
s
s
i
o
n
so
f
r
e
q
u
e
s
七sa
ndr
e
s
p
o
n
s
e
s8
0
r
en
o
tc
o
n
s
i
d
e
r
e
dandi
n
v
o
c
a
t
i
o
n
so
fmethodsa
r
en
o
tne
叫e
d
.S
i
n
c
et
h
ec
o
n
s
i
s
C
h
e
c
k
p
o
i
n
t
s8
0
r
ed
e
f
i
n
e
di
nむermso
fm
e
s
s
8
0
g
e
se
x
t
e
n
t旬，ぬed
e
f
i
n
i
t
i
o
ni
sr
e
f
e
r
r
e
dも0 槌
changedamongo
b
j
e
c
m
e
s
s
a
g
e
b
a
s
e
d
.
The8
o
u
t
h
o
r
s[
1
3
]de
五n
eo
b
j
e
c
ιbasedconsistent(0・
c
o
n
s
i
s
t
e
n
t
)
c
h
e
c
k
p
o
i
n
t
sw
hichc
8
0
nbe同 kenb
a
s
e
don
もh
ec
o
n
f
i
i
c
t
i
n
gr
e
l
8
o
t
i
o
namongt
h
emethodsi
nv
a
r
i
o
u
sk
i
n
d
so
fi
n
v
o
c
叫i
o
n
sl
i
k
esy~chronous 8
0
n
da
s
y
n
c
h
r
o
n
9
U
so
n
e
si
no
b
j
e
c
t
b
a
s
e
ds
y
s
t
e
m
sevenもhough
i
もmayb
e
'i
n
c
o
n
s
i
s
t
e
n
tw
i
t
h出 e
.t
r
a
d
i
t
i
o
n
a
lm
e
s
s
a
g
e
b
a
s
e
dd
e
f
i
n
i
t
i
o
n
. H
i
g
a
k
ie
ta
t[
5
]
d
i
s
c
u
s
s8
0
na
s
y
n
c
h
r
o
n
o
u
sc
h
e
c
k
p
o
i
n
t
i
n
gp
r
o
もo
c
o
l
i
n出 em
e
s
s
a
g
e
-b
a
s
e
d
s
y
叫 em
，
whereo
b
j
e
c
旬a.sy
n
c
h
r
o
n
o
u
s
l
yn
o
to
n
l
yt
a
k
e
8
or
t
e
d
. I
n theωyn
・
c
h
e
c
k
p
o
i
n
t
s but a
l
s
oa
r
er
e
s
t
c
h
r
o
n
o
u
sc
h
e
c
k
p
o
i
n
t
s，
t
h
eo
b
j
e
c
t
s~onoも suspend d
u
r
i
n
g出 ec
h
e
c
k
p
o
i
n
t
s
. l
nt
h
i
sp
a
p
e
r，
o
b
j
e
c
t
s
i
n
g同 k
旬 b
e
c
8
0
u
s
eo
b
j
e
c
t
s町 e
a
s
y
n
c
h
r
o
n
o
u
s
l
yt
8
0
k
ec
h
e
c
k
p
o
i
n
r
e
q
u
i
r
e
dもomorefrequentlyt
a
k
ec
h
e
c
k
p
o
i
n
t
st
obe
h
i
g
h
l
ya
v
a
i
l
a
b
l
e
.Wed
i
s
c
u
s
showt
ot
8
0
k
e0・c
o
n
s
i
s
t
e
n
t
c
h
e
c
k
p
o
i
n
t
si
n8
o
n
.a
s
y
n
c
h
r
o
n
o
u
smannerbye
x
t
e
n
d
i
n
g
h
eo
b
j
e
c
t
・b
a
s
e
ds
y
s
t
e
m
.By
t
h
eH
i
g
a
k
i
'
sa
l
g
o
r
i
t
h
mもot
t
h
e0・c
o
n
s
i
s
t
e
n
tc
h
e
c
k
p
o
i
川 町 出en
umbero
fc
h
e
c
k
k
e
nbyo
b
j
e
c
旬 c
8
0
nQer
e
d
u
c
e
d
.
p
o
i
n
t
s七a
wef
i
r
凶 p
r
e
s
e
n
も
もh
esystemmode
l
.I
n
I
ns
e
c
t
i
o
n2，
s
e
c
t
i
o
n3，
wed
i
s
c
u
s
sぬei
n
f
l
u
e
n
t
i
8
0
lm
e
s
s
8
0
g
e
sandd
e
・
f
i
n
et
h
eo
b
j
e
c
t
b
a
s
e
dc
h
e
c
k
p
o
i
n
t
.l
ns
e
c
t
i
o
n
s4
'
a
n
d5，
weshowap
r
o
t
o
c
o
lf
o
rt
a
k
i
n
g0・c
o
n
s
i
凶e
n
tc
h
e
c
k
p
o
i
n
t
s
同.
r
t
i
n
gt
h
eo
b
j
e
c
回.
andr
e
s
2 SystemModel
2
.
1 O
bjects
Ad
i
s
t
r
i
b
u
t
e
ds
y
s
t
e
mi
scomposedo
fm
u
l
t
i
p
l
eo
b
j
e
c
t
s
.
Eacho
b
j
e
c色 oi
sane
n
c
a
p
s
u
l
a
t
i
o
no
fd
a
t
aandac
o
l
l
e
c
t
i
o
no
fm
e
t
h
o
d
s
.l
nぬi
sp
a
p
e
r，
weassumemethods
a
r
es
y
n
c
h
r
o
n
o
u
s
l
yi
n
v
o
k
e
dbyu
s
i
n
gt
h
er
e
m
o
t
ep
r
o
・
c
e
d
u
r
ec
a
l
l
. Onr
e
c
e
i
p
to
far
e
q
u
e
s
tm
e
s
s
a
g
em w
i
t
h
opi
sp己r
f
o
r
m
e
dont
h
eo
b
j
e
c
七o
.Then，
amethodop，
t
h
er
e
s
p
o
n
s
em
e
s
s
8
0
g
ew
i
t
hむh
e
r
e
s
u
l
もo
fopi
ss
e
n
tba
.
c
k
.
u
凶h
ermorei
nv
o
k
emethodson
Themethodopmayf
o
t
h
e
ro
b
j
e
c旬
，.
ie
.i
n
v
o
c
a
t
i
o
no
fopi
sn
e
s
t
e
d
.
Am
e
s
s
8
0
g
emis8
0
no1'ph.
a
ni
f
fm i
sr
e
c
e
i
v
e
db叫 no
も
s
e
n
ti
nt
h
es
y
s
もe
m.A c
o
n
s
i
s
t
e
n
tg
l
o
b
8
o
lc
h
e
c
k
p
o
i
n
ti
s
d
e
f
i
n
e
d七obeonewhereもh
e
r
ei
snoorphanm
e
s
s
a
g
e[
2
]
.
t
h
esystemi
sreferredω 剖 ~essage-based s
i
n
c
e
H
e
r
e，
8
o
t
i
o
ne
a
.
chm
e
s
s
a
g
ec
8
o
r
i
ti
sn
o
td
i
s
c
u
s
s
e
dwhati
n
f
o
r
m
r
i
e
s
.I
nF
i
g
u
r
e1
，
8
0p
a
i
r
o
fo
b
j
e
c
も
So
ia
nd0; t
a
k
el
o
c
a
l
'，
r
e
s
p
e
c
t
i
v
e
l
y
，
ando
is
e
n
d
sames
c
h
e
c
k
p
o
i
n
t
sc
'叩 dc
s
a
g
em も0 句・ l
nF
i
g
u
r
e1
(
2
)，
ag
l
o
b
a
lc
h
e
c
k
p
o
i
n
t(
c
'，
d)i
si
n
c
o
n
s
i
s
もe
ntb
e
c
a
u
s
em i
s叩 o
r
p
h
a
n
.
，
2
.
2 Typeso
fmethods
L
e
to
p
(s
)denote8
0脚 色 eo
b
t
a
i
n
e
d byp
e
r
f
o
r
m
i
n
g8
0
methodopon8
0s
t
a
t
e
so
f8
0
no
b
j
e
c
to
.o
p
l
a
O
P
2m
e
8
0
n
s
t
h
8
0
t8
0methodOP2 i
sp
e
r
f
o
r
m
e
da
f
t
e
rDpl c
o
m
p
l
e
t
e
s
.
Ap
8
0
i
ro
fmethodsOPl and叩 2o
f8
0
no
b
j
e
c
t0 a
r
ec
omp
a
t
i
b
l
eπ
i OPl。 明 (
s
) OP200Pl(
s
)f
o
re
v
e
r
ys
t
8
0
t
eS o
f
o
n
f
t
i
c
ti
f
fもhey8
0
r
en
o
tcomp
8
o
t
i
b
l
e
.
o[
4
]
.Dpl刷 物 c
色os
u
p
p
o
r
t
stwok
i
n
d
so
fmethods
，
.
ie
:8
0
n
Ano
b
j
e
c
u
p
d
a
t
emethodwhichc
h
a
n
g
e
st
h
e
's
t
a
t
eo
f0 and8
0
non-upd
.
a
t
eo
newhichd
o
e
sn
o
tchange色hes
t
a
t
eo
fo
.
-73ー
，
，
=
F
o
rex
田n
p
l
e，
d
e
p
o
s
i
to
faB
a
n
l
co
b
j
e
c
ti
sanupdate
h
e
c
l
ci
sanon-updateo
n
e
.I
nt
h
i
sp
a
p
e
r，
method嗣 dc
we槌 sumet
h
a
tt
h
et
y
p
e
so
ft
h
emethodsa
r
es
p
e
c
i
f
i
e
d
w
i
t
ht
h
ec
o
n
f
l
i
c
t
i
n
gr
e
l
a
t
i
o
namongt
h
emethodsi
nt
h
e
b
j
e
c
t
.
d
e
f
i
n
i
t
i
o
no
fもheo
吋i
c
i
po
.
t
e
si
name
もh
od01'i
fm i
sa
A messagem pa
r
e
q
u
e
s
to
rr
e
s
p
o
n
s
eo
f0
1
'
.L
e
tOp(m)d
e
n
o
t
eamethod
i
nwhichm p
a
r
t
i
c
i
p
a
t
e
s
.Ano
b
j
e
cも0 s
e
n
d
sar
e
q
u
e
s
t
もh
e
ro
b
j
e
cも0
;・Onr
e
c
e
i
p
to
fmltO
P
2
mlo
fop2もoano
i
sp
e
r
f
o
r
m
e
don町
・ L
e
top~ d
e
n
o
t
e細 川αnceo
fa
methodO1'~， i
.e
.computationo
fOPc
Ii
nOh・Theo
b
j
e
c
t
句 s
e
n
d
sar
e
s
p
o
n
s
em2o
fo~ t
o0.
，Here，
mlandm2
p
a
r
t
i
c
i
p
a
t
ei
n。
局
，i
.
e
.Op(ml) Op(向)=例.
0
;
4
O
1
'
l
ι1.
，
弓
官
，
向
0
.
;
・-c
O3
.
o
i
.
J
u
t
=
3
d
t
i
m
e
F
i
g
u
r
e2
:P
o
s
s
i
b
l
ec
旬.
h
e
c
k
p
o
i
n
色i
me
(
1
)C
o
n
s
i
s
もe
n
t
..(
2
)I
n
c
o
n
s
i
s
t
e
n
t
同:c
h
e
c
k
p
o
i
n
t
F
i
g
u
r
e1
:M
e
s
s
a
g
e
b
a
s
e
dc
h
e
c
k
p
o
i
n
t
s
.
3 O-consistentCheckpoints
Wed
i
s
c
u
s
swhatt
y
p
e
so
fc
h
e
c
k
p
o
i
n
t
scanbet
a
k
e
ni
n
t
h
eo
b
j
e
c
t
b
a
s
e
ds
y
s
t
e
m
.
3
.
1 Message-basedsystem
，
Ano
b
j
e
c
t0 t
a
k
e
sal
o
c
a
lc
h
e
c
k
p
o
i
n
tc
'wheret
h
es
t
a
t
e
ss
t
o
r
e
di
nt
h
el
o
g1(
i 1
，
，
. n).If七heobject
o
f0 i
o
ii
sf
a
u
l
もあ向 i
sr
o
l
l
e
dbackt
ot
h
el
o
c
a
lc
h
e
c
k
p
o
i
n
も
c
'byr
e
s
t
o
r
i
n
gt
h
es
t
a
t
es
t
o
r
e
di
nt
h
el
o
g
Then，
o
t
h
e
ro
b
j
e
c
旬 h
avet
ober
o
l
l
e
dbackt
ot
h
ec
h
e
c
k
p
o
i
n
t
s
i
ft
h
e
y hadr
e
c
e
i
v
e
dm
e
s
s
a
g
e
ss
e
n
もb
yO
i
. Ag
l
o
b
a
l
sat
u
p
l
e(
c1，
.
.
.
，
♂
)ofthel
o
c
a
lc
h
e
c
k
c
k
e
c
l
c
p
o
i
n
tci
p
o
i
n
t
s
. Fromh
e
r
e，
atermc
h
e
c
l
c
p
o
i
n
tmeansag
1
0
6o
.
1
o
n
e
.I
fano
b
j
e
c
tois
e
n
d
samessagem b
e
f
o
r
eもa
k
i
n
g
c
'b
u
ta
n
o
t
h
e
ro
b
j
e
c
t句 r
e
c
e
i
v
e
sm a
f
t
e
rt
a
k
i
n
gc
'，
m
h
e
c
k
p
o
i
n
tci
sc
o
n
s
i
s
t
e
n
tぜ t
h
e
r
e
i
sanorphan. Thec
tc
.T
h
i
sd
e
f
i
n
i
t
i
o
ni
sr
e
f
e
r
r
e
dも0 剖
i
snoorphan問 a
message-basedc
o
悶 i
s
t
e
n
古c
h
e
c
l
c
p
o
i
n
t
.I
nF
i
g
u
r
e1
(
1
)，
t
h
ec
h
e
c
k
p
o
i
n
t(
c
'，
c
1
)i
sc
o
n
s
i
s
t
e
n
tw
i
t
ht
h
em
e
s
s
a
g
e
もi
o
n
.I
nF
i
g
u
r
e1
(
2
)，
(
c
"c
1
)泊
i
s
i
n
。
c
∞nsis色旬e
町
加n
b
a
s
e
dd
e
f
i
n
i
b
e
c
a
u
s
em i
sano
r
抑制・ P
a
p
e
r
s[
1
3，
9
，
1
1
]d
i
s
c
u
s
show
t
o同 k
ec
o
n
s
i
s
t
e
n
tc
h
e
c
k
p
o
i
n
t
si
n出 emessage-bωed
s
y
s
t
e
m
.
，
，=
.
i
'
nF
i
g
u
r
e2
.
.
.
， o~ ，} i
.
町(叩~， c
{
)={OE恥
We d
i
s
c
u
s
sw
rn
h
e
t
h
e
ro
o
te
a
c
hc
h
e
c
k
p
o
i
n
t(
4，
d
，
.
)canbetakenintheobject・b踊 edsystem. The
もc
も cmayb
c
o
n
s
i
s
t
e
n
h
e
c
k
p
o
i
n
0・
ei
n
c
o
n
s
i
s
t
e
n
tw
i
t
h
もh
回 e
em
e
s
s
a
g
e
b
dd
七
i
o
n
.F
o
rexample，
e
f
i
n
i
ec
h
e
c
k
七h
p
o
i
n
t
s(
d
a
)and(c
4，
，
l ~)釘e message-basedIncons
i
s
t
e
n
ti
i
g
u
r
e2
.I
sn
nF
f場 i
o
n
u
p
d
a
t
e，
もh
e伽 旬
d
e
n
o
t
e
dby~. i
st
h
esamea
s~ and~. Thati
s，
(
c
1，
伽
a
n
d
s
h
o
w
t
h
e
t
e
s
a
m
e
倒
的
，
Th
c
{
) (
弓
， ~)
~)・
c
h
e
c
k
p
o
i
n
t(
sc
o
n
s
i
s
t
e
n
t wi
七ht
h
em朗 s
a
g
e
弓
， ~) i
b
a
s
e
dd
e
f
i
n
i
t
i
o
nb
e
c
a
u
s
eもh
e
r
ei
snoo
r
p
h
a
n
. Hence，
t
h
eo
b
j
e
c
t0
a
nber
e
s
t
a
r
t
e
d合omanyo
ft
h
el
;c
o
c
a
l
c
h
e
c
k
p
o
i
n
t
s~ andd.tぜ句 c
a
nb
er
e
s
t
a
r
t
e
dfrom~. A
1
c
h
e
c
k
p
o
i
n
tc (
，
. cn)i
so
b
j
e
ct
c
-6
t
lc
o
n
o
i
o
t
e
n
t
，
tUe
・c
o
n
s
.
i
dent)i
v
e
r
yo
f
fe
b
j
e
c
to
(
0
a
nber
o
l
l
e
dbackもo
ic
t
h
el
o
c
a
lc
h
e
c
k
p
o
i
n
tc
nc
'and出e
a
nb
e目 前a
r
t
e
dfrom
i
o
b
j
e
c
tp
cfrom七h
o
i
n
to
fv
i
e
w
.(
c
1，
~) and ，
~)
:
c
も
areO
・c
o
n
s
l
s
e
n
t
.
I
f叫 i
sanupdateもype，
(
c
sn
o
t0・c
o
n
s
i
s
t
e
n
t
，
l ~) i
b
e
c
a
u
s
eO~ mayh
a
v
echangedt
h
e脚 色ea
td
H
i
s
0
;
a
.
r
o
l
l
e
dback色oc
su
n
d
o
n
e
.Supposet
h
a
t0
a
k
e
s
;t
i，
O
1
'
ii
w
h
e
r
e
i
s
剖
p
a
r
t
i
a
l
l
y
p
e
r
f
o
r
m
e
d
s
h
o
w
n
i
n
F
i
g
u
r
e
o~
~
2
. 叫 旭 町u
i
r
e
dt
obea
b
o
r
t
e
dw
h
i
l
eo
t
h
e
rmethods
b
e
i
n
gp
e
r
f
o
r
m
e
da
t~ mayn
o
th
a
v
et
obeu
n
d
o
n
e
.
=
<
4
同町
C1
ー
~.，~
c
2 ~.，~
4 4
4
3
.
2 0b
j
e
c
t
-basedsystem
Supposeamethodo
p
li
nano
b
j
e
c
t町 i
n
v
o
k
e
s停 2
h
b
j
e
c
t0
a
n
o
t
h
e
ro
;・Figures2showsapairofpossible
b
j
e
c
t
s
h
e
c
k
p
o
i
n
t
s4andc
obet
'
l
o
c
a
lc
a
k
e
ni
nもheo
ht
e
s
p
e
c
t
i
v
e
l
y
. Here，let 可(~戸， c
nd0
e
t
;，r
1
)beas
o
ia
o
fmethodswhich
• p
r
e
c
e
d
eザ and
• s
h
e
c
k
p
o
i
n
tc
1o
u
c
c
e
e
dal
o
c
a
lc
ra
r
eb
e
i
n
gp
e
r
・
七c
formeda
1i
n句、.
C
o
n
d
i
t
i
o
n
s
叫
sn
o
n
u
p
d
a
t
e
.
停~ i
i
s
'
n
o
n
u
p
d
蹴
.
~
句
m
駒
d
)
Mch i
d
i哨田
，
式d
n
s巧
o
h
n
m
o
a
d
i
d
(
hm
ws
sn
o
n
u
p
d
a
t
e
.
~，~. I 坐 i
T
a
b
l
e1
O
D
s
i
s
t
e
n
tchec~points f
o
rF
:0・c
i
g
u
r
e2
.
y
p
e
so
fl
o
c
a
lc
Therea
r
e色wot
h
e
c
k
p
o
i
n
t
s
i
.
e
. com，
i
p
l
e
t
eand初 c
o
m
p
l
e
t
eo
n
e
s
. Al
o
c
a
lcheckpoin~ c
i
s
o
.methodb
旬 i
comple
e
r
ei
sn
fもh
e
i
n
gp
e
r
f
o
r
m
e
da
tci •
n
c
o
m
p
l
e
t
e
.F
0もh
si
o
rexample，
e
r
w
i
s
e，
c
'i
si
n
c
o
m
c~ i
upp08eぬeo
p
l
e
t
ei
i
g
u
r
e2
nF
.S
b
j
e
c
t
.0
sr
o
l
l
e
dback
;i
同e
c
o
n
s
i
n
tc
h
e
c
k
p
o
i
n
tc
t
oan0・
sc
o
m
p
l
e
t
e，
k
:If i
-74-
c
t
t
h
es
t
抗 eo
f句 i
sj
u
s
tr
e
s
t
o
r
e
dfrom出 el
o
g
.
.I
f~ i
s
もh
emethodsb
e
i
n
gp
e
r
f
o
r
m
e
da
t~ h
a
v
e
i
n
c
o
m
p
l
e
t
e，
t
a
t
ei
sr
e
s
t
o
r
e
d
.However，
no
t
ob
ea
b
o
r
t
e
da
f
t
e
r出 es
methodi
nv
o
k
e
dbyぬemethodsa
b
o
r
t
e
di
sr
e
q
u
i
r
e
d
t
ob
er
o
l
l
e
dbacks
i
n
c
et
h
emethodsa
r
en
o
n
u
p
d
a
t
e
.
ec
h
e
c
k
p
o
i
n
t(
e
i，
d
a
)whend
ai
si
n
L
e
tu
sc
o
n
s
i
d
e
rもh
r
er
o
l
l
e
dbackもoc
land
c
o
m
p
l
e
t
e
.SupposeOiand句 a
，
4
t respectively. Sinceo~ i
sa
b
o
r
t
e
donr
o
l
l
i
n
gb
a
c
k
t
od
g，匂 i
sf
i
n
a
l
l
yr
o
l
l
e
dbackもoas
t
a
もed
e
n
o
t
e
dby~.
(ι~) i
sc
o
n
s
i
s
t
e
.
n
t
. Hence，
(
c
i，
d
g
)i
s0・c
o
n
s
i
s
悦n
t
.
(c~ ， t
4
)and(
c
1，
G
)arealso0・consi凶 ent.
L
e
tu
sc
o
n
s
i
d
e
rcheckpoi附 (C~ ， ~)， (c~ ， ~)， and
(c~ ， ~) w
hicha
r
em
e
s
s
a
g
e
b
a
s
e
di
n
c
o
n
s
i
s
t
e
n
t
.I
f叩 4
i
sn
o
n
u
p
d
a
t
e，
~ d
e
n
o
t
e
st
h
esames
t
抑 制 Gs
i
n
c
e
例 doesnoも changethe叫 a
t
e
. Hence
，(c~ ， ~) i
s0・
c
o
n
s
i
s
t
e
n
ts
i
n
c
e(c~ ， G
)i
sm
e
s
s
a
g
e
b
a
s
e
dc
o
n
s
i
s
t
e
n
t
.
H
e
r
e，
s
u
p
p
o
s
et
h
a
t~ I
sr
e
a
.dandt
h
e
r
ei
ssomew
r
i
t
e
叫 h preceding叫 卸dfollowingc
{
.
。
品 readsdata
c
{deno七e
sas
七a
t
ed
i
f
f
e
r
e
n
t
w
r
i
t
t
e
nby喝 h・ Hence，
.Ifnomethodfollowingc
{andpreceding叫
fromG
c
o
n
f
l
i
c旬 w
i
t
h0品
， o~ sendsthesameresulteveni
f
叫 i
sp
e
r
f
o
r
m
e
db
e
f
o
r
e叫 1
・H
ence，
i
f場 i
sn
o
n
u
p
d
a
t
eandc
o
n
f
l
i
c
t
sw
i
もhn
omethodi
nt
h
eseも宥J(O~ ，
c
i
)ofreq印 刷 ，(c~ ， c
{
)i
sO
c
o
n
s
i
s
t
e
n
t
. (c~ ，~) i
s
a
l
s
oO
c
。
∞nsi
泊
s
も
旬
e
町
加n
乱
l
i
n
c
o
m
p
l
e
t
e
.
Ta
b
l
e 1summarizes 出
h
eme
伺s
回s
胞a
伊
g
e
b
踊 e
吋d i
n
。
c
∞n
悶s
i
泊
s
s
七
同
e
叫
n
も b
叫
u
も
1
泊 O
-c
∞
o
n
四
s
i
恒
s
t
旬e
叫
n
も
l
凶 c
h
e
c
k
p
o
i
n
旬
， w
herec
h
e
侃c
k
p
o
i
n
色
旬
m
a
釘
r
.
r
k
e
♂
dキ 釘 卸ei
n
c
o
“
凹
[
Def
貧
i
n
耐i
託
悩
t
i
加
。
叩
n
]
阿Su即
p
p。s
田
卿
e色出
h
加
伽
a
叫
も 叩叫~ s
e
n
d
samessagem t
o
op~ i
nano
b
j
e
c
t0
;
.・L
e
tc
'b
eal
o
c
a
lc
h
e
c
k
p
o
i
n
tmost
t
1ytakenbyt
h
eo
b
j
e
c
t0
&
. Them
essagem i
si
n
r
e
c
e
n
f
l
u
e
πt
ia
.
li
f
fo
n
eo
ft
h
ef
o
l
l
o
w
i
n
gc
o
n
d
i
もi
o
n
si
ss
a
t
i
s
f
i
e
d
:
1
.I
fm i
sar
e
q
u
e
凶 me
嗣 ，g
e，
amethodOp(m)(=
叩
，
1
)i
su
p
d
a
t
e
.
Op(m) (=叫)i
s
2
.l
fm i
sar
e
s
p
o
n
s
emessage，
d
)conflicts
u
p
d
a
t
eo
rsomemeもhodin向 (Op(m)，
w
i
t
hOp(m).
I
famethodop;.i
sa
b
o
r
t
e
d，
o
n
l
ymethodsr
e
c
e
i
v
i
n
gi
n
r
er
e
q
u
i
r
e
dt
obea
b
o
r
t
e
d
.
f
i
u
e
n
t
i
a
lm
e
s
s
a
g
e
sfromOPia
c
o
n
F
o
l
l
o
w
i
n
gt
h
ee
x
a
m
p
l
e
sd
i
s
c
u
s
s
e
dh
e
r
e，O
七sa
r
ed
e
f
i
n
e
d槌 f
o
l
l
o
w
s
.
s
i
s
t
e
n
tc
h
e
c
k
p
o
i
n
c1，.
.
.
，
♂
)i
s
[
D
e
f
i
n
i
t
i
o
n
]A g
l
o
b
a
lc
h
e
c
k
p
o
i
n
tc=(
o
b
j
e
c
t
b
a
s
e
dc
o
n
s
i
s
t
e
n
t(0
・c
o
n
s
i
s
t
e
n
t
)i
f
f七h
e
r
ei
sno
i
n
f
i
u
e
n
t
i
a
lorphanmessage叫 c
.口
，
.
. co)i
sassumedt
obec
o
n
s
i
s
加 l
t
.A
f
t
e
rs
e
n
d
i
n
g
andr
e
c
e
i
v
i
n
gm
e
s
s
a
g
e
s，
0
&t
a
k
e
saf
i
r
s
tl
o
c
a
lcheck~
p
o
i
n
tc
i
. Thus， t
a
k
e
st
h
et
t
hl
o
c
a
lc
h
e
c
k
p
o
i
n
tc
;
a
f
t
e
rt
a
k
i
n
g七he(
t
1
)
t
hl
o
c
a
lc
h
e
c
k
p
o
i
n
tC
i
l(
t>0
)
.
Thecommunicationbetween 1andc~ i
sr
e
f
e
r
r
e
dt
o
栂 c
k
e
c
k
p
o
i
n
t飢 t
e
r
va
.l1
;
1
'Int
h
ei
n
t
e
r
v
a
l，
;
1 0;.sends
andr
e
c
e
i
v
e
sm
e
s
s
a
g
e
s
.H
e
r
e，
tdenotesacheckpoint
numbero
fc~. Thec
h
e
c
k
p
o
i
n
tnumberi
si
n
c
r
e
m
e
n
t
e
d
byo
n
ee
a
c
ht
i
m
eal
o
c
a
lc
h
e
c
k
p
o
i
n
ti
sもa
k
e
n
.Suppose
Oi a
叫o
nomouslyt
a
k
e
sas
u
c
c
e
e
d
i
n
gl
o
c
a
lc
h
e
c
K
p
o
i
n
t
c~ a
f
t
e
r同 k
i
n
gc~_l ・ Then， o
n
l
yi
fもh
e
r
ei
sam
e
s
s
a
g
e
m wh
i
c
h0 s
e
n
d
sもoano
も
h
e
ro
b
j
e
c
t0;，
mi
smarked
c
h
e
c
k
p
o加 t
e
d
.Bys
e
n
d
i
n
gm，
t
h
eo
b
j
e
c
t0
&n
o
t
i
貴e
st
h
e
a
k
e
sc~. Thus，
Oi
d
e
s
t
i
n
a
t
i
o
no
b
j
e
c
t
so
fm t
h
a
t0;. t
d
o
e
sno
色s
e
n
4anya
d
d
i
t
i
o
n
a
lc
o
n
t
r
o
lm
e
s
s
a
g
eもor
e
・
q
u
i
r
eo
t
h
e
ro
b
j
e
c
胞 もot
a
k
el
o
c
a
l
.c
h
e
c
k
p
o
i
n
t
s
.H
e
r
e，
s
u
p
p
o
s
et
h
a
tal
o
c
a
lc
h
e
c
k
p
o
i
n
t~-1 i
st
a
k
e
ni
nt
h
e
o
b
j
e
c
t0
;andac
h
e
c
k
p
o
i
n
t(
c
L
1
1~-1) i
sc
o
n
s
i
s
t
e
n
t
.
Onr
e
c
e
i
p
to
ft
h
ec
h
e
c
k
p
o
i
n
t
e
dm
e
s
s
a
g
em from0
"the
a
k
e
sal
o
c
a
lc
h
e
c
k
p
o
i
n
t~ a
twhich0
;s
a
v
e
s
o
b
j
e
c
t匂 t
もh
es
t
a
t
ewhichi
sj
u
同 b
e
f
o
r
er
e
c
e
i
v
i
n
gm. I
ti
s
.c
l
e
a
r
t
h
ec
h
e
c
k
p
o
i
n
t (c~ ， ~) i
sc
o
n
s
i
s
も
e
n
tfromt
h
ed
e
f
i
n
i
t
i
o
n
.Then，
s
u
p
p
o
s
e0
;s
e
n
d
sam
e
s
s
a
g
em't
o叩 o
t
h
e
r
sa
l
s
omarkedc
k
e
c
k
p
o
i
n
t
e
d
.Onr
e
c
e
i
p
七
o
b
j
e
cもOle・m'i
o
fm，
O
l
et
a
k
e
sal
o
c
a
lc
h
e
c
k
p
o
i
n
ti
n出 es
剖n
eway回
0
;
.Thus，
e
a
c
ho
b
j
e
c
t同 k
e
sal
o
c
a
lc
h
e
c
k
p
o
i
n
toni
t
s
叫i
n
g吐l
ec
h
e
c
k
p
o
i
n
t
i
n
gp
r
o
c
e
d
u
r
eo
rar
e
c
e
i
p
to
f
i
n
i
t
i
ac
h
e
c
k
p
o
i
n
t
e
dm
e
s
s
a
g
e
.
"
0
c
:
_
，
4
.
2 O-consistentcheckpoints
Ano
b
j
e
c
t0
&m
anipula
もe
sv
a
r
i
a
b
l
e
sC
P
l，
・
， C]Jn 色。
i
d
e
n
もi
f
yal
o
c
a
lcheckpoinも c~. Eachv
a
r
i
a
b
l
ei
si
n
i
t
i
a
l
l
yO
.I
f0 t
a
k
e
sc~ ， t
h
ec
h
e
c
k
p
o
i
n
tnumbercp i
s
i
n
c
r
e
m
e
n
t
e
dbyo
n
e，
i
.e
.C
P
i:
=C
P
;
.+1andt=C
P
i
.A
m
e
s
s
a
g
em wh
i
c
h0 s
e
n
d
st
o0; a
f
t
e
r同 k
i
n
gc
1c
a
r
r
i
e
s
av
e
c
旬ro
fc
h
e
c
k
p
o
i
n
tnumbersm.cp=(m.cpl'・
，
m.cp
π
)，
wherem.cp
1
: C
P
:
1(
k 1
，
.
， n).
Onr
e
c
e
i
p
to
fam
e
s
s
a
g
em fromano
もh
e
ro
b
j
e
c
t
句
， a
no
b
j
e
c
t0 c
h
a
n
g
e
sav
a
r
i
a
b
l
eC
.町i.e
. CPj :=
m
.
c
p
j・Thus，
i
nt
h
eo
b
j
e
c
七，
i
O cp showsacheckpoint
a
k
e
smo
同r
e
c
e
n
もl
yand明 showsa
numberwh
i
c
h0 t
newes
もc
h
e
c
k
p
o
i
n
tnumbero
fa
n
o
t
h
e
ro
b
j
e
c
色町 w
h
i
c
h
0 k
nows(
j= 1，
.
， n，
j:
f
;i
)
.・
I
'ha
もi
s，
0 k
nows
抗 (
C
!
p
l
'.，. c.~pJ i
sac
u
r
r
e
n
tc
h
e
c
k
p
o
i
n
t
.I
fm
.
c
p
j
t
h
>.
c
p
;i
n0
" 0 findsむhat0 hasもakenasucceeding
c
h
e
c
k
p
o
i
n
tc
'
uwhereu m.cp;. A checkpointc~ i
s
i
d
e
n
t
i
f
i
e
dbyac
h
e
c
k
p
o
i
n
tv
e
c
t
o
r(C~.CP1 ， ・.'， c~.cPn)
w
h
e
r
ec
1
.
c
p
;s
howsav
a
l
u
ew
h
i
c
hc
p
;h
a
st
a
k
e
nwhen
c~ w
ω 胞 ken(
j 1，
.
，n
)
.
Al
o
c
a
lc
h
e
c
k
p
o
i
n
tc~ h槌 abitmapc~.BM (BM
，
t
，
.
. B Mn). Supposeanobject0& i
n
i
七i
a
t
e
sac
h
e
c
k
p
o
i
n
t
i
n
gp
r
o
c
e
d
u
r
ea
f
t
e
rt
a
k
i
n
gC
1
1andもhen，
0
，
，
，
=
，
，
，
，
，
，
=
=
=
，
，
=
，
4 CheckpointingProtocol
Wed
i
s
c
u
s
sanωynchronousp
r
o
もo
c
o
lf
o
rt
a
k
i
n
gc
h
e
c
k
p
o
i
n
t
samongo
b
j
e
c
t
s
.
4
.
1 Basicprotocol
l
nt
h
ea
s
y
n
c
h
r
o
n
o
u
sp
r
o
もo
c
o
l，e
a
c
ho
b
j
e
c
t0
;
.i
s舗 sumedt
oi
n
i
t
i
a
l
l
yt
a
k
eal
o
c
a
lc
h
e
c
k
p
o
i
n
tc~ wheret
h
e
;
.i
s
t
a
k
e
n
. Ani
n
i
t
i
a
lc
h
e
c
k
p
o
i
n
t(
c
a，
i
n
i
t
i
a
ls
t
a
t
eo
f0
-75-
c
h
e
c
k
p
o
i
n
t
i
n
gp
r
o
t
o
c
o
li
n
i
t
i
a
t
e
dbyasameo
b
j
e
c
t
.
[
D
e
f
i
n
i
t
i
o
n
]Ap
a
i
ro
il
o
c
a
lc
h
e
c
k
p
o
i
n
t
sc~ and~ a
r
e
i
nt
h
esamegenerationi
ic~.BM nct.BM=
Fゆand
c~ .
c
p
l
:
~.
c
p
l
:f
o
re
v
e
r
yo
b
j
e
c
t01
cs
u
c
h色h
a
tc~.BM1c
ct.BM
l
:
1
.
ロ
S
i
n
c
ei
ti
sc
l
e
a
rt
ha
.
tもh
e
r
ei
snoorphanm
e
s
s
a
g
ei
n
t
h
esameg
e
n
e
ra
.
t
i
o
nc
h
e
c
k
p
o
i
n
t，
t
h
ei
o
l
l
o
w
i
n
gt
h
e
o
r
e
m
h
o
l
d
s
.
[Theorem]A c
h
e
c
k
p
o
i
n
tcomposedo
isameg
e
n
e
ra
.
t
i
o
nl
o
ca
.
lc
h
e
c
k
p
o
i
n
t
si
sc
o
n
s
i
s
t
e
n
t
.ロ
Eacht
i
m
eano
b
j
e
c
t0 s
e
n
d
sam
e
s
s
a
g
em，
as
e
q
u
e
n
c
enumbers
qi
si
n
c
r
e
m
e
n
t
e
dbyo
n
e
.I
n
a
d
d
i
t
i
o
n，
as
u
b
s
e
q
u
e
n
c
enumbers
s
q
;i
si
n
c
r
e
m
e
n
t
e
dbyo
n
ei
fm
i
ss
e
n
tt
oano
b
j
e
c
t0
;(
j= 1，
.
.
，. n).Themessagem
e
q
u
e
n
c
enumberm
.sqandav
e
c
t
o
ro
ft
h
e
c
a
r
r
i
e
sもhes
s
u
b
s
e
q
u
e
n
c
enumbersm
.
s
s
q=(
m
.
s
s
q
l，
，
. m.ssqn
.
)
.
Ano
b
j
e
c
t0
;m
a
n
i
p
u
l
a
t
e
sv
a
r
i
a
b
l
e
sr
s
q
l，
・
， rsq.
nand
r
s
s
q1!・
， rssqntoreceive.messages.Onreceiptofm
from0
"O
jr
e
c
e
i
v
e
sm i
fm
.ss
町 =r
s
s
q +1
. Th
a
.
t
0
;de
1
iv
e
r
sm
e
s
s
a
g
e
sf
o
re
a
c
ho
b
j
e
c
ti
nt
h
es
e
n
d
i
n
g
i
s，
s
s
前 +1a
ndr
s
q :=m
.
s
q
.
o
r
d
e
r
. Then，何時:=r
s
q showas
u
b
s
e
q
u
e
n
c
enumberands
e
r
s
s
q
iandr
q
u
e
n
c
enumbero
fm
e
s
s
a
g
ewhich0
;h
a
smos
もr
e
c
e
nt
1
y
i
， r
e
s
p
e
c
t
i
v
e
l
y
.
r
e
c
e
i
v
e
dfromO
も
Them
e
s
s
a
g
em a
l
s
oc
a
r
r
i
e
sav
e
c
t
o
ro
ft
h
er
e
c
e
i
p
s
e
q
u
e
n
c
enumbersm.r
q=(
m
.r
q
l，
・
， m.rqn
.
)wh
e
r
e
m
.
r
q1
c
r
s
q
l
c(
k 1，
.
，n
)
. Here，
m.rq1
cs
howsa
s
e
q
u
e
n
c
enumbero
fm
e
s
s
a
g
ewhich0 r
e
c
e
i
v
e
s告om
0
;j
u
s
tb
e
f
o
r
et
a
k
i
n
gt
h
el
o
c
a
lc
h
e
c
k
p
o
i
n
tc~ andt
m.cp (
k 1，
・
・
・
，n
)
.
Onr
e
c
e
i
p
もofmf
rom0
"t
h
eo
b
j
e
c
も0
;c
o
l
l
e
c
t
sas
e
も
崎 o
fm
e
s
s
a
g
e
smj1J .
， m;l;whichο;hassentもoOi
a
f
t
e
rt
a
k
i
n
gt
h
ec
u
r
r
e
n
tl
o
c
a
lc
h
e
c
k
p
o
i
n
t~-1 and0
h
a
sr
e
c
e
i
v
e
db
e
f
Q
r
et
a
k
i
n
gc~. Here，
mjh・
s
q:
5m.r町
[
F
i
g
u
r
e3
]
.MessageswhichO
js
e
n
d
sa
f
t
e
rt
a
k
i
n
g~-1
a
r
es
t
o
r
e
di
nt
h
es
e
n
d
i
n
gl
o
go
f0
;
.Suppose0
;r
e
c
e
i
v
e
s
I
fm.cPi>C
1
'
i
，0
;
ac
h
e
c
k
p
o
i
n
t
e
dm
e
s
s
a
g
em fromO
j・
knowst
h
a
to
it
a
k
e
sanewc
h
e
c
k
p
o
i
n
色c
l
.0
;c
o
l
l
e
c
t
s
e
n
ta
f
t
e
r~-1 and
e
v
e
r
ym
e
s
s
a
g
em'which句 h舗 s
m
'
.
s
q<m.rs
匂
・ M;i
sas
e
to
ft
h
em
e
s
s
a
g
e
sc
o
l
l
e
c
t
e
d
h
ed
e
f
i
n
i
t
i
o
n，
i
もi
sc
l
e
a
rf
o
rt
h
e
h
e
r
e
.A
c
c
o
r
d
i
n
g七ot
f
o
l
l
o
w
i
n
gtheoremt
oh
o
l
d
.
=
=
=
，
=
，
，=
，
0
句
(
5，
3，
8
)
t
i
m
e
F
i
g
u
r
e4
:C
y
c
l
i
cc
h
e
c
k
p
o
i
n
t
s
.
=
，
C
t
D2
，
，
，
=
Thec
o
n
d
i
t
i
o
no
ft
h
et
h
e
o
r
e
mi
sr
e
f
e
r
r
e
dtoω 飢i
f
l
包e
n
t
i
a
l
.
m
e
s
s
，
og
e(1M)cond~tio_n_. I
fatle~t oneoithe
m
e
s
s
a
g
e
smjl，
.
， mj';i
sd
e
c
i
d
e
dt
obei
n
f
l
u
e
n
t
i
a
la
c
c
o
r
d
i
n
gt
o色h
e
.1Mc
o
n
d
i
t
i
o
n
s，
もh
e
o
b
j
e
c
t0
;泊 k
e
sa
1
0
ω
1checkpoint.~ s
h
o
w
i
n
gas
t
a
t
eo
fj
u
s
tb
e
f
o
r
er
e
e
r
w
i
s
e，
O
jd
o
e
sn
o
t同k
eal
o
c
a
lc
h
e
c
k
c
e
i
v
i
n
g
.m.0もh
. m;;
，a
r
eo
r
p
h
a
n
ss
i
n
c
eもhey
p
o
i
n
te
v
e
n
.i
fm
j
1
'，
h
e
c
k
p
o
i
n
t~， t
h
e
a
r
en
o
ti
n
f
t
u
e
n
t
i
a
l
. If 匂 ~akes ac
si
n
c
r
e
m
e
n
t
e
dbyo
n
ei
n0
;
.
c
h
e
c
k
p
o
i
n
tnumber明 i
M
e
s
s
a
g
e
swhich0
;s
e
n
d
sa
f
t
e
rt
a
k
i
n
g~ a
.
r
emarked
c
h
e
c
/
c
p
o
i
n
t
e
dωpresentedh
e
r
e
.
O
j
~-1
4
.
3 C
y
c
l
i
ccheckpointing
Supposet
h
e
r
ea
r
et
h
r
e
eo
b
j
e
c
旬 0
1，
0
2，
and0
3w
h
e
r
e
C
P
1，
C
P
2，
c
拘)i
s(
4，
2，
7
)i
ne
a
c
h
ac
h
e
c
k
p
o
i
n
tv
e
c
t
o
r(
も[
F
i
g
u
r
e4
]
.Supposetheo
b
j
e
c
t0
1t
a
.
k
e
sal
o
c
a
l
o
b
j
e
c
c
h
e
c
k
p
o
i
n
tc
l
.0
1s
e
n
d
sac
h
e
c
k
p
o
i
n
t
e
dm
e
s
s
a
g
em1
2
，
7
)t
o0
2a
f
t
e
r色a
k
w
i
t
ht
h
ec
h
e
c
k
p
o
i
n
tv
e
c
t
o
r(
5，
hgc
i
.句 t
a
k
e
sal
o
c
a
lc
h
e
c
k
p
o
i
n
tc
lonr
e
c
e
i
p
もo
f
mlw
h
e
r
ec
;
.
c
p= (
5，
3，
7
)
. Then，
0
2s
e
n
d
sac
h
e
c
k
p
o
i
n
t
e
dm
e
s
s
a
g
ef
f
l
2w
i
凶作， 3，7
)t
o句・ Onr
e
c
e
i
p
も
ofm
ゎ0
3t
a
k
e
s~ ands
e
n
d
sac
h
e
c
k
p
o
i
n
t
e
dme
蹴 g
e
3，
8
)もo0
1・
H
e
r
e，
e
v
e
ni
f0
1r
e
c
e
i
v
e
sm3，
m3w
i
t
h(
5，
0
1d
o
e
sno
もn
e
e
dt
oもa
k
eal
o
c
a
lc
h
e
c
k
p
o
i
n
もb
e
ca
.
u
s
ea
c
h
e
c
k
p
o
i
n
t(c~ ， c
l，
c~) もaken a
l
r
e
a
d
yi
sc
o
n
s
i
s
t
e
n
t
.I
f
，
t
h
eo
b
j
e
c
t
s0
1，
0
2，
叩 d0
3c
a
n
n
o
tt
e
r
0
1t
a
k
e
sc
Ah
e
r
e
ec
h
e
c
k
p
o
i
n
t
i
n
gp
r
o
c
e
d
u
r
e
.T
h
i
si
sac
y
c
l
i
c
m
i
n
a
t
eもh
c
h
e
c
/
c
p
o
i
n
t
i
n
g
.
Wed
i
s
c
u
s
showt
or
e
s
o
l
v
e出 e
_
c
y
c
l
i
cc
h
e
c
k
p
o
i
n
t
i
n
g
.
I
nF
i
g
u
r
e4，
t
h
eo
b
j
e
c
t0
1s
e
n
d
s句 ac
h
e
c
k
p
o
i
n
t
e
d
C
P (
5，
2
，
7
)andm1・
BM=
m
e
s
s
a
g
emlw
i
t
hm1・
(
1，
0，
0
)a
f
t
e
rCP1 i
si
n
c
r
e
m
e
n
t
e
dand凶 k
i
n
gc~. On
色o
fm1，
c
p (
5，
2，
7
)i
n0
2・Then，
0
2s
e
n
d
s
r
e
c
e
i
p
m2w
i
t
hm2・
op (
5，
3，
7
)andm2.BM (
1，
1
，
0
)t
o
0
3a
f
t
e
rt
a
k
i
n
gc~. Onr
e
c
e
i
p
to
fmぁ o
atakesalocal
c
p (
5，
3，
8
)
c
h
e
c
k
p
o
i
n
tc
landt
h
e
ns
e
n
d
sm3w
i
t
hm3・
andm3.BM (
1，
1
，
1
)も0
01・
When0
1r
e
c
e
i
v
e
sm3，
0
1
:
k
nowst
h
ec
h
e
c
k
p
o
i
n
t
i
n
gp
r
o
c
e
d
u
r
eW~ i
n
i
t
i
a
t
e
dby0
1
m
3
.
C
P
l=
5b
e
c
a
u
s
ec
h
e
c
k
p
o
i
n
t
si
d
e
n
t
f
f
i
e
d
s
i
n
c
eC
P
1=
2，
7
)and(
5，
3，
8
)a
r
ei
n七h
esameg
e
n
e
r
a
:
もi
:
e
m.
by(
5，
Onr~~eipt o
fa
_che~pointed m
e
s
s
a
g
em froman
・
o
t
h
e
ro
b
j
e
c
t0
;，
ぬeo
b
j
e
c
toi d
o
e
sn
o
tt
a
k
eal
o
c
a
l
checkp~nt i
fm.cps~ow~ a
.Ba~e g
e
n
e
r
a
t
i
o
nc
h
e
c
k
p
o
i
n
t
a
s0.
，Here，
o
im
a
n
i
p
u
l
a
t
e
sもh
ec
h
e
c
k
p
o
i
ntv
e
c
t
o
rc
p
andもh
ebitmapB M槌 f
o
l
l
o
w
s
:
l
::
=max(cpl
:t m
.cp
l
:
)i
fm.BM
1
c=1
.
• C
P
=
=
=
d
u
=
t
i
m
e
F
i
g
u
r
e3
:I
n
f
l
u
e
n
t
i
a
lm
e
s
s
a
g
e
s
.
[Theorem)Am
e
s
s
a
g
emjhi
nM;i
si
n
f
t
u
e
n
t
i
a
li
ft
h
e
f
o
l
l
o
w
i
n
gc
o
n
d
i
t
i
o
n
s
h
o
l
d
:
1
.m;h卯 i
su
p
d
a
t
ei
fT
J
:
I
.
jh
.i
sar
e
q
u
e
凶
， o
r
2
. m;h・
opi
su
p
d
a
t
eo
rc
o
n
f
l
i
c
t
sw
i
t
hsomeu
p
d
a
t
e
m
j
h・
op
，
~-1) ぜ m;h. i
sar
e
s
p
o
n
s
e
.
methodi
n巧 (
口
-76ー
=
=
O
a
c
02
内
a宮a
01
a
c
i
a
• B M:=B MU m.BM.
Thec
h
e
c
k
p
o
i
n
tv
e
c
t
o
rcpandt
h
ebitmapB Ma
r
e
s
a
v
e
di
nぬel
o
go
n
l
yぜ色，heya
r
eu
p
d
a
t
e
d
.
4
.
4 Mergeo
fcheckpoints
Next，
s
u
p
p
o
s
et
h
e
r
ea
r
ef
o
u
ro
b
j
e
c
旬 01，
O~h 03，
and
0
4剖 showni
nF
i
g
u
r
e5
. Here，e
v
e
r
yo
b
j
e
c
th剖 a
c
h
e
c
k
p
o
i
n
もv
e
c
t
o
r(
4，
3
，
7
，
2
)
.Suppose出 品 t
h
eo
b
j
e
c
t
s
0
1 and0
4i
n
i
t
i
a
t
e七h
ec
h
e
c
k
p
o
i
n
t
i
n
gp
r
o
c
e
d
u
r
e
. 0
1
s
e
n
d
sac
h
e
c
k
p
o
i
n
t
e
dmessagem1a
f
t
e
rもa
k
i
n
gal
o
c
a
l
c
h
e
c
k
p
o
i
n
tC
lwithcp (5，
3，
7，
1
)andB M (
1，
0，
0，
0
)
. Onr
e
c
e
i
p
to
fml，
o:a凶k
e
sal
o
c
a
lc
h
e
c
k
p
o
i
n
t
C~ andt
h
e
ns
e
n
d
sac
h
e
c
k
p
o
i
n
t
e
dmessagem2w
i
t
h
cp (
5，
4，
7，
1
) andB M (
1，
1
，0，0). Onもhe
o
t
h
e
rh剖叫 0
4t
a
k
e
sal
o
c
a
lc
l
悶 k
p
o
i
n
tc~ w
i
t
hc
p=
(
4，
3，
7，
2
)andB M (
O，
0，
0，
1
)andt
h
e
ns
e
n
d
sa
c
h
e
c
k
p
o
i
n
t
e
dm
essagem4t
o0
3・Theo
b
j
e
c
to
atakes
al
o
c
a
lc
h
e
c
k
p
o
i
n
tC~ w
i
t
hCp (
4，
3，
8，
2
)andB M
(
0，
0，
1
，
1
)andt
h
e
ns
e
n
d
sm3も002・Theo
b
j
e
c
t0
2
r
e
c
e
i
v
e
sm3wi
七hC
p (
4
，
3，
8，
2
)andB M (
0，
0，
1，
1
)from句 a
f
t
e
rt
a
k
i
n
gc
;w
i
t
hcp (
5，
4，
7，
1
)
.0
3
r
e
c
e
iv
e
sm2wi
もhc
p (
5，
4，
7，
1
)andB M (
1，
1
，
0，
0
)a
f
t
e
rt
a
k
i
n
g~ wi
七hc
p (
4
，3，
8，
2
)
. Onewayi
s
七h
a
も0
2and句 ぬkel
o
c
a
lc
h
e
c
k
p
o
i
n
t
sC~ w
i
t
hcp (
4，
5，
8，
2
)andB M (
0，
1
，
1
，
1
)組 dc~ w
i
t
hcp (
5，
4，
9，
3
)andB M (
1，
1
，1，
0
)
. Byu
s
i
n
gぬi
smethod，
もh
eo
b
j
e
c
t
s01，
02，
03，
and0
4t
a
k
eもwocl
悶 k
p
o
i
n
t
s(c~ ，
c
i，
d，c;)and(c;，Ci，ci，ci).Here，suppose出 品 04
sr
o
l
l
e
dback七oc~.
i
sf
a
u
l
t
y叩 di
I
no
r
d
e
rt
or
e
d
u
c
et
h
enumbero
fc
h
e
c
k
p
o
i
n
t
st
a
k
e
n
we凶 k
e
s叩 approachもomergingm
u
l
i
n出 esystem，
b
j
e
c
t0
2
t
i
p
l
ec
h
e
c
k
p
o
i
n
t
st
oo
n
e
.I
nF
i
g
u
r
e丸 山eo
r
e
c
e
i
v
e
sac
h
e
c
k
p
o
i
n
t
e
dmessagem3a
f
t
e
r同 k
i
n
gt
h
e
twoc
h
e
c
k
p
o
i
n
t
s(
c
A，c~)
l
o
c
a
lcheckpoint~. Here，
w
i
t
h(
1，
1
，0，0) and (C~ ， c~) with (0，0，1，1
)町 e
l，
4，c~) with(1，1，
mergedi
n
t
oonec
h
e
c
k
p
o
i
n
t(c~ ， c
1，
1
)
.
[Mergeofcheckpoints]A
f
t
e
rano
b
j
e
c
t向 同k
e
sa
"r
e
c
e
i
v
e
sac
h
e
c
k
p
o
i
n
t
e
dmessage
l
o
c
a
lc
h
e
c
k
p
o
i
n
tc~ ， 0
m.
1
.I
fac
h
e
c
k
p
o
i
n
tdeno
旬 db
ym.cpi
sn
o
ti
nt
h
esame
=
c:~
，，，
1
c
e
<4 3 8 2>
=
=
timc
=
F
i
g
u
r
e5
:C
h
e
c
k
p
o
i
n
t
s
=
o
.
"
:
3
Oi
=
=
=
=
=
=
=
generationω C~ ，
・
c
t
.
c
p:
=m.cp i
f
=1.
J
，
:
J
，
:
c~.BMJ，:
~-1
=
=
=
d
‘
品
=
=
=0andm.BM
c
1
・ ~.BM :=c~.BM Um.BM.
2.0
出e
r
w
i
s
e，
cl.BM:=c~.BM U m.BMandC1.CPl
:
=max(c~.叩1c， m.cpJ，:) f
o
rk=1
，
，
. n，
kp
:i
.ロ
[Theorem]A s
e
to
fl
o
c
a
lc
h
e
c
k
p
o
i
n
旬 wh
i
c
hb
e
l
o
n
g
も
ot
h
esameg
e
n
e
r
抗i
o
ni
s0・c
o
n
s
i
s
七e
n
t
.
刊 もh
etheorembyc
o
n
t
r
a
d
i
c
t
i
o
n
.A
s
[
P
r
o
o
f
]Wep
r
o
e
r
ea
r
etwol
o
c
a
lc
h
e
c
k
p
o
i
n
t
s~ and~
sumet
h
a
tもh
whichb
e
l
o
n
gt
o叶l
esameg
e
n
e
r
a
t
i
o
n
.anda
r
en
o
t0・
c
o
n
s
i
s
t
e
n
t，
i
.e
. 世l
e
r
ee
x
i
s
t
sani
n
f
l
u
e
r
凶i
a
lmessagem
sr
e
c
e
i
v
e
db
e
f
o
r
ec
![Figwhichi
ss
e
n
ta
f
t
e
rc~ andi
u
r
e6
]
. Here，
i
f町 s
e
n
d
sm t
o0
;，
mi
smarkedc
h
e
c
k
p
o
i
n
t
e
d
.Onr
e
c
e
i
p
to
fm，
0
;同 k
e
sal
o
c
a
lc
h
e
c
k
p
o
i
n
t
~-1 j
u
s
tb
e
f
o
r
er
e
c
e
i
v
i
n
gm i
fm i
si
n
f
l
u
e
n
t
i
a
l
.Othe
r
w
i
s
e，
o
;d
o
e
sno
もt
a
k
eal
o
c
a
lc
h
e
c
k
p
o
i
n
t
.Thus，
t
h
e
checkpoin旬 c~ a
nd&
，
.neverbelongt
osameg
e
n
e
r
a
もi
o
n
.
T
h
i
sc
o
n
t
r
a
d
i
c
t
st
h
ea
s
s
u
m
p
t
i
o
n
.ロ
F
i
g
u
r
e6
:Sameg
e
n
e
r
剖i
o
nc
h
e
c
k
p
o
i
nt
s
5 R
estartingProtocol
I
fano
b
j
e
c
to
ii
sf
a
u
l
t
y
，
もh
er
e
s
t
a
r
t
i
n
gp
r
o
もo
c
o
li
si
n
i
，詰 r
o
l
l
e
dback加もhel
o
c
a
lc
h
e
c
k
t
i
a
t
e
d
.Theo
b
j
e
c
t0
p
o
i
n
tc
:whichi
smostr
e
c
e
n
t
l
y同 k
e
nby~. I
no
r
d
e
r
t
ok
e
e
pt
h
es
y
s
もem0・c
o
n
s
i
s
t
e
n
t，
o
b
j
e
c
旬 w
hichhave
f
t
e
r同 k
i
n
g
r
e
c
e
i
v
e
di
n
f
l
u
e
n
t
i
a
lm
e
s
s
a
g
e
ss
e
n
tby0 a
t
h
el
o
c
a
lcheckpoin色 c~ a
r
er
e
q
u
i
r
e
dt
ober
o
l
l
e
db
a
c
k
.
Therea
r
e七woc
卸 e
s，
onec
a
s
ei
st
h
a
t0
"r
e
c
o
r
d
sm
e
s
s
a
g
e
swh
i
c
hOi s
e
n
d
si
n七hel
o
gandt
h
e0もh
e
rc
a
s
ei
s
t
h
a
tOi d
o
e
sn
o
tt
a
k
el
o
gs
i
n
c
e.
i
tt
a
k
e
st
i
m
e七or
e
c
o
r
d
，
weぬk
e
eachmessages
e
n
ti
nt
h
el
o
g
.I
nt
h
i
sp
a
p
e
r
t
h
ef
i
r
凶 a
p
p
r
o
a
c
h
.Theo
b
j
e
c
t0 s
e
n
d
sa
-r
o
l
l
b
a
c
kr
e
・
que
前 m
essageR・Reqt
oe
v
e
r
yo
b
j
e
c
も句 w
hicho
ih鎚
s
e
n
tm
e
s
s
a
g
e
sa
f
t
e
rt
a
k
i
n
g Then
，
0c
a
nr
e
s
t
a
r
tt
h
e
computation幽 y
n
c
h
r
o
n
o
u
s
l
yw
i
t
ho
t
h
e
ro
b
j
e
c
t
s
.
b
j
e
c
t
sR-Reqもob
e
I
no
r
d
e
rt
od
e
c
i
d
eもowhicho
s
e
n
_
t，
e
a
c
ho
b
j
e
c
t0 r
e
c
o
r
d
sd
e
s
t
i
n
a
t
i
o
no
b
j
e
c
t
si
nal
o
g
SL~. When~ t
a
k
e
sc~ ， SL~ i
si
n
i
t
i
a
t
e
dもobee
m
p
t
y
.
Eachもime0 s
e
n
d
sani
n
f
t
u
e
n
t
i
a
lmessagem も0飢 ・
0もh
e
ro
b
j
e
c
t0
;a
f
t
e
rc
t，SL~ SL~ U {Oj}. Here，m
n
f
l
u
e
n
t
i
a
la
c
c
o
r
d
i
n
gt
ot
h
ei
n
f
l
u
e
n
・
i
sd
e
c
i
d
e
dぬ bei
t
i
a
lm
e
s
s
a
g
e(
I
F
)c
o
n
d
i
t
i
o
n
s，
I
no
r
d
e
rt
or
e
d
u
c
eもh
e
o
v
e
r
h
e
a
d色ow
r
i
t
e七hel
o
g
，SL~ i
sw
r
i
t
t
e
n色ot
h
el
o
g
o
n
l
yi
fSL~ i
sc
h
a
n
g
e
d
.I
f0 i
sr
o
l
l
e
db
a
c
k主ot
h
el
o
c
a
l
ch~ckpoint c
l，
0s
e
n
d
sR-Reqt
oe
v
e
r
yo
b
j
e
c
t0
;i
n
SL~. H
ere，
R・Reqc
o
n
t
a
i
n
st
h
ef
o
l
l
o
w
i
n
gi
n
f
o
r
m
a
t
i
o
n
:
• Ac
h
e
c
k
p
o
i
n
tv
e
c
t
o
rc
p (
C
P
1
'・
・
・，
cPn) o
fもh
e
"i
sr
o
U
e
db
a
c
k
.
l
o
c
a
lc
h
e
c
k
p
o
i
n
tc~ 七o which0
仰11.
， rvn)whereeach
• Ar
o
l
l
b
a
c
kv
e
c
t
o
r問 =(
T町 i
s1i
fo
iknowsOlc i
sr
o
l
l
e
db
a
c
k
. 0七h
e
r
w
i
s
e，
r
vJ，: O
.
Onr
e
c
e
i
p
to
fR-ReqfromOi，
ano
b
j
e
c
tOj d
i
s
c
a
r
d
s
Reqi
fR
R
e
q
.
r
v
; 1s
i
n
c
e0
;h
a
sbeena
l
r
句 dyr
o
I
l
e
d
R・
-77-
，
，
c
:
.
，
，
=
，
，
•
=
=
=
，
b
a
c
ki
nt
h
i
sg
e
n
e
r
a
t
i
o
n
.O
t
h
e
r
w
i
s
e，
r
V
:
l:=max(r，
V
:
l
R・R
e
q
.
r
V
k
)(
k=1
，
.
.
，. n)・句 looksforanoldestlocal
'
uwhereC
P
i=R・R
e
q
'
C
P
i
'I
f0
;f
i
n
d
ss
u
c
ha
c
h
e
c
k
p
o
i
n
tc
l
o
c
a
lc
h
e
c
k
p
o
i
n
t~， c
'
ui
sr
e
f
e
r
r
e
d色0 剖 r
o
l
l
btJc
kp
o
i
n
t
o
f0 O
t
h
e
r
w
i
s
e，
t
h
emostr
e
c
e
r
i
tc
h
e
c
k
p
o
i
n
tw
h
e
r
e
C
P
i:
<R-Req.cPibecomesarollbaclcpoint. Then，
0
;
c
o
l
l
e
c
旬 a8
e
tRVo
fm
e
s
s
a
g
e
swhich0
;h
a
sr
e
c
e
i
v
e
d
fromo
ia
f
t
e
rt
a
k
i
n
g~. I
f
色h
e
r
ei
ssomei
n
f
t
u
e
n
t
i
a
l
m
e
s
s
a
g
ei
nR V，
句 i
sr
o
l
l
e
dbackt
ot
h
er
o
l
l
b
a
c
l
cp
o
i
n
t
c
i
.句 sendsR-ReqもoeveryOlc inSL~ wiもhR-Req.rvj
:
三 1a
.
n
dr
VI
:=
1
.I
f
o
;h剖 n
o
tr
e
c
e
i
v
e
danyi
n
f
t
u
e
n
t
i
a
l
"0
;d
i
s
c
a
r
d
s R・Reqs
i
n
c
e0
;i
sn
o
t
m
e
s
s
a
g
efrom0
r
e
q
u
i
r
e
dt
ob
er
o
l
l
e
db
a
c
k
.
e
C
h
e
c
k
p
o
i
n
t
i
n
gandC
o
n
c
u
r
r
e
n
tR
o
l
l
b
a
c
kf
o
rR
c
o
v
e
r
yi
nD
i
s
t
r
i
b
u
t
e
dS
y
s
t
e
m
s- ， AnO
p
t
i
m
i
s
t
i
c
Approach，
"Proc. 0
1IEEE SRDS-7，pp.3・12，
1
9
8
8
.
・・
，
0
<0，
0，
0>
C
i
<1，
0，
0>
<0，
o
.0>
Oj
<0.o
.0>
[
2
}Ch
卸 d
y
，K.M.andLamport，L.“
，Di山 ibuted
旬
D
e
t
e
r
m
i
n
i
n
gG
l
o
b
a
lS
t
a
t
e
so
fD
i
s
Snapsho
t
r
i
b
u
t
e
dS
y
s
t
e
m
s
"
，AOMTOCS，
Vo
l
.3，
No・1
，
p
p
.6
37
5，
1
9
8
5
;
.
M
.J
.，
G
r
i
f
f
e
t
h，
.
N
.D
.，
a
n
d
.
L
y
n
c
b，
N
.A
.，
[
3
]F
i
s
c
b
e
r，
“
G
l
o
b
a
lSも叫e
so
faD
i
s
t
r
i
b
凶e
d.
System，
"IEEE
7rtJ
n
s
.01
1
.S
0
β切 tJr
eE
n
g
i
n
e
e
r
i
n
g
，
Vo
l
.SE
-8，
N
o
.
3，
pp.19ι202，
1
9
8
2
.
間G
a
r
c
i
a
-Mo1
i
na
，H.，
“Using Semantics Knowl-
a
n
s
a
c
t
i
o
n
P
r
o
c
e
s
s
i
n
gi
naD
i
s
t
r
i
b
u
t
e
d
e
d
g
ef
o
rTr
D
a
t
a
b
a
s
e，
"Proc.olAOMSIGMOD，
Vo
l
.8，
N
o
.
2，
p
p
.1
8
8
・2
1
3，
1
9
8
3
.
0
"
[
5
]H
i
g
a
k
i，H
.，
Sima
，K.，Tanaka，K.，Tacbik
a
.
wa
，
T
.叩 dTa
凶 awa
，
M.
“
，CheckpointandRollback
i
nAsynchronousD
i
s
t
r
i
b
u
t
e
dSyste~ ，" P
r
o
c
.0
1
lEEEINFOOOM'97，
p
p
.1
0
0
0
1
0
0
7
，
1
9
9
7
.
c
f
c
;
. and Ta
.
ki
z
a
w
a
，M.，
“Checkpoint・
[
6
}H
i
g
a
k
i，H
Rec
o
v
e
r
yPro
もo
c
o
lf
o
rR
e
l
i
a
b
l
eM
o
b
i
l
eS
y
s
t
e
m
s，
"
P
r
o
c
.0
1IEEESRDS-17，
p
p
.
9
3
・
9
9，
1
9
9
8
.
. 叩 d Toueg，S
.，
“Checkpoi凶 ngand
[
7
] Koo，R
"
R
o
l
l
b
a
c
k
R
e
c
o
v
e
r
yf
o
r D
i
s
t
r
i
b
u
t
e
dS
y
s
t
e
m
s，
lEEE 宝Mn6. 01
1
.C
omputers，
Vo
l
.C
1
3，
N
o
.1
，
p
p
.2
3
3
1，
1
9
8
7
.
t
i
m
e
F
i
g
u
r
e7
:R
e
s
t
a
r
t
i
n
gp
r
o
c
e
d
u
r
e
.
S
u
p
p
o
s
et
h
a
t 叫ueeo
b
je
c
t
s0
" 0
;，and 01
: t
a
k
e
c
h
e
c
k
p
o
i
n
t
s剖 showni
nF
i
g
u
r
e7
.H
e
r
e，
i
f0 becomes
，
0 i
sr
o
l
l
e
db
a
c
kt
ot
h
ec
h
e
c
k
p
o
i
n
色C
iwhicbi
s
f
a
u
l
t
y
もr
e
c
e
nt
1yもakenby0・
，O
is
e
n
d
sani
n
f
t
u
e
n
t
i
a
lm
e
s
mos
s
a
g
e7
'
l
'
1
¥
もoOj a
f
t
e
rc
l
.向日nds句 i
nSL~ s
i
n
c
eT
n
ii
s
0 s
e
n
d
sR-Reqt
o0; w
i
t
bv
e
c
t
o
r
s
i
n
f
l
.u
e
n
t
i
a
l
. Then，
C
p (
1，
0，
0
)and刊 =(
1，
0，
0
)
.Onr
e
c
e
i
p
もo
fR・Req
丘omoi，
句 f
i
n
d
sano
l
d
e
s
もl
o
c
a
lc
h
e
c
k
p
o
i
n
tc
{wbere
C
p 1b
e
c
a
u
s
eR
R
e
q
.C!pi 1
.S
i
n
c
ef
f
l
ii
nRL'i
si
n
句 i
sr
o
l
l
e
db
a
c
kt
o~. R-Req・川 1
.Then，
f
t
u
e
n
t
i
a
l，
句 s
e
n
d
sR~Req t
oOJ
:i
fm;i
si
n
f
l
u
e
凶 a
l
.Onr
e
c
e
i
p
むd
R・ReqfromO
j，
01
:i
sr
o
l
l
e
db
a
c
k初七hec
h
e
c
k
p
o
i
n
tc~
i
fm;i
si
n
到u
e
n
t
i
a
l
.0むb
e
r
w
i
s
e，
OJ
:j
u
s
td
i
s
c
a
r
d
sR-Req
andc
o
n
t
i
n
u
et
h
ec
o
m
p
u
t
a
t
i
o
n
.
，
=
，
=
[
8
]L
i
n，L
. andAhamad，
M.“
，Cbeckpointingand
R
o
l
l
b
a
c
k
R
e
c
o
v
e
r
yi
nD
i
s
t
r
i
b
u
t
e
dO
b
j
e
c
tB錨 e
d
S
y
s
t
e
m
s，
"Proc.0
1IEEESRD5
.
・9
，
p
p
.9
7
1
0
4，
1
9
9
0
.
，
[
9
]Leong，
H
.V
.andAgrawal，
D
.
“
，UsingMessage
S
e
m
a
n
t
i
c
st
oReduceRo
l
l
b
a
c
ki
nO
p
t
i
m
i
s
色i
cMe
s
s
a
g
eL
o
g
g
i
n
gR
e
c
o
v
e
r
ySchemes，
"P
r
o
c
.ollEEE
p
p
.
2
2
7
2
3
4，
1
9
9
4
.
IODOS-14，
，
=
=
6 ConcludingRemarks
. and S
i
n
g
h
a
l，M.，
“A Low[
1
0
] Manivannan，D
回 i
Overtead R
e
c
o
v
e
r
yT
e
c
h
n
i
q
u
eU
s
i
n
g Qu
~~I!chronous C
h
e
c
k
p
o
i
n
t
i
n
g，
"P
r
o
c
.0
1 IEEE
ICDOS
・
1
6，
p
p
.
1
0
0
1
0
7，
1
9
9
6
.
[
1
1
] Ra
manathan，
P
.andS
h
i
nK
.G
.
“
，Checkpoinレ
s
i
n
gandR
o
l
l
b
a
c
kR
e
c
o
v
e
r
yi
naD
i
s
t
r
i
b
u
t
e
dSy
temUs
i
n
gCommonTimeB踊 e
，
"Proc.0
1IEEE
・7
，
p
p
.1
3
2
1，
1
9
8
8
.
SRDS
. and T
a
k
i
z
a
w
a
，M.，
“Distributed
[
1
2
]T， 卸aka，K
"
C
h
e
c
k
p
o
i
n
t
i
n
gBased onI
n
f
l
.
u
e
n
t
i
a
lM
e
s
s
a
g
e
s，
P
r
o
c
.ollEEEICPADS'96，
p
p
.4
4
0
4
4
7
，
1
9
9
6
.
Weh
a
v
ed
i
s
c
u
s
s
e
dhowもot
a
k
eo
b
j
e
c
t
b
u
e
dc
o
n
s
i
s
t
e
n
t
・c
o
n
s
i
s
t
e
n
t
)c
h
e
c
k
p
o
i
n
t
sw
h
i
c
hc
a
nb
e
_t
a
k
e
nfrom
(0
も
i
o
np
o
i
n
to
fv
i
e
wbutmaybei
n
c
o
n
s
i
s
t
h
ea
p
p
l
i
c
a
t
e
n
twi
七ht
h
et
r
a
d
i
t
i
o
n
a
lm
e
s
s
a
g
e
b
a
s
e
d
d
e
f
i
n
i
色i
o
n
.We
h
a
v
ed
e
f
i
n
e
d加:
j
l
u
e
n
t
i
t
J
lmeS6tJg
e
6ont
h
eb回 i
so
fもh
e
s
e
m
a
n
t
i
c
so
fr
e
q
u
e
s
旬 a
ndr
e
s
p
o
n
s
e
swhereもbem
e
t
h
o
d
s町 en
e
凶e
dandもh
emethodsa
r
ep
e
r
f
o
r
m
e
dbyt
h
e
r
e
m
o
t
ep
r
o
c
e
d
u
r
ec
a
l
l
. Onlyo
b
j
e
c
t
sr
e
c
e
i
v
i
n
gi
n
f
l
u
e
n
t
i
a
lm
e
s
s
a
g
e
sa
r
er
o
l
l
e
dbacki
f出 es
e
n
d
e
r
so
f出 e
i
n
f
l
.
uen
もi
a
lm
e
s
s
a
g
e
sa
r
er
o
l
l
e
db
a
c
k
.The0・c
o
n
s
I
8
t
e
n
t
h
.e
c
c
1
p
o
i
n
ti
so
n
ewhereもh
e
r
ei
snoorphani
n
f
l
u
e
n
t
i
a
l
c
m
e
s
s
a
g
e
.Weh
a
v
ep
r
e
s
e
n
t
e
dぬe創 刊c
h
r
o
n
o
u
sp
r
o
も
0・
c
o
lf
o
rt
a
k
i
n
g0・c
o
n
s
i
s
t
e
n
tc
h
e
c
k
p
o
i
n旬.
[
1
4
]Wang
，
.
Y
.M.andF吋 叫 W. K
.“
，Optimistic
Mess
暗号 L
o
g
g
i
l
!
gf
?
r I~depend<<mt C
h
e
c
k
p
o
i
n
t
i
n
g1
n
_M
e
s
s
a
g
e
P
剖 s
i
n
gS
y
s
旬 ms
，
"P
r
o
c
.ollEEE
・1
1，
p
p
.1
4
7
・1
5
4，
1
9
9
2
.
SRDS
References
[
1
5
] Weikum
，
G.，
"
P
r
i
n
c
i
p
l
e
sandR
e
a
l
i
z
a
t
i
o
nS
t
r
a
t
e
g_ie~_ :.o~ ~_u!ti!c:v~l .
'þ'~_n8action M
anagement，
"
ACMTODS，
Vo
l
.1
6
，
N
o
.1
，
p
p
.
1
3
2
1
8
，
O 1991
.
[
1
3
]Tanaka
，K.，Higaki，H.，and Takizawa，M.，
“
O
b
j
e
c
t
・B舗 e
dC
h
e
c
k
p
o
i
r
i
t
si
nD
i
s
t
r
i
b
u
旬 dS
y
s
"J0.
1
品
r
n
a
l0
1ComputerSystemsS
c
i
e
n
c
e.
a
nd
tems，
E
n
g
i
n
e
e丙n
9，
V
o
l
.1
3，
N
o
.
3，
p
p
.1
2
5
1
3
1，
1
9
9
8
.
[
1
}Bhargava
，B. and Lian，s
.R.，"Independent
-78-