V N U JO U R N A L OF S C IE N C E . Nat ■ Sci . & Tech . ĩ XIX, N.j4. 2QQ3______________________ ___________________

EVALUATIƠN OF CPM - A COMMIT PROTOCOL
FOK M O B IL E D IS T R IB Ư T E D DATABASE SY S TEM S
Le H u u L a p
pnsts T e lecom m un ica tions In s titu te ()f Technology
N g u v e n K h a c L ic h , T r a n T h e T r u y e n
Research In s tĩtu tv
ilis t.rib u to ỚVer th e fix e d netvvork. b u t some o f the m may be in Nvirtíless n e tw o rk . For
the purpose o f tra n s a c tio n stu d y, th e netvvork can be vievved as a log ica l mess
( K ig u re 2).
Such M I)D B S m u st execute c o m m it protocols to e n su re a to m ic ity a fte r the

traiìsaction executions on data. Typically the commit protocols are based on
m rssage pa ssin# betvveen p n rtic ip n n ts in the tra n s a c tio n , in one o r m ore d iffe re n t
phases such as 1PC (O ne-Phase O o m m it), 2P C (Tw o-P hase C o m m it) and 3PC
(T hree-P hase C o m m it) |4. 5, 10). U n lik e w ith fíxed n e tw o rk f those protocols may
nnt w o rk w e ll in vvireless n ie d iu m and w ith the r ie x ib ility o f User m o h ility fo r
v a rio u s reasons |8, 10j:
•

w ire le s s

co n n e ctio n

is

prone

to

ía ilu re

due

to

the

Le H u u L a p , N guyên K h a c I J c h 9 T r a n The Truyen
Ilì th is p a p e r we e v a lu a te a new co m m it protocol • C P M (C o m m it P rotocol fo r
M o b ile ) th a t is do si^ne d to ove r come some lim ita tio n (>f th e m ost vvrdelv used 2PC
and to a llo w u se r-e n a h le d d isco n n e ctio n s and o fflin e Processing. S ection 2 provides
a sh o rt re v ie w o f s e v rra l c o m m it protocols and p o in ts out d ra w b a c k s o f 2PC in
m o bile c o m p u tin g . S ection 3 describes and analyzes th o th e o re tỉc a l aspects o f th e
C F M . T h e n e x t tw o sections p re se n t th e m o d e lin g and s im u la tio n o f th e C P M .

Figure 2: Logical view o f DDBS

Kigure 1: Generic physical model o f MDDBS

2. C o m m o p itm en t in d is trib u te d transaction Processing
2.1. T r a n s a c tio n M o d e ls
T h e re have been m a ny tra n s a c tio n m odels proposed fo r m o b ile c o m p u tin g [2,
3, 12] th a t c a p tu re cla ssica l tra n s a c tio n m anagem ent íe a tu re s such as co n currency
c o n tro l an d re co ve ry |1Ị and m o b ility . For the purpose o f th is p a per, th e y are
assum ed to a lre a d y e x is t. A d is tr ib u te d tra n s a c tio n T

in itia te d a t a s ite con sists o f

n u m b e r o f íra g m e n ts {T tJ} w h ic h a re d is trib u te d to p a r tic ip a tin g s ite s to execute.
The g e n e ric tra n s a c tio n

m odel considered

a p p lic a tio n s (A P P k/ fo r a r b itr a r v k e

in



E ỉ u Ị iK ítio n ()f ( 'PM

a c o m rn it p r o to e o l fo r ..

;ifte r a ll > itfs in lu rm i h r i r c n m p lc tio n o fT ,. A m o n g th e niost W1 (||*I\ rlcplo yed IS thi*
Ttvo-Phơsc C o n m iit r J lV ) p ro tn m l. w h ií h \ve w ill d e s c rib r in m ore cit»f;ii 1 in thí* next

su h srcĩion. Kvrn thuimlì. 2IH* IS ro n sid e rc d to be i n s u íĩic ir n t b c r a u s e C)f high
c o m m it ro st «1 1 1 ( 1 p o ír u t lỉil (>f 1/0 h ỉo c k in g . T h e re have becn m a n y a tte m p ts to
irn p ro v r th e 2 IH ' and to proposi* a ltc rn a tiv e s to solve these issm \s. Som c a im at
m in im i/m t' n is ts oỉ ||>H w r itin g and C om m unications, in w h ir h P rC (P re sum e d
C o m m it) and K a r lv P rcp a rc |w. 1 ]| an* o f thoso noticeable. O th e r re search in c lu đ e s
1IH 1 and v a ria n ts such iis ( 'L P (C o o rđ in a to r Log P rotocol), and ỈY V P ( Im p lic it YesVoti* P rotocol). 1PC Itf!iurt\s th e P R E P A R K phase o f ‘2 PC b u t its a s s u m p tio n s are too
s tr ic t to be tis H u l in ro m m e rria l svstem s. ỉn c o n tra s t to those ap pro ache s, 3P C
(th re e -p h a se c o m n n t) in tro đ u c e s m ore cost and c o m p le x ity bv an a d d itio n a l phase to
h c lp avoul th e I/O h lo c k in ^ in 2PC.

2.3. T ĩvo p h a s e c o m m i t p r o to c o l
Thi* ro m m it p ro to rn l. as 1 1> nam o in d ic a ỉc s , has tw o phases: th í' f ir s t asks fo r
v o tin g fro m a ll s ite s roíKỈy to c o m m it. and the second c a rry out th e c o m m itm e n t.
P h a s e 1: c o íu lils record « P K K I \ \ R K T , » to the log, w r itc s th e lug to s ta b le
storage and s ta rts a tim e r (F K K P A R E _ T IM E O U T ) th e n sends P R E P A R E message
to a l! T C . O n re e e iv in g such a message, each T ơ decides vvhether o r n o t to c o m m it.
l f the nnsvver is N O . T O ;ul(ls record « N 0 T „ » to th e log and responses A B O R T
T to CO. O th e rw is e . T í ' 1adds record « R E A D Y T „ » to the log a n d forces th e log to
the sta h le storage. T C ' re p lic s K E A D Y T „ to c o .
P h a s e 2 U pon re c e iv in g R E A D Y T,, fro m a ll TC ' w ith in tim e o u t p e rio d , c o
l*orce-\vrites T, log to s ta b lc stnrage. A t th is p o in t, th e fat(» o f th e tra n s a c tio n is
ilu te rm in c d . c o th e n simh I s C O M M IT T, to a ll T C 1. In th e bad ca se, th e P R E P A R E


are

ra th e r

exp e n sive

in

m o bile

Communications in te rm (>f tim e (and possibly m oney since th e m o b ile cost is
u s u a lly d e te rm in e d on th e basis o f connection tim e ).

3.

CPM • Comniit p roto col for m obile tra n sa ctio n m o d els
3.1. T h e C P M C o m m ỉt P ro to c o l
In th e lig h t o f above discu ssio n, it is reasonable to m in im iz e th e need to

co m m u n ica te over w ire le s s lin k and the n u m b e r o f messages p a s s in g in th e netvvork
per tra n s a c tio n . We proposed a novel com m it protocol c a lle d C P M (C o m m it p rotocol
fo r A /obile T ra n s a c tio n s ) th a t avoids th e possible d isc o n n e c tio n s d u rin g th e co m m it
process.

In

a d d itio n

CPM


o f s e n d in g

th e

re st o f

tra n s a c tio n T ầị - T ,k to c o o rd in a to r as in 2PC, T C k d is tr ib u te s those fra g m e n ts to
co rre sp o n d in g p a rtic ip a n ts and s ta rts a T R A N S _ E X E C tim e o u t. Each p a rtic ip a tin g
site executes its p a rt a n d send co m p le tio n message back to th e re q u e s te r.
I f th e T C k receives a ll such messages, it s ta rts th e c o m m it process by sen ding
C O M M IT _R E Q U .E S T message and tra n s a c tio n log to c o . U po n re c e iv in g c o m m it
re que st and tra n s a c tio n log fro m T C k, c o fo re -w rite s th e log to s ta b le storage and
sends C O M M IT message to a ll p a rtic ip a tin g sites. Each s ite th e n c o m m its its
tra n s a c tio n

p o rtio n

T M and

acks

back

to

co

acknow led gem e nts are received a t c o , th e c o


T C k gets

a ll

T R A N S .A C K fro m p j, T C k sends A B O R T message to c o and T R A N S _ N O T _ O K to
A P P k. In th is case, c o has n o t logged the tra n s a c tio n y e t. so th e A B O R T message


E v a ỉ u a t i o n ()f C 'ỉ * \ i

a v o m m it p r o to c o l fo r .

m>i‘ds to c a rry a ll n o crssa rv in fo rm ;itio n ab o u t th e ab o rte d tra n s a e tio n (i.e. ID o f
p a r tin p iin ts

U s in ^ g iv rn in fo rm a tio n , c o m u ltic a s ts A B O R T messages to a ll

TC ' {J * h) T ( ’ t h r iì t r lls its co rre s p o n d in g p tơ a b o rt.
As m e iìtio n e d abọvo, tho p a rtic ip a n t P' and the a g ent T ơ a c tin g on its b e h a lf
a r r not n e ce ssa rily at t h i’ sanu' s it t \ so d u rin g the c o m m it process, p* m ay fa il and
m ay Iio t v e n tv th e c-ommit w ith T O . So T C J needs to use a C ()M M !T _ K X E C tim c o u t
vvhriì c o m m a n d in g r

Upon re c e iv in g such com m and, p rin is h e s its tra n s a c tio n

p o rtio n a n d th e n lo tf-w rite s a “ c o m m it” . The tra n s a c tio n p o rtio n is done. I f the
lim e o u t is passed and P' has not c o n firm e d th e c o m m it, T C 1 assum es th e ĩa ilu re o f
l >!. T C th e n checks the existonce o f “ c o m m it'’ log a t P \ I f th e log cỉoes no t e x is t, the
T C ’ tu ll p to rtj d() th i' tra n s a rtio n e xe cution and c o m m it prơcedures.
Once re c e iv in g C ()M M IT _ A C K fro m c o . T C k sends T R A N S .O K to A P P k. the


re c é iv in g

.

r-

in s tru c tio n

rr or ĩ ì TC

i n s t r u c t . i o n . i s TRANS OK)
s t a r t new t r a n s a c t i o n a f t e r

//th e

t r a n s a c t io n

restart

a

tim e

in te rv a l

25 a b o rte d

t.ra n s a c tio n


to

TC" w r it e

t:he

a 11

TCk è x t r a c t

s c h ed u ler

«LOG

its

//th is

T ;)

T, »

to

and

p la y s
then

th e


rest
its

tim e r

i f ( t im eout

-

p o rtio n

not

a ll

co rre s p o n d in g

fo r c o n firm a tio n

re c e iv e

a ll

send

ABORT T

TCk


p}

T lk

and w a i t

&Ẳ TC

to

of

T )

TC

k

{Tt l|


Le H u u L a p , N g u y ê n K h a c L ic h , T r a n The T ru y e n

40

b eg in
T C k s e n d COMMI T T ; , a l l <
TC
CO)

b e g in
TC

send

record

«C O M M IT

T .,»

and

c o mm an d C O M M I T
p-

T,

to

p

TC s t a r t t i m e r a n d w a i t f o r a c k o f T j , f r o m
i f (TC
r e c e i v e com m it c o n f i r m a t i o n o f p )
TC1 send
e ls e

end
end

e ls e

/ / T C j r e c e ì v e ABORT Tịj f r o m c o
send ABORT T n t o p j

end
F ig ure 4: C PM a lg o rith m a t tra n sa ctio n c o n tro lle rs (T C k & T C 3)
A c tiv itie s a t P :
b e g in
if( p
r e c e iv e
b e g in
execute
send
wai t

tra n s a c tio n

fragm ent

T,

from

TC )

Tn


•11

À c t i v i í i c s (lí ( ( l i
b e g in
i f ( 0 ’ re^eive ABORT T
i f ( r.




from
T,

TC )

and

T C'

end
end
F ig u re 6: CPM a lg o rith m at co o rd in a to r c o
3.2. C ost a n a ly s ỉs

CPM

2 < n -l)

1+n

2

l+ (n + n_op)

2

w here n op is n u m b e r o f tra n s a c tio n ĩra g m e n ts .
A lth o u g h C F M a llo w s fle x ib le o fflin e P r o c e s s i n g and d is c o n n e c tio n d u rin g
c o m m ittin g , b u t whi*n too m anv tra n s a c tio n s w a itin g to in the c o o rd in a to r queue,
the c o o rd in a to r is forced to c u to ff so me tra n s a c tio n s to avoid process o v e rflo w . The
c u to ff m echanism can be as sim p le as ro u n d -ro b in to rem ove th e ơ ldest ite m in the
queue, b u t th is is open to la te r im p le m e n ta tio n s

4. S im u la tio n m odoling
In a d d itio n to q u a lita tiv e a n a ly s is presented in p rc v io u s sections. we have
q u a n tita tiv e ly in v e s tig a te d th í4 pc»rformance o f C PM in d iffe re n t scenarios and in


Le H ư u L a p t N g u y en K h a c Lichy T r a n The T ru y e n

42

co m p a riso n w ith th e 2 P ( \ Wi* doveloped a D iscrete K vent S im u la to r (I)E S ) th a t


n e tw o rk

is

im p le m e n te d as a ge neric node vvith p rim a ry fu n c tio n a lity o f ro u tin g . F o r s im p lic ity
we do not im p le m e n t a n y m echanism fo r che cking fo r e r ro r a n d message o rd e rin g a t
T ra n s p o rt la y e r as u su al in c o m m u n ic a tio n n e tw o rk , th e loss o f message and
d isco n n e ctio n a n d re co n n e ctio n in w ire le s s lin k are m odeled as s u ffic ie n tlv long
de lay. T h is is because it is u s u a l fo r tra n s p o rt la v e r to assum e message loss based
on tim e o u t w h e n n e tw o rk congestions occur. S im ila rly . h a n d o ff is also m odeled as
long đ e lay vvith th e average d e lay tim e fo r h a n đ o ff is ls . T a k in g in to account the
fact th a t ave rag e v e lo c ity o f m obile users is 3m/s, avcrage c e ll d ia m e te r is a ro u n d
lỉOOm. so th e h a n d o ff ra te is ab o u t one every lOOs.
Each s ittí co n sists o f an a p p lic a tio n APP, a tra n s a c tio n c o n tro lle r T C and a
da tabase (o r p a rtic ip a n t). T ra n s a c tio n s are alvvays in itia te d a t M U a n d the nevv One
is cre a te d

Is a fte r th e c o m p le tio n o r a b o rt o f the p re v io u s . Each p o rtio n T tJ o f

tra n s a c tio n T is a s s ig n e d ^ o a p a rtic ip a n t in the m *tw ork ra n d o m ly , t*xccpt fo r the
o r ig in a tin g si te (M U ), lỉecause th e re are m u ltip le tra n s a c tio n s b e in g c o n c u rre n tly
re q u e stcd a t c o and p a rtic ip a tin g site s, each s ite needs to m a in ta in a tra n s a c tio n
queue. F o r s im p lỉc itv . thí* qucue is im p lc m e n te d on K irs t C om e K irs t Serve (FC FS )
basis. To a v o id po ssible Processing overload. the tra n a a c tio n qu e u e a t c o operates
in ro u n d -ro b in s tra te g y , w here the o ld e s t a v v a itin ^ tra n s a c ỉÌH iì w ill be a b o rte d when
th t‘ queue is fu ll.
A t each s ite , C PU e xccu tio n an d 1/0 ciisk access are im p le m e n te d in m u tu a l
e x c lu sive


ỈAỉự, Kon r \VTIU*

200ms

T r;m s:ictio n S r^ iìirn t K xiTU tion

34ms

T i nu* to Si'í om* lock

lm s

T im e to unlock

1ms

l) ;it;i ()hji*( t updati* t ime

6ms

T ra n sa ctio n Díĩgrec o f (iis trih u tio n

7-10 íra g m e n ts

Messa^e h ỉin d lin ^ tim e

lm s

Averagt* w ireless tra n sm issio n delay



set

to

e v a lu a te

th e

p tT Íb rm a n a * o f tw o c o m m it protocols o f in te re s t: 2PC and C P M . T h e p e rfo rm a n c e is
p r im a r ilv m casured u s in g m e tric oí* tra n s a c tio n th ro u g h p u t pe r I in it o f tim e . O th e r
facto rs includ e p o rtio n o f successful tra nsactio riy average n u n ib e r o f messages p e r
tra n s a c tio n

and

trơ n s a c tio n

tu rn a ro u n d

tim e

(F ig u re

10).

The

tra n s a c tio n


350

F igure 7: Períbrm ance o f 2PC and C PM
under load vvịth norm al disconnection rate
(0.5%)

F ig u re 8: P eríorm ance o f 2PC and C P M
u n d c r load w ith lìi^ h disconnection ra te
(4%)
3500

20

76

50

Number of active MUs

40

60

Number of active paraftel active MUs

F ig u re 9: A veragc n u m b e r o f messages per
tra n sa ctio n

Average transaction turnaround time



s ig n iíìc a n t

de gra de

in

o v e ra ll

system


E v a ỉu u tio n o f CPM

45

a c o m m it p r o to c o l fo r .

2PC under various disconnection

20

F ỉg u re I I : Kffect o f discunnertìon
íìvc|iu*ncy OM o ve rall th ro u g h p u t (handoíT
ra te is ().()])

NumbéKbf MUs

60


T h e p e río rm a n ce ní ( T M u n d e r load vvith d iffe re n t ỉra n s a c tio n d isco nne ction
p ro b a h ility (K ig u re

13) tends to have the same c h a ra c te ris tic s as th a t o f 2PC


Le H u u L a p , N guyên K h a c ỈÁ chi T r a n The T ru y e n
(K ig u re 12). T h a t is thi* vveak c o m m u n ic a tio n m e d iu m m akes th e tim e to reach
m a xim u m th ro u g h p u t lo n g e r and also decreases th e m a x im u m v a lu e .
5.3. S ystem p e r fo r m a n c e in r e la t io n w it h q u e u e 8Ìze a t c o
It

is in tu itiv e

th a t

th e queue size a t c o

in flu e n c e s th e o v e ra ll system

p e ríbrm an ce because o f the ro u n d -ro b in o p e ra tio n . A set o f e x p e rim e n ts has been
conducted to c o n firm th is con clusion (F ig u re 14). T h e o v e ra ll th ro u g h p u t does no t
change w ith queue size w hen the n u m b e r o f p a ra lle l a c tiv e M U s 1 8 s m a ll. H ow eve r,
it appears to d e te rm in e w hen the system degrades u n d e r heavy load. T h e la rg e r
queue size, th e b e tte r it can h a n d le m u ltip le a w a itin g tra n s a c tio n s , vvhich is c le a rly
ro u g h ly

p ro p o rtio n a l

to

40

50

60

o f A C í-ve

Figure 15: Average transaction
F ig u re 14: Inílu en ce o f queue size a t c o on
System th ro u g h p u t

tu rn a ro u n d tim e vvith d iffe re n t queue
size (10,30.50)

5.4. Other experiments
A s ig n iíìc a n t n u m b e r o f o th e r e x p e rín ie n ts have been c a r ric d o u t in c lu d e th e
in v e s tig a tio n s o f v a rio u s s tra tc g ie s to s ta rt an re s ta rt a tra n s a c tio n , d iffe re n t
p ro b a b ilis tic d is tr ib u tio n s o f ra n d o m h a n d o ff and đ is c o n n e c tio n tim e , tim e o u t valu e
analyses and C P U speeds. Those re s u lts a ll e o n íirn i m a in c o n rlu s io n s presen ted in
th is paper, o f w h ic h we s u m m a riz e in n e xt Section.

6. C on clu sio n s and P urth er work
We havt* proposed a new c o m m it protocol fo r rnohile tra n s a c tio n
(C P M ). F ro m th e o re tic a l a n a ly s is and q u a n tita tiv e s tu d y

m odels

u s in g s im u la tio n , we


47

u n d c rs ta n c lin g o f protocol be havio rs and correctn ess u n d e r v a rio u s c o n fig u ra tio n s .
T h ỉ' n u nn re s u ỉts frorn e x p e rim e n ts presented in th is p a p e r are s u m m a riz e d below:
•

M ost ()f the ti me the CPM p e rfo rm s s ig n ific a n tly b e tte r th a n th e classical

2PC under mobile coníigurations.

In adciition, CPM allows offline

Processing and M U -enablecỉ (iisco n n e ctio n d u rin g the c o m n iit tim e .
•

H a n d o ff ratí* is not very c r itic a l in system pe río rm a n ce

•

Disconnections d u rin g t r a n s a c ti o n d e g ra d e t h e p e rí o r m a n c e rapidly.

•

T u rn a ro u n d

ti me tenđs

to

he


tra n s a c tio n

m anagem ent

in

m obile

d is tr ib u te d database system s
•

T h e s o ftw a re vvill ho re -de sig ne d as a fra m e w o rk fo r s im u la te c o m m it
p ro to co ls and to enable th e p ro o í o f correctn ess u s in g m ore p o w e rfu l
te c h n iq u e s such as Colored P e tri nets [7ị.

R efer en ces
1.

I \ A . B e r n s t e i n , V. Had zi l ac o s, a n d N. G o o d m a n , C o n c u rre n c y c o n tro l a n d recovery in

d a ta b a s e s y s te m s , Adcỉ ison- Wesley, 1987.

2

V K. C hrysanthis, Transaction Processing in mobile com puting environm ent, Proc. IEEE
VVor k s h o p A d v a n c e s in P araỉlel a n d D is tr ib u te d S y s t e m s , Oct . 1 993, pp. 7 7- 8 2 ,

3.



Conference

on

7.

L. M Kristensen, s. Christensen, and K. Jensen, The practitioner guide to coloured
p e t r i nets. I n t. J S 7 7 T ( 1 9 9 8 ) 2 : 98 132.

8

V Kumar, N. Prabhu. M. H Dunham, and A. Y. Seydim, TCOT - A Timeout-Based
mobile transaction commitment protocol, I E E E Transactions on C o m p u t e r s , Vol. 51, No.
10. O c t o b e r 2 0 0 2 .

9

(V Mohan, B, Lindsav and R. Orbermarck, Transaction management in the distributed
đ a t a b a s e m a n a g e m e n t System. A C M T r a n sa c tio n s on D a ta b a s e S y s t e m s , 1986.


Le H u u L a p y N g u y c n K h a c L i c h , T r a n The Truyen

48
10. A. S i b e r s c h a t z , H . F. K o r t h a n d

s.

Sudarshan,

trê n các mô h ìn h giao tác khác nhau, tro n g đó cho phép xù lý ngoại tu y ế n và ngắt kết
nỏì tạ m thờ i tro n g k h i đang thực h iệ n m ột giao dịch dữ liệ u q u a m ạng d i động.
G iao th ứ c C P M có sô lượng bản tin , sô lân v iế t n h ậ t k ý và o bộ nhớ ổn đ ịn h và
chi p h í tru y ề n th ô n g ít hơn 2CP, th íc h hợp với m ôi trư ờ ng tru y ề n th ô n g kém tin cậy
như di động. C P M cho phép động ch ủ động cao hơn từ phía d i động th a y vì lệ thuộc
hoàn to à n vào bộ điề u phối tr u n g tâ m như với 2PC và các giao thứ c khác.
C h ú n g tô i xây đựng một phẩn mềm mô phỏng m ạng d i động theo hướng sự
k iệ n rời rạ c (D E S - D iscre te E ve n t S im u la tio n ) với giao thứ c hợp thứ c 2PC và CPM
ho ạt động trê n đỏ. Các kế t quá mô phòng đà chứng tỏ dược h iệ u s u ấ t cùa C P M cao
hơn 2PC tro n g m ôi trư ờ ng phân tá n d i động.