Post on 29-May-2018
8/8/2019 compu archi
1/25
S p e c i f y i n g a n d E n f o r c i n g I n t e r t a s k D e p e n d e n c i e s
P a u l C . A t t i e ,
1
M u n i n d a r P . S i n g h ,
1
A m i t S h e t h ,
2
a n d M a r e k R u s i n k i e w i c z
3
1 : C a r n o t P r o j e c t , M C C , 3 5 0 0 W . B a l c o n e s C e n t e r D r i v e , A u s t i n , T X 7 8 7 5 9 - 6 5 0 9
2 : B e l l C o m m u n i c a t i o n s R e s e a r c h , 4 4 4 H o e s L a n e , P i s c a t a w a y , N J 0 8 8 5 4 - 4 1 8 2
3 : D e p a r t m e n t o f C o m p u t e r S c i e n c e , U n i v e r s i t y o f H o u s t o n , H o u s t o n , T X 7 7 2 0 4 - 3 4 7 5
e m a i l : a t t i e @ m c c . c o m , m s i n g h @ m c c . c o m , a m i t @ c t t . b e l l c o r e . c o m , m a r e k @ c s . u h . e d u
A b s t r a c t
E x t e n s i o n s o f t h e t r a d i t i o n a l a t o m i c t r a n s a c t i o n m o d e l a r e n e e d e d t o s u p p o r t t h e d e v e l o p -
m e n t o f m u l t i - s y s t e m a p p l i c a t i o n s o r w o r k o w s t h a t a c c e s s h e t e r o g e n e o u s d a t a b a s e s a n d l e g a c y
a p p l i c a t i o n s y s t e m s . M o s t e x t e n d e d t r a n s a c t i o n m o d e l s u s e c o n d i t i o n s i n v o l v i n g e v e n t s o r d e -
p e n d e n c i e s b e t w e e n t r a n s a c t i o n s . I n t e r t a s k d e p e n d e n c i e s c a n s e r v e a s a u n i f o r m f r a m e w o r k f o r
d e n i n g e x t e n d e d t r a n s a c t i o n m o d e l s . I n t h i s p a p e r , w e i n t r o d u c e e v e n t a t t r i b u t e s n e e d e d t o
d e t e r m i n e w h e t h e r a d e p e n d e n c y i s e n f o r c e a b l e a n d t o p r o p e r l y s c h e d u l e e v e n t s i n e x t e n d e d
t r a n s a c t i o n m o d e l s . U s i n g t h e s e a t t r i b u t e s a n d a f o r m a l i z a t i o n o f a d e p e n d e n c y i n t o t h e t e m p o -
r a l l o g i c C T L , w e c a n a u t o m a t i c a l l y s y n t h e s i z e a n a u t o m a t o n t h a t c a p t u r e s t h e c o m p u t a t i o n s
t h a t s a t i s f y t h e g i v e n d e p e n d e n c y . W e s h o w h o w a s e t o f s u c h a u t o m a t a c a n b e c o m b i n e d i n t o
a s c h e d u l e r t h a t p r o d u c e s g l o b a l c o m p u t a t i o n s t h a t s a t i s f y a l l r e l e v a n t d e p e n d e n c i e s . W e s h o w
h o w d e p e n d e n c i e s r e q u i r e d t o i m p l e m e n t r e l a x e d t r a n s a c t i o n s s u c h a s S a g a s c a n b e e n f o r c e d
a n d d i s c u s s b r i e y t h e i s s u e s o f c o n c u r r e n c y , s a f e t y a n d r e c o v e r a b i l i t y .
8/8/2019 compu archi
2/25
1 I n t r o d u c t i o n
O n e o f t h e m a i n o b j e c t i v e s o f t h e C a r n o t p r o j e c t a t M C C i s t o p r o v i d e a n e n v i r o n m e n t f o r t h e
d e v e l o p m e n t o f a p p l i c a t i o n s t h a t n e e d t o a c c e s s r e l a t e d i n f o r m a t i o n s t o r e d i n m u l t i p l e e x i s t i n g
s y s t e m s C a 9 1 ] . A n i m p o r t a n t c o m p o n e n t o f t h i s e o r t i s a f a c i l i t y f o r r e l a x e d t a s k m a n a g e m e n t
A t a s k i s a n y u n i t o f c o m p u t a t i o n t h a t p e r f o r m s s o m e u s e f u l f u n c t i o n i n a s y s t e m . T h e t a s k s t h a t
a r e o f p a r t i c u l a r i n t e r e s t t o u s a r e d a t a b a s e t r a n s a c t i o n s . T o e c i e n t l y d e v e l o p s u c h m u l t i - s y s t e m
a p p l i c a t i o n s a c c e s s i n g t h e e x i s t i n g h e t e r o g e n e o u s a n d c l o s e d
1
s y s t e m s , w e m u s t b e a b l e t o m o d u l a r l y
c a p t u r e t h e e x e c u t i o n c o n s t r a i n t s o f v a r i o u s a p p l i c a t i o n s . T h i s c a n b e a c h i e v e d b y m o d e l i n g t h e m
a s r e l a x e d t r a n s a c t i o n s c o n s i s t i n g o f r e l a t e d t a s k s e x e c u t e d o n d i e r e n t s y s t e m s .
I t s h o u l d b e n o t e d , t h a t t h e r e q u i r e m e n t s o f t h e t r a d i t i o n a l t r a n s a c t i o n m o d e l b a s e d o n f u l l
i s o l a t i o n , a t o m i c c o m m i t m e n t a n d g l o b a l s e r i a l i z a b i l i t y m a y b e e i t h e r t o o s t r o n g , o r n o t s u c i e n t
f o r a p a r t i c u l a r m u l t i - s y s t e m a p p l i c a t i o n . F o r e x a m p l e , a n a p p l i c a t i o n m a y n e e d t o e n s u r e t h a t
t w o t a s k s c o m m i t o n l y i n a c e r t a i n t e m p o r a l o r d e r . A n e x a m p l e i s a b a n k i n g a p p l i c a t i o n i n w h i c h
d e p o s i t s m a d e i n t o a n a c c o u n t o v e r a c e r t a i n p e r i o d m a y h a v e t o b e p r o c e s s e d b e f o r e d e b i t s c a n
b e m a d e f r o m t h e a c c o u n t o v e r t h e s a m e p e r i o d . T h e r e f o r e , w e m a y n e e d t o s e l e c t i v e l y r e l a x t h e
A C I D p r o p e r t i e s G r a 8 1 , H R 8 3 ] f o r m u l t i - s y s t e m t r a n s a c t i o n s t o c a p t u r e p r e c i s e l y t h e s y n c h r o n y
a n d c o u p l i n g r e q u i r e m e n t s b a s e d o n t h e t r u e a p p l i c a t i o n s e m a n t i c s . T h e s e m a n t i c c o n s t r a i n t s m a y
b e s p e c i e d a s i n t e r t a s k d e p e n d e n c i e s , w h i c h a r e c o n s t r a i n t s o v e r s i g n i c a n t t a s k e v e n t s , s u c h a s
c o m m i t a n d a b o r t .
T h e c o n c o m i t a n t r e d u c t i o n i n s e m a n t i c c o n s t r a i n t s a c r o s s t a s k s m a k e s p o s s i b l e t h e g e n e r a -
t i o n o f s c r i p t s t h a t c a n b e e c i e n t l y e x e c u t e d w i t h a h i g h l e v e l o f p a r a l l e l i s m . T h i s , i n t u r n , m a y
r e s u l t i n a h i g h e r a v a i l a b i l i t y o f d a t a , b e t t e r r e s p o n s e t i m e s a n d a h i g h e r t h r o u g h p u t . T h e m o d e l i n g
o f c o m p l e x t e l e c o m m u n i c a t i o n a p p l i c a t i o n s i s d i s c u s s e d i n A N R S 9 2 ] w h e r e i t i s a r g u e d t h a t m a n y
m u l t i - s y s t e m a p p l i c a t i o n s c a n b e e c i e n t l y m o d e l e d a n d e x e c u t e d a s r e l a x e d t r a n s a c t i o n s .
T o i l l u s t r a t e t h e s e c o n c e p t s , l e t u s c o n s i d e r t h e f o l l o w i n g s c e n a r i o . A t r a v e l a g e n c y m a i n t a i n s
t w o d a t a b a s e s : o n e c o n t a i n i n g d e t a i l e d i n f o r m a t i o n a b o u t t h e b o o k i n g s m a d e b y d i e r e n t a g e n t s a n d
a n o t h e r c o n t a i n i n g a s u m m a r y o f t h e i n f o r m a t i o n i n t h e r s t d a t a b a s e w i t h t h e n u m b e r o f b o o k i n g s
p e r a g e n t . W h e n t h e s u m m a r y c h a n g e s , a t a s k i s r u n t h a t s e t s o a n a l a r m i f t h e s u m m a r y f a l l s
b e l o w a p r e s e t t h r e s h o l d . A n o b v i o u s i n t e g r i t y c o n s t r a i n t i s t h a t f o r e a c h t r a v e l a g e n t , t h e n u m b e r
o f r o w s i n t h e b o o k i n g s d a t a b a s e s h o u l d b e e q u a l t o t h e n u m b e r o f b o o k i n g s s t o r e d f o r t h a t a g e n t
i n t h e s u m m a r y d a t a b a s e .
A s s u m i n g t h a t i t h o l d s i n i t i a l l y , t h e m a i n t e n a n c e o f t h i s c o n s t r a i n t c a n b e a s s u r e d b y e x -
e c u t i n g a l l t h e u p d a t e s t o b o t h d a t a b a s e s a s a t o m i c m u l t i d a t a b a s e t r a n s a c t i o n s t h a t a r e g l o b a l l y
s e r i a l i z a b l e B S 8 8 ] . T h i s , h o w e v e r , m a y b e v e r y i n e c i e n t o r e v e n i m p o s s i b l e , i f t h e d a t a b a s e
1
I n m a n y s u c h s y s t e m s , t h e d a t a c a n b e a c c e s s e d o n l y t h r o u g h t h e e x i s t i n g i n t e r f a c e s , e v e n i f i t i s i n t e r n a l l y s t o r e d
u n d e r t h e c o n t r o l o f a g e n e r a l p u r p o s e D a t a b a s e M a n a g e m e n t S y s t e m ( D B M S ) . S u c h s y s t e m s a r e f r e q u e n t l y r e f e r r e d
t o a s l e g a c y s y s t e m s a n d t h e a p p l i c a t i o n s t h a t a c c e s s s e v e r a l o f t h e m a r e c a l l e d w o r k o w s
1
8/8/2019 compu archi
3/25
i n t e r f a c e s d o n o t p r o v i d e v i s i b l e t w o - p h a s e c o m m i t f a c i l i t i e s . I n s t e a d , w e m a y a s s u m e t h a t t h e i n -
t e r d a t a b a s e i n t e g r i t y i s m a i n t a i n e d b y e x e c u t i n g s e p a r a t e t a s k s t h a t o b e y t h e a p p r o p r i a t e i n t e r t a s k
d e p e n d e n c i e s . T h e s e d e p e n d e n c i e s s t a t e t h a t i f a d e l e t e t a s k o n t h e b o o k i n g s d a t a b a s e c o m m i t s ,
t h e n a d e c r e m e n t - s u m m a r y t a s k s h o u l d a l s o c o m m i t . F u r t h e r m o r e , i f a d e l e t e t a s k a b o r t s , w h i l e i t s
a s s o c i a t e d d e c r e m e n t - s u m m a r y t a s k c o m m i t s , t h e n w e m u s t r e s t o r e c o n s i s t e n c y b y c o m p e n s a t i n g f o r
t h e s p u r i o u s d e c r e m e n t . W e d o t h i s b y e x e c u t i n g a n i n c r e m e n t - s u m m a r y t a s k . F i g u r e 1 s h o w s t h e
t a s k s i n v o l v e d i n t h i s e x a m p l e ; d B , d S , i S , a n d u ? a d e n o t e t h e d e l e t e - b o o k i n g , d e c r e m e n t - s u m m a r y ,
i n c r e m e n t - s u m m a r y , a n d u p d a t e - a l a r m t a s k s , r e s p e c t i v e l y .
P
P
P
P
P
P
P
P
P
P
P
-
-
D E L E T E
B O O K I N G
d e l e t e
b o o k i n g
( d B )
d e c r e m e n t
s u m m a r y
( d S )
u p d a t e
i n c r e m e n t u p d a t e
a l a r m
( u ? a )
a l a r m
( u ? a )
s u m m a r y
( i S )
F i g u r e 1 : T a s k G r a p h f o r t h e D e l e t e B o o k i n g E x a m p l e
W e m o d e l e a c h i n t e r t a s k d e p e n d e n c y a s a d e p e n d e n c y a u t o m a t o n , w h i c h i s a n i t e s t a t e
a u t o m a t o n w h o s e p a t h s r e p r e s e n t t h e c o m p u t a t i o n s t h a t s a t i s f y t h e d e p e n d e n c y . E a c h s u c h a u -
t o m a t o n e n s u r e s t h a t i t s c o r r e s p o n d i n g d e p e n d e n c y i s n o t v i o l a t e d , b y p e r m i t t i n g o n l y t h o s e e v e n t s
w h o s e e x e c u t i o n w o u l d n o t l e a d t o t h e v i o l a t i o n o f t h e d e p e n d e n c y . T h e s c h e d u l e r r e c e i v e s e v e n t s
c o r r e s p o n d i n g t o a p o s s i b l e t a s k e x e c u t i o n . I t q u e r i e s t h e a p p l i c a b l e d e p e n d e n c y a u t o m a t a t o d e -
t e r m i n e w h e t h e r t h e y a l l a l l o w t h e e v e n t t o b e e x e c u t e d . I f s o , t h e e v e n t i s e x e c u t e d ; o t h e r w i s e , i t
i s d e l a y e d a n d i t s e x e c u t i o n r e - a t t e m p t e d l a t e r .
I n t h i s p a p e r , w e p r e s e n t a f r a m e w o r k i n w h i c h d e p e n d e n c i e s c a n b e s t a t e d m o d u l a r l y a s
c o n s t r a i n t s a c r o s s t a s k s . W e a l s o p r e s e n t a s c h e d u l e r t h a t e n f o r c e s a l l s t a t e d d e p e n d e n c i e s a n d
a s s u r e s t h a t a d y n a m i c a l l y c h a n g i n g c o l l e c t i o n o f t a s k s i s e x e c u t e d i n a c c o r d a n c e w i t h a s e t o f
i n t e r t a s k d e p e n d e n c i e s . T h e s c h e d u l e r d o e s t h i s b y a c c e p t i n g , r e j e c t i n g , o r d e l a y i n g s i g n i c a n t
e v e n t s s o t h a t t h e r e s u l t i n g g l o b a l c o m p u t a t i o n s a t i s e s a l l o f t h e d e p e n d e n c i e s .
2
8/8/2019 compu archi
4/25
T h e r e s t o f t h e p a p e r i s o r g a n i z e d a s f o l l o w s . S e c t i o n 2 p r o v i d e s t h e t e c h n i c a l a n d m e t h o d -
o l o g i c a l b a c k g r o u n d f o r o u r w o r k a n d g i v e s a n e x a m p l e o f i t s a p p l i c a t i o n . S e c t i o n 3 d e s c r i b e s h o w
w e f o r m a l l y s p e c i f y d e p e n d e n c i e s , d i s c u s s e s t h e i m p o r t a n t i s s u e o f e v e n t a t t r i b u t e s , t h e i r i m p a c t
o n t h e e n f o r c e a b i l i t y o f d e p e n d e n c i e s , a n d c o n s i d e r s h o w d e p e n d e n c i e s c a n b e a d d e d o r r e m o v e d a t
r u n - t i m e . S e c t i o n 4 g i v e s a f o r m a l d e n i t i o n o f a d e p e n d e n c y a u t o m a t o n , w h i c h w e u s e t o r e p r e s e n t
e a c h d e p e n d e n c y ; i t a l s o s h o w s h o w d e p e n d e n c y a u t o m a t a o p e r a t e a n d e n f o r c e t h e i r c o r r e s p o n d i n g
d e p e n d e n c i e s . S e c t i o n 5 p r e s e n t s o u r e x e c u t i o n m o d e l a s w e l l a s t h e n o t i o n o f v i a b l e p a t h s e t s , w h i c h
w e u s e a s a c o r r e c t n e s s c r i t e r i o n . I t f o r m a l i z e s t h e s e d e n i t i o n s a n d u s e s t h e m i n t h e d e n i t i o n o f a
s c h e d u l e r a l g o r i t h m .
2
I t a l s o s h o w s h o w a r e l a x e d t r a n s a c t i o n m o d e l s u c h a s t h e S a g a s G S 8 7 ] c a n
b e d e s c r i b e d ( a n d h e n c e e n f o r c e d ) a s a s e t o f d e p e n d e n c i e s . S e c t i o n 6 b r i e y d i s c u s s e s t h e c o n c u r -
r e n c y c o n t r o l , s a f e t y a n d r e c o v e r y i s s u e s i n t h e c o n t e x t o f e x i b l e t r a n s a c t i o n J N R S 9 1 ] . S u m m a r y
a n d c o n l u s i o n s a r e p r e s e n t e d i n S e c t i o n 7 .
2 B a c k g r o u n d
T h e s p e c i c a t i o n a n d e n f o r c e m e n t o f i n t e r t a s k d e p e n d e n c i e s h a s r e c e n t l y r e c e i v e d c o n s i d e r a b l e
a t t e n t i o n C R 9 0 , D H L 9 0 , E l 9 2 , K l 9 1 ] . F o l l o w i n g K l 9 1 ] a n d C R 9 2 ] , w e s p e c i f y i n t e r t a s k d e p e n -
d e n c i e s a s c o n s t r a i n t s o n t h e o c c u r r e n c e a n d t e m p o r a l o r d e r o f c e r t a i n s i g n i c a n t e v e n t s s p e c i e d
o n a p e r - t a s k b a s i s . K l e i n h a s p r o p o s e d t h e f o l l o w i n g t w o p r i m i t i v e s K l 9 1 ] :
1 e
1
! e
2
: I f e
1
o c c u r s , t h e n e
2
m u s t a l s o o c c u r . T h e r e i s n o i m p l i e d o r d e r i n g o n t h e o c c u r r e n c e s
o f e
1
a n d e
2
2 e
1
< e
2
: I f e
1
a n d e
2
b o t h o c c u r , t h e n e
1
m u s t p r e c e d e e
2
E x a m p l e s o f t h e e x e c u t i o n d e p e n d e n c i e s d e n e d i n t h e l i t e r a t u r e i n c l u d e :
C o m m i t D e p e n d e n c y C R 9 2 ] : T r a n s a c t i o n A i s c o m m i t - d e p e n d e n t o n t r a n s a c t i o n B , i i f
b o t h t r a n s a c t i o n s c o m m i t , t h e n A c o m m i t s b e f o r e B c o m m i t s . L e t t h e r e l e v a n t s i g n i c a n t
e v e n t s b e d e n o t e d a s c m
A
a n d c m
B
. T h i s c a n b e e x p r e s s e d a s c m
A
< c m
B
A b o r t D e p e n d e n c y C R 9 2 ] : T r a n s a c t i o n A i s a b o r t - d e p e n d e n t o n t r a n s a c t i o n B , i i f B
a b o r t s , t h e n A m u s t a l s o a b o r t . L e t t h e s i g n i c a n t e v e n t s h e r e b e a b
A
a n d a b
B
, s o t h i s c a n
b e w r i t t e n a b
B
! a b
A
C o n d i t i o n a l E x i s t e n c e D e p e n d e n c y K l 9 1 ] : I f e v e n t e
1
o c c u r s , t h e n i f e v e n t e
2
a l s o o c c u r s ,
t h e n e v e n t e
3
m u s t o c c u r . T h a t i s , t h e e x i s t e n c e d e p e n d e n c y b e t w e e n e
2
a n d e
3
c o m e s i n t o
f o r c e i f e
1
o c c u r s . T h i s c a n b e w r i t t e n e
1
! ( e
2
! e
3
)
2
T h i s p a p e r i s a s l i g h t l y r e v i s e d a n d a b b r e v i a t e d v e r s i o n o f t h e r e p o r t A S R S 9 2 ] a v a i l a b l e f r o m t h e a u t h o r s . T h e
r e p o r t c o n t a i n s c o m p l e t e p r o o f s o f t h e t h e o r e m s m e n t i o n e d h e r e .
3
8/8/2019 compu archi
5/25
T h e a b o v e p r i m i t i v e s a r e i m p o r t a n t b e c a u s e t h e y c a n c a p t u r e m a n y o f t h e s e m a n t i c c o n -
s t r a i n t s e n c o u n t e r e d i n p r a c t i c e . A n y u s e f u l f r a m e w o r k f o r i n t e r t a s k d e p e n d e n c i e s s h o u l d b e a t
l e a s t a s p o w e r f u l . O u r a p p r o a c h d e s c r i b e d b e l o w m e e t s t h i s c r i t e r i o n : t h e a b o v e p r i m i t i v e s a r e
s p e c i a l c a s e s o f o u r f o r m a l i s m .
s t
C o m m i t t e d
D o n e
A b o r t e d
E x e c u t i n g
N o t e x e c u t i n g
a b
*
J
J
J
J
J
J
J
J
J]
H
H
H
H
H
HY
d n
c m
a b
6
6
F i g u r e 2 : A n E x a m p l e T a s k S t a t e T r a n s i t i o n D i a g r a m
T h e r e l a t i o n s h i p s b e t w e e n s i g n i c a n t e v e n t s o f a t a s k c a n b e r e p r e s e n t e d b y a t a s k s t a t e
t r a n s i t i o n d i a g r a m w h i c h i s a n a b s t r a c t r e p r e s e n t a t i o n o f t h e a c t u a l t a s k t h a t h i d e s i r r e l e v a n t
d e t a i l s o f i t s s e q u e n t i a l c o m p u t a t i o n s . E x e c u t i o n o f t h e e v e n t c a u s e s a t r a n s i t i o n o f t h e t a s k t o
a n o t h e r s t a t e . F i g u r e 2 s h o w s a n e x a m p l e t a s k s t a t e t r a n s i t i o n d i a g r a m t a k e n f r o m K l 9 1 ] . F r o m
i t s i n i t i a l s t a t e ( a t t h e b o t t o m o f t h e d i a g r a m ) , t h e t a s k r s t e x e c u t e s a s t a r t e v e n t ( s t ) . O n c e t h e
t a s k h a s s t a r t e d , i t w i l l e v e n t u a l l y e i t h e r r o l l b a c k , a s r e p r e s e n t e d b y t h e a b t r a n s i t i o n , o r n i s h ,
a s r e p r e s e n t e d b y t h e d n t r a n s i t i o n ( f o r \ d o n e " ) . W h e n a t a s k i s d o n e , i t c a n e i t h e r c o m m i t , i . e . ,
m a k e t h e c m t r a n s i t i o n , o r a b o r t , i . e . , m a k e t h e a b t r a n s i t i o n .
D e p e n d i n g o n t h e c h a r a c t e r i s t i c s o f t h e l o c a l s y s t e m a t w h i c h t h e t a s k i s e x e c u t i n g , t h e
s e t o f t r a n s i t i o n s a n d t h e s e t o f s i g n i c a n t e v e n t s o f a t a s k m a y b e d i e r e n t . O u r a p p r o a c h ( a n d
o u r i m p l e m e n t a t i o n ) a c c e p t s t a s k s t h a t a r e c h a r a c t e r i z e d b y a n a r b i t r a r y s e t o f t a s k s t a t e s a n d
s i g n i c a n t t a s k s e v e n t s .
U s i n g t h e s t a t e t r a n s i t i o n d i a g r a m s a n d s i g n i c a n t e v e n t s d e n e d a b o v e , w e c a n r e p r e s e n t
t h e t r a v e l a g e n t a p p l i c a t i o n d e s c r i b e d i n t h e p r e v i o u s s e c t i o n a s s h o w n i n F i g u r e 3 . T h e i n t e r t a s k
d e p e n d e n c i e s a r e s h o w n a s \ l i n k s " b e t w e e n s i g n i c a n t e v e n t s o f v a r i o u s t a s k s .
3 I n t e r t a s k D e p e n d e n c y D e c l a r a t i o n s
A s d i s c u s s e d i n S e c t i o n 2 , w e s p e c i f y i n t e r t a s k d e p e n d e n c i e s a s c o n s t r a i n t s o n t h e o c c u r r e n c e a n d
t e m p o r a l o r d e r o f e v e n t s . L e t e , e
i
, e
j
, e t c . d e n o t e a n y s i g n i c a n t e v e n t ( o r w h e n n o a m b i g u i t y ,
j u s t e v e n t ) a n d D ( e
1
; ; e
n
) d e n o t e a n u n s p e c i e d d e p e n d e n c y o v e r e
1
; ; e
n
. W e a s s u m e t h a t
4
8/8/2019 compu archi
6/25
!
!
!
!
!
P
P
P
P
P
P
P
P
P
P
-
-
@
@
@
@
@
@
@
@
@
@R
@
@
@
@
@
@
@
@
@
@R
/
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
C
CW
?
?
?
?
?
?
?
?
?
?
6
6
A
A
A
A
A
A
AK
@
@
@I
?
?
?
6
6
A
A
A
A
A
A
AK
@
@
@I
?
?
?
6
6
A
A
A
A
A
A
AK
@
@
@I
?
?
?
6
6
A
A
A
A
A
A
AK
@
@
@I
?
?
?
6
6
A
A
A
A
A
A
AK
@
@
@I
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
F i g u r e 3 : D e p e n d e n c i e s B e t w e e n S i g n i c a n t E v e n t s i n t h e D e l e t e B o o k i n g E x a m p l e
a n e v e n t c a n o c c u r a t m o s t o n c e i n a n y p o s s i b l e e x e c u t i o n o f t h e s y s t e m . T h i s i s n o t a r e s t r i c t i o n
i n r e a l t e r m s . I f a t a s k a b o r t s a n d m u s t b e r e - e x e c u t e d , a n e w i d m a y b e g e n e r a t e d f o r i t ( a n d f o r
i t s e v e n t s ) . T h e d e p e n d e n c i e s c a n b e a p p r o p r i a t e l y m o d i e d a n d e v e r y t h i n g c a n p r o c e e d n o r m a l l y .
3 . 1 F o r m a l S p e c i c a t i o n o f D e p e n d e n c i e s
W e a d o p t t h e l a n g u a g e o f C o m p u t a t i o n T r e e L o g i c ( C T L ) a s t h e l a n g u a g e i n w h i c h t h e s e d e p e n d e n -
c i e s w i l l b e e x p r e s s e d E m 9 0 ] . C T L i s a p o w e r f u l l a n g u a g e , w e l l - k n o w n f r o m d i s t r i b u t e d c o m p u t i n g .
A b r i e f d e s c r i p t i o n o f C T L a n d m o d e l i n g o f v a r i o u s d e p e n d e n c i e s i s g i v e n i n A p p e n d i x A . T h e p r i m -
i t i v e s
8/8/2019 compu archi
7/25
t h e p e r s o n w h o s p e c i e s d e p e n d e n c i e s .
3 . 2 E n f o r c e a b l e D e p e n d e n c i e s
T h e s c h e d u l e r e n f o r c e s a d e p e n d e n c y b y v a r i o u s l y a l l o w i n g , d e l a y i n g , r e j e c t i n g , o r f o r c i n g e v e n t s t o
o c c u r , s o t h a t t h e r e s u l t i n g c o m p u t a t i o n s a t i s e s t h e g i v e n d e p e n d e n c y . S o m e s y n t a c t i c a l l y w e l l -
f o r m e d d e p e n d e n c i e s m a y n o t b e e n f o r c e a b l e a t r u n - t i m e . F o r e x a m p l e , t h e d e p e n d e n c y a b ( T
1
) !
c m ( T
2
) i s n o t e n f o r c e a b l e , b e c a u s e a s c h e d u l e r c a n n e i t h e r p r e v e n t a b ( T
1
) f r o m o c c u r r i n g n o r
g u a r a n t e e t h e o c c u r r e n c e o f c m ( T
2
) . T h i s i s b e c a u s e , i n g e n e r a l , a s c h e d u l e r c a n n o t p r e v e n t u s e r
t a s k s f r o m u n i l a t e r a l l y d e c i d i n g t o a b o r t . T h u s b o t h T
1
a n d T
2
c a n a b o r t .
W e a s s o c i a t e w i t h e a c h s i g n i c a n t e v e n t t y p e t h e f o l l o w i n g a t t r i b u t e s :
F o r c i b l e : t h e s y s t e m c a n a l w a y s f o r c e t h e e x e c u t i o n o f a n e v e n t o f t h i s t y p e .
R e j e c t a b l e : t h e s y s t e m c a n a l w a y s r e j e c t a n e v e n t o f t h i s t y p e .
D e l a y a b l e : t h e s y s t e m c a n d e l a y e x e c u t i o n o f a n e v e n t o f t h i s t y p e .
W e a s s u m e t h a t e v e r y n o n - r e a l - t i m e s i g n i c a n t e v e n t i s d e l a y a b l e . T h i s a s s u m p t i o n i s u n a v o i d a b l e
i n a n y m o d e l i n w h i c h e v e n t e x e c u t i o n i s s u b j e c t t o t h e c o n t r o l o f a n e n t i t y ( i . e . , t h e s c h e d u l e r )
o t h e r t h a n t h e t a s k t h a t i s s u e s t h e e v e n t .
I n t h e d i s c u s s i o n b e l o w w e a s s u m e t h a t t h e s y s t e m s o n w h i c h t h e t a s k s a r e e x e c u t e d p r o v i d e
a p r e p a r e d - t o - c o m m i t s t a t e a n d a t a s k c a n i s s u e a p r e p a r e - t o - c o m m i t p r e v e n t . T h e p r e p a r e d -
t o - c o m m i t s t a t e i s v i s i b l e i f t h e a p p l i c a t i o n t a s k ( t h e s c h e d u l e r ) c a n d e c i d e w h e t h e r t h e p r e p a r e d
t a s k s h o u l d c o m m i t o r a b o r t . W e a l s o d i s t i n g u i s h b e t w e e n s i g n i c a n t e v e n t s f r o m t a s k s i n i t i a t e d
b y u s e r s ( u s e r e v e n t s ) a n d t h o s e f r o m t a s k s t h a t a r e i n i t i a t e d b y t h e s c h e d u l e r . A n e x a m p l e o f a
s y s t e m - g e n e r a t e d t a s k i s o n e t h a t i s i n v o k e d u n d e r t h e c o n t r o l o f t h e s c h e d u l e r t o r e s t o r e m u t u a l
c o n s i s t e n c y o f d a t a R S K 9 1 ] . T a b l e 1 b e l o w s h o w s t h e a t t r i b u t e s o f t h e s i g n i c a n t e v e n t s o f u s e r
a n d s y s t e m t a s k s u s u a l l y f o u n d i n d a t a b a s e a p p l i c a t i o n s a n d D B M S s .
U s e r T a s k s F o r c i b l e R e j e c t a b l e
c m
p
a b
p r
s t
p
S y s t e m T a s k s F o r c i b l e R e j e c t a b l e
c m
p
a b
p
p r
s t
p p
T a b l e 1 : A t t r i b u t e T a b l e s f o r S i g n i c a n t E v e n t s
N o w w e c a n c h a r a c t e r i z e t h e r u n - t i m e e n f o r c e a b i l i t y o f d e p e n d e n c y D ( e
1
; ; e
n
) i n t e r m s o f
t h e a t t r i b u t e s o f e
1
; ; e
n
d e s c r i b e d a b o v e . I n g e n e r a l , a d e p e n d e n c y c a n b e r u n - t i m e e n f o r c e a b l e
6
8/8/2019 compu archi
8/25
b a s e d o n t h e a t t r i b u t e s o f i t s e v e n t s . F o r e x a m p l e , e
1
! e
2
i s r u n - t i m e e n f o r c e a b l e i f r e j e c t a b l e ( e
1
)
h o l d s , s i n c e w e c a n t h e n d e l a y e
1
u n t i l e
2
i s s u b m i t t e d , a n d r e j e c t e
1
i f w e s e e t h a t t a s k t h a t i s s u e s
e
2
h a s t e r m i n a t e d ( o r t i m e d o u t : s e e b e l o w ) w i t h o u t i s s u i n g e
2
. A l t e r n a t i v e l y , i f e
2
i s f o r c i b l e ,
t h e n w e c a n e n f o r c e e
1
! e
2
a t r u n - t i m e b y f o r c i n g t h e e x e c u t i o n o f e
2
w h e n e
1
i s a c c e p t e d f o r
e x e c u t i o n . Y e t a n o t h e r ( a l t h o u g h s o m e w h a t v a c u o u s ) s t r a t e g y w o u l d b e t o u n c o n d i t i o n a l l y r e j e c t
e
1
. T h i s s t r a t e g y i s a l s o a n o p t i o n w h e n r e j e c t a b l e ( e
1
) h o l d s .
A s a n o t h e r e x a m p l e , c o n s i d e r e
1
< e
2
. T h e r e a r e t w o p o s s i b l e s t r a t e g i e s f o r e n f o r c i n g t h i s
d e p e n d e n c y . T h e r s t o n e , w h i c h c a n b e a p p l i e d f o r a n y e v e n t a t t r i b u t e s , i s t o d e l a y e
2
u n t i l
e i t h e r e
1
h a s b e e n a c c e p t e d f o r e x e c u t i o n , o r t a s k 1 h a s t e r m i n a t e d w i t h o u t i s s u i n g e
1
. T h e s e c o n d
s t r a t e g y w h i c h c a n b e a p p l i e d i f r e j e c t a b l e ( e
1
) h o l d s , i s t o l e t e
2
b e e x e c u t e d w h e n i t i s s u b m i t t e d
a n d t h e r e a f t e r r e j e c t e
1
i f i t i s s u b m i t t e d .
O n e w a y t o e x t e n d o u r a p p r o a c h t o a c c o u n t f o r r e a l - t i m e d e p e n d e n c i e s i s b y c o n s i d e r i n g
r e a l - t i m e e v e n t s , s u c h a s c l o c k t i m e s ( e . g . , 5 : 0 0 p . m . ) , a s r e g u l a r e v e n t s t h a t l a c k t h e a t t r i b u t e
o f d e l a y a b i l i t y . C o n s i d e r t h e d e p e n d e n c y e
1
< e
2
, w h e r e e
2
i s n o n - d e l a y a b l e . T h i s d e p e n d e n c y i s
e n f o r c e a b l e o n l y i f e
1
i s r e j e c t a b l e . T h e s c h e d u l e r c a n e n f o r c e e
1
< e
2
b y a c c e p t i n g e
1
i f e
2
h a s n o t
a l r e a d y o c c u r r e d a n d b y r e j e c t i n g e
1
o t h e r w i s e .
3 . 3 D y n a m i c A d d i t i o n a n d R e m o v a l o f D e p e n d e n c i e s
T h e p r e c e d i n g e x p o s i t i o n h a s i m p l i c i t l y a s s u m e d t h a t a l l d e p e n d e n c i e s a r e i n i t i a l l y g i v e n , i . e . , a t
c o m p i l e - t i m e . H o w e v e r , d e p e n d e n c i e s m a y b e a d d e d o r d e l e t e d d y n a m i c a l l y a t r u n - t i m e . T h e
a d d i t i o n o f a d e p e n d e n c y r e q u i r e s t h a t a n a u t o m a t o n b e s y n t h e s i z e d f o r i t a n d u s e d i n t h e s c h e d u l -
i n g . T h e r e m o v a l o f a d e p e n d e n c y a t r u n - t i m e i s a c h i e v e d b y s i m p l y r e m o v i n g i t s c o r r e s p o n d i n g
a u t o m a t o n f r o m t h e s c h e d u l e r .
A p o t e n t i a l p r o b l e m i s t h a t a d e p e n d e n c y m a y b e a d d e d t o o l a t e t o b e e n f o r c e d . S u p p o s e
D = e
1
! e
2
i s a d d e d a f t e r e
1
i s e x e c u t e d . N o w i f e
2
i s n o t f o r c i b l e a n d i s n e v e r s u b m i t t e d , D
c a n n o t b e e n f o r c e d . T h i s s i t u a t i o n i s u n a v o i d a b l e i n g e n e r a l , s i n c e t h e a d d i t i o n o f d e p e n d e n c i e s
c a n n o t b e p r e d i c t e d . T h e b e s t w e c a n d o i n s u c h a c a s e , i s t o r e p o r t a v i o l a t i o n i f a n a t t e m p t t o
a d d s u c h a d e p e n d e n c y i s m a d e .
4 D e p e n d e n c y A u t o m a t a : E n f o r c i n g a S i n g l e D e p e n d e n c y
F o r e a c h d e p e n d e n c y D , w e c r e a t e a n i t e s t a t e m a c h i n e A
D
t h a t i s r e s p o n s i b l e f o r e n f o r c i n g D
T h i s c a n b e d o n e e i t h e r m a n u a l l y , o r b y u s i n g a n e x t e n s i o n o f t h e C T L s y n t h e s i s t e c h n i q u e o f
E C 8 2 , E m 9 0 ] t h a t w e h a v e d e v e l o p e d A S R S 9 2 ] . O u r p r o c e d u r e r e q u i r e s o n l y t h e s p e c i c a t i o n o f
t h e d e p e n d e n c i e s , n o t o f t h e t a s k s o v e r w h i c h t h o s e d e p e n d e n c e s a r e d e n e d . A s a r e s u l t , i t g e n e r a t e s
7
8/8/2019 compu archi
9/25
a n o p e n s y s t e m . B y c o n t r a s t , t r a d i t i o n a l t e m p o r a l l o g i c s y n t h e s i s m e t h o d s E C 8 2 , M W 8 4 ] r e q u i r e
a s p e c i c a t i o n o f t h e e n t i r e s y s t e m . T h u s t h e i r r e s u l t s h a v e t o b e r e c o m p u t e d w h e n e v e r t h e s y s t e m
i s m o d i e d . T h e d e t a i l s o f t h e s y n t h e s i s p r o c e d u r e a r e o m i t t e d h e r e f o r b r e v i t y , b u t c a n b e f o u n d
i n A S R S 9 2 ] .
A
D
i s a t u p l e h s
0
; S ; ; i , w h e r e S i s a s e t o f s t a t e s , s
0
i s t h e d i s t i n g u i s h e d i n i t i a l s t a t e ,
i s t h e a l p h a b e t , a n d S S i s t h e t r a n s i t i o n r e l a t i o n . W e u s e t
i
t o i n d i c a t e t h e s p e c i c
t e r m i n a t i o n e v e n t o f t a s k i , a n d " t o d e n o t e a n y e v e n t w h i c h c a n e i t h e r b e a s i g n i c a n t e v e n t
( p r e v i o u s l y n o t a t e d w i t h e ) o r a t e r m i n a t i o n e v e n t . T h e e l e m e n t s o f a r e n o t a t e d a s ,
0
, e t c .
c a n b e o f f o r m a ( a c c e p t ) o r r ( r e j e c t ) , a n d c a n b e i n t e r l e a v e d o r s e q u e n c e d a s d e s c r i b e d b e l o w .
a ( "
1
; ; "
m
) : T h i s i n d i c a t e s t h a t A
D
a c c e p t s t h e e v e n t s "
1
t h r o u g h "
m
. I f t h i s t r a n s i t i o n i s
t a k e n b y A
D
, t h e n e a c h "
i
i s a c c e p t e d a n d , i f "
i
i s a s i g n i c a n t e v e n t , i t i s t h e n f o r w a r d e d t o
t h e e v e n t m o n i t o r f o r e x e c u t i o n .
r ( e
1
; ; e
m
) : T h i s i n d i c a t e s t h a t A
D
r e j e c t s t h e e v e n t s e
1
t h r o u g h e
m
b e c a u s e t h e e x e c u t i o n
o f a n y o f t h e m w o u l d v i o l a t e t h e d e p e n d e n c y D .
1
n
, w h e r e t h e
i
2 : T h i s i n d i c a t e s t h e i n t e r l e a v i n g o f t h e a c c e p t o p e r a t i o n s
c o r r e s p o n d i n g t o
1
t h r o u g h
n
1
; . . . ;
n
, w h e r e t h e
i
2 : T h i s i n d i c a t e s t h e a c c e p t o p e r a t i o n s o f
i
o c c u r b e f o r e t h e
a c c e p t o p e r a t i o n s o f
i + 1
( f o r 1 i ( n ? 1 ) ) .
E x a m p l e D e p e n d e n c y A u t o m a t a
W e r e p r e s e n t A
D
a s a l a b e l e d g r a p h , w h o s e n o d e s a r e s t a t e s , a n d w h o s e e d g e s a r e t r a n s i t i o n s . E a c h
e d g e i s l a b e l e d w i t h a n e l e m e n t o f . d e n o t e s t h e a c t i o n s , s u c h a s a c c e p t o r r e j e c t , t h a t a r e
t a k e n b y t h e s c h e d u l e r w h e n t h a t t r a n s i t i o n i s e x e c u t e d .
I n F i g u r e s 4 a n d 5 b e l o w , w e g i v e e x a m p l e d e p e n d e n c y a u t o m a t a f o r t h e d e p e n d e n c i e s
e
1
< e
2
, a n d e
1
! e
2
, r e s p e c t i v e l y . T h e s y m b o l i n d i c a t e s c h o i c e : a n e d g e l a b e l e d
0
m a y b e
f o l l o w e d i f t h e s c h e d u l e r p e r m i t s e i t h e r o r
0
O p e r a t i o n o f a n A u t o m a t o n
T h e f o l l o w i n g o b s e r v a t i o n s a r e m a d e w i t h r e s p e c t t o h o w a d e p e n d e n c y a u t o m a t o n e n f o r c e s a
d e p e n d e n c y . A t
i
i n d i c a t e s t h e t e r m i n a t i o n o r t i m i n g o u t o f a t a s k . A d e p e n d e n c y a u t o m a t o n
c a n n o t r e j e c t a t
i
e v e n t , s i n c e i t c a n n o t u n i l a t e r a l l y p r e v e n t s u c h a n e v e n t . H o w e v e r , a n a u t o m a t o n
m a y d e l a y a t e r m i n a t i o n e v e n t u n t i l a n a p p r o p r i a t e t i m e . T h e i m p o r t a n c e o f t
i
e v e n t s i s t h a t t h e i r
s u b m i s s i o n t e l l s t h e a u t o m a t o n t h a t e v e n t s t h a t m a y h a v e b e e n s u b m i t t e d b y t h e g i v e n t a s k w i l l
8
8/8/2019 compu archi
10/25
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
Hj
J
J
J
J
J
J
J
J
P
P
P
P
P
P
P
P
P
P
P
P
P
P
P
Pq
)
?
?
?
?
?
?
a ( e
2
) a ( t
1
)
a ( e
1
) a ( t
1
)
a ( e
2
) a ( t
2
)
a ( e
1
)
a ( t
2
) r ( e
2
)
a ( t
1
)
a ( e
2
) a ( t
2
)
F i g u r e 4 : D e p e n d e n c y A u t o m a t o n f o r o r d e r d e p e n d e n c y e
1
< e
2
a s s u m i n g r e j e c t a b l e ( e
2
)
m
mmm
m
H
H
H
H
H
H
H
H
H
H
H
H
H
H
Hj
/
P
P
P
P
P
P
P
P
P
P
P
P
P
P
P
Pq
@
@
@
@
@
@R
)
a ( t
2
)
a ( e
2
) a ( t
2
)
a ( t
1
) r ( e
1
)
a ( e
1
) a ( e
2
)
r ( e
1
) a ( t
1
)
a ( e
1
) a ( t
1
)
a ( e
2
)
F i g u r e 5 : D e p e n d e n c y A u t o m a t o n f o r e x i s t e n c e d e p e n d e n c y e
1
! e
2
a s s u m i n g r e j e c t a b l e ( e
1
)
9
8/8/2019 compu archi
11/25
d e n i t e l y n o t b e s u b m i t t e d . T h i s c a n s i g n i c a n t l y a e c t t h e a u t o m a t o n ' s b e h a v i o r . K n o w l e d g e
t h a t t h e g i v e n t a s k h a s t e r m i n a t e d m a y a l l o w t h e s c h e d u l e r t o a c c e p t f o r e x e c u t i o n a p r e v i o u s l y
d e l a y e d e v e n t e
j
, a s t h e k n o w l e d g e t h a t e
i
w i l l n e v e r o c c u r m a y e n a b l e t h e s c h e d u l e r t o i n f e r t h a t
t h e e x e c u t i o n o f e
j
n o w w i l l n o t v i o l a t e c e r t a i n d e p e n d e n c i e s . T h i s h a p p e n s , f o r e x a m p l e , i f a
d e p e n d e n c y e
i
< e
j
i s t o b e e n f o r c e d a n d e
j
h a s b e e n s u b m i t t e d , b u t i s b e i n g d e l a y e d . I n s u c h a
c a s e , t h e a r r i v a l o f t
i
e n s u r e s t h a t t h e d e p e n d e n c y e
i
< e
j
c a n n o t b e v i o l a t e d ; c o n s e q u e n t l y , e
j
c a n
b e s c h e d u l e d ( u n l e s s d o i n g s o w o u l d v i o l a t e s o m e o t h e r d e p e n d e n c i e s ) . T h e o r d e r i n g o f t h e r e j e c t
o p e r a t i o n s i s n o t c o n s t r a i n e d , s i n c e t h e y d o n o t c o n t r i b u t e t o t h e n a l g l o b a l c o m p u t a t i o n .
W e a s s u m e f o r s i m p l i c i t y t h a t e a c h t a s k c a n h a v e a t m o s t o n e e v e n t i n a g i v e n d e p e n d e n c y ,
i . e . , o n l y i n t e r t a s k d e p e n d e n c i e s a r e e x p l i c i t l y c o n s i d e r e d . T h u s t h e i n p u t a l p h a b e t f o r A
D
, w h e r e
D i s o f t h e f o r m D ( e
1
; ; e
n
) , i s f e
1
; ; e
n
; t
1
; ; t
n
g . T h a t i s , t h e s i z e o f t h e i n p u t a l p h a b e t f o r
A
D
i s 2 n
A
D
o p e r a t e s a s f o l l o w s . A t a n y t i m e , i t i s i n s o m e s t a t e , s a y , s . I n i t i a l l y , s = s
0
. E v e n t s
a r r i v e s e q u e n t i a l l y . L e t " b e t h e c u r r e n t e v e n t . I f s h a s a n o u t g o i n g e d g e l a b e l e d a ( " ) a n d i n c i d e n t
o n s t a t e s
0
, t h e n t h e g i v e n t r a n s i t i o n i s e n a b l e d . T h i s m e a n s t h a t , a s f a r a s i t s l o c a l s t a t e i s
c o n c e r n e d , A
D
c a n c h a n g e i t s s t a t e t o s
0
. H o w e v e r , A
D
c a n n o t a c t u a l l y m a k e t h e t r a n s i t i o n u n l e s s
t h e s c h e d u l e r p e r m i t s i t ( s e e S e c t i o n 5 ) .
I f t h e s c h e d u l e r p e r m i t s a c e r t a i n t r a n s i t i o n , t h e n t h e a u t o m a t o n c a n e x e c u t e i t , t h e r e b y
c h a n g i n g i t s l o c a l s t a t e t o k e e p i n s y n c h r o n i z a t i o n w i t h r e s p e c t t o t h e e v e n t s e x e c u t e d s o f a r . T h e
b e h a v i o r o f t h e s c h e d u l e r i s s u c h t h a t i t a c c e p t s a n e v e n t o n l y i f i t c a n n d a n e v e n t o r d e r i n g t h a t
i s c o n s i s t e n t w i t h a l l o f t h e d e p e n d e n c y a u t o m a t a t h a t c o n t a i n t h a t e v e n t i n t h e i r i n p u t a l p h a b e t .
S o i f i t a c c e p t s a n e v e n t , a l l t h e r e l e v a n t a u t o m a t a m u s t b e i n a g r e e m e n t . T h e r e f o r e , e a c h o f t h e m
m u s t e x e c u t e t h e g i v e n a c c e p t i n g t r a n s i t i o n . T h i s e n s u r e s t h a t a c c e p t a n c e o f t h e e v e n t d o e s n o t
v i o l a t e a n y o f t h e d e p e n d e n c i e s i n w h i c h t h e e v e n t i s m e n t i o n e d . S i m i l a r l y , t h e s c h e d u l e r c a n r e j e c t
a n e v e n t o n l y i f a l l o f t h e r e l e v a n t a u t o m a t a r e j e c t i t , i . e . , o n l y i f i t c a n n d a n e v e n t o r d e r i n g t h a t
i s c o n s i s t e n t w i t h a l l o f t h e r e l e v a n t d e p e n d e n c y a u t o m a t a e x e c u t i n g a r e j e c t i n g t r a n s i t i o n f o r t h e
e v e n t . T h e s a m e r e a s o n i n g a s f o r a c c e p t i n g a n e v e n t a p p l i e s h e r e , s i n c e t h e r e j e c t i o n o f a n e v e n t
c a n a l s o c a u s e t h e v i o l a t i o n o f a d e p e n d e n c y i n w h i c h t h e e v e n t i s m e n t i o n e d . S e c t i o n 5 d i s c u s s e s
t h e o p e r a t i o n o f t h e s c h e d u l e r i n d e t a i l .
D e a l i n g w i t h F a i l u r e s u s i n g T i m e o u t s
W e h a v e s o f a r i n t e r p r e t e d t h e t
i
e v e n t s t o i n d i c a t e t h e t e r m i n a t i o n o f t a s k i . O r d i n a r i l y , t a s k s
t e r m i n a t e b y c o m m i t t i n g o r a b o r t i n g . H o w e v e r , s y s t e m p r o b l e m s , s u c h a s d i s k c r a s h e s a n d c o m m u -
n i c a t i o n f a i l u r e s , m a y c a u s e i n d e n i t e w a i t s . F o r e x a m p l e , t h e a u t o m a t o n s h o w n i n F i g u r e 4 d e l a y s
a c c e p t i n g e
2
u n t i l t
1
o r e
1
i s s u b m i t t e d . T h i s i s t o e n s u r e t h a t i f b o t h e
1
a n d e
2
a r e s u b m i t t e d ,
t h e n e
1
e x e c u t e s b e f o r e e
2
. T h u s t h i s a u t o m a t o n c o u l d p o s s i b l y h a n g f o r e v e r .
O n e p o l i c y i s t o h a v e t h e a u t o m a t o n a c c e p t e
2
w h e n e
2
a r r i v e s a n d r e j e c t e
1
i f e
1
a r r i v e s
1 0
8/8/2019 compu archi
12/25
8/8/2019 compu archi
13/25
'
&
$
%
'
&
$
%
6
J
J
J
J
J
J
J
-
-
J
J
J
J
J
J
J
J
-
D e l a y e d E v e n t s
E v e n t
P e n d i n g
S e t
A u t o m a t a
D e p e n d e n c y
R e p l i e s Q u e r i e s
S c h e d u l e r
E v e n t s
R e j e c t e d
S u b m i t t e d
i n d i c a t e s a p r o c e s s
i n d i c a t e s a d a t a s t r u c t u r e
E v e n t s
E x e c u t i o n o f
D e l a y e d E v e n t s
R e - a t t e m p t e d
A c c e p t e d E v e n t s i n p a r t i a l o r d e r
E x e c u t e
D i s p a t c h e r T a s k s
F i g u r e 6 : T h e E x e c u t i o n M o d e l
i . e . , a c o r r e s p o n d i n g s e t o f p a t h s . A p a t h s e t c o n s i s t s o f o n e p a t h f r o m e a c h r e l e v a n t d e p e n d e n c y
a u t o m a t o n . T h e d e s i r e d p a t h s e t m u s t
1 . a c c e p t " ,
2 . b e g i n i n t h e c u r r e n t g l o b a l s t a t e o f t h e s c h e d u l e r ,
3 . b e o r d e r - c o n s i s t e n t ,
4 . b e a - c l o s e d a n d r - c l o s e d , a n d
5 . b e e x e c u t a b l e .
O r d e r - c o n s i s t e n c y m e a n s t h a t d i e r e n t p a t h s i n t h e s e t m u s t a g r e e o n t h e o r d e r o f e x e c u t i o n o f
e a c h p a i r o f e v e n t s . T h e r e q u i r e m e n t s o f a - c l o s u r e a n d r - c l o s u r e m e a n t h a t f o r a n y e v e n t t h a t i s
a c c e p t e d o r r e j e c t e d , p a t h s f r o m e a c h a u t o m a t o n r e f e r r i n g t o t h a t e v e n t m u s t b e i n c l u d e d a n d m u s t
a g r e e o n w h e t h e r t o a c c e p t o r r e j e c t i t . E x e c u t a b l e m e a n s t h a t a l l r e j e c t e d e v e n t s m u s t h a v e b e e n
s u b m i t t e d a n d a l l a c c e p t e d e v e n t s m u s t h a v e b e e n s u b m i t t e d o r b e f o r c i b l e . A p a t h s e t t h a t m e e t s
c r i t e r i a 2 { 5 i s c a l l e d v i a b l e
F o l l o w i n g a f e w t e c h n i c a l d e n i t i o n s , w e d i s c u s s f u r t h e r u s e o f p a t h s e t s a n d a n a l g o r i t h m t o
d e t e r m i n e t h e m .
D e n i t i o n 1 ( G l o b a l S t a t e ) .
A g l o b a l s t a t e s i s a t u p l e h s
D
1
; ; s
D
; ; s
D
n
i w h e r e s
D
i s t h e l o c a l s t a t e o f A
D
, a n d D
1
; D
n
a r e a l l t h e d e p e n d e n c i e s i n t h e s y s t e m .
1 2
8/8/2019 compu archi
14/25
T h e g l o b a l s t a t e i s s i m p l y t h e a g g r e g a t i o n o f t h e l o c a l s t a t e s o f e v e r y i n d i v i d u a l d e p e n d e n c y a u -
t o m a t o n .
D e n i t i o n 2 ( P a t h ) .
A p a t h i n A
D
,
D
, i s a s e q u e n c e s
1
1
s
2
2
s
j
j
s
j + 1
s u c h t h a t ( 8 j 1 : ( s
j
;
j
; s
j + 1
) 2
D
)
w h e r e
D
i s t h e t r a n s i t i o n r e l a t i o n o f A
D
A g l o b a l c o m p u t a t i o n i s a s e q u e n c e o f e v e n t s a s e x e c u t e d b y t h e e v e n t d i s p a t c h e r . R e c a l l t h a t
A
D
i s m e a n t t o e n c o d e a l l t h e c o m p u t a t i o n s t h a t s a t i s f y d e p e n d e n c y D . T h u s , e a c h p a t h o f A
D
r e p r e s e n t s c o m p u t a t i o n s t h a t s a t i s f y D . F u r t h e r m o r e , A
D
i s m a x i m a l i n t h e s e n s e t h a t e v e r y
p o s s i b l e c o m p u t a t i o n w h o s e p r e x e s s a t i s f y D i s r e p r e s e n t e d b y s o m e p a t h i n A
D
. B y d e n i t i o n , a
g l o b a l c o m p u t a t i o n m u s t c o n s i s t s o l e l y o f e v e n t s a c c e p t e d b y t h e s c h e d u l e r . O u r s c h e d u l e r h a s t h e
p r o p e r t y t h a t , f o r e a c h d e p e n d e n c y D , t h e p r o j e c t i o n o f a n y g l o b a l c o m p u t a t i o n o n t o t h e e v e n t s i n
D i s r e p r e s e n t e d b y a p a t h i n A
D
. T h i s m e a n s t h a t o u r s c h e d u l e r e n f o r c e s e a c h d e p e n d e n c y .
D e n i t i o n 3 ( P a t h s e t ) .
A p a t h s e t i s a s e t , , o f p a t h s s u c h t h a t :
1 . E a c h e l e m e n t o f i s a p a t h i n s o m e A
D
2 . E a c h A
D
c o n t r i b u t e s a t m o s t o n e p a t h t o
A s w e m e n t i o n e d i n s e c t i o n 5 . 1 , w h e n a n e v e n t " i s s u b m i t t e d t o t h e s c h e d u l e r , t h e s c h e d u l e r
a t t e m p t s t o e x e c u t e " b y n d i n g a v i a b l e p a t h s e t t h a t a c c e p t s " . I f s u c h a p a t h s e t i s f o u n d , t h e n a l l
e v e n t s t h a t a r e a c c e p t e d b y t h e p a t h s e t a r e e x e c u t e d i n a n o r d e r t h a t i s c o n s i s t e n t w i t h t h a t i m p o s e d
b y t h e p a t h s e t . T h i s r e s u l t s i n t h e g l o b a l s t a t e o f t h e s c h e d u l e r b e i n g u p d a t e d a p p r o p r i a t e l y . I f
s u c h a p a t h s e t i s n o t f o u n d , t h e n e v e n t " i s p l a c e d i n t h e p e n d i n g s e t . A n o t h e r a t t e m p t a t n d i n g
a s u i t a b l e p a t h s e t i s m a d e w h e n o t h e r e v e n t s t h a t h a v e a n i m p a c t o n t h e a c c e p t a b i l i t y o f " h a v e
b e e n s u b m i t t e d . E v e n t " r e m a i n s i n t h e p e n d i n g s e t u n t i l e i t h e r a v i a b l e p a t h s e t e x e c u t e d t h a t
a c c e p t s o r r e j e c t s i t . I n t h e l a t t e r c a s e , " i s r e j e c t e d f o r e x e c u t i o n b y t h e s c h e d u l e r a n d t h e t a s k
t h a t i s s u e d " i s i n f o r m e d o f t h i s d e c i s i o n .
5 . 3 T h e P a t h s e t S e a r c h A l g o r i t h m
I n F i g u r e 7 , w e p r e s e n t a ( r e c u r s i v e ) p r o c e d u r e s e a r c h t h a t s e a r c h e s f o r v i a b l e p a t h s e t s . T h e
p r o c e d u r e i s i n i t i a l l y c a l l e d a s s e a r c h ( ; ) . T h e e v e n t t o b e e x e c u t e d , " , a n d o t h e r n e c e s s a r y d a t a
s t r u c t u r e s a r e a s s u m e d t o b e g l o b a l s f o r s i m p l i c i t y ( t h e y a r e p a s s e d a s p a r a m e t e r s i n t h e a c t u a l
i m p l e m e n t a t i o n ) . T h e s e a r c h p r o c e d u r e a t t e m p t s t o c o n s t r u c t a v i a b l e p a t h s e t b y s e l e c t i n g p a t h s
f r o m e a c h r e l e v a n t a u t o m a t o n t h a t a r e o r d e r - c o n s i s t e n t w i t h a n d a r e e x e c u t a b l e . I f t h e s e p a t h s
c o n t a i n a ( " ) o r r ( " ) e v e n t s t h a t o c c u r i n a u t o m a t a o u t s i d e t h e s e t o f a u t o m a t a b e i n g c o n s i d e r e d ,
t h o s e a u t o m a t a a r e c o n s i d e r e d t o e n s u r e a - c l o s u r e a n d r - c l o s u r e o f t h e e v e n t u a l s o l u t i o n .
1 3
8/8/2019 compu archi
15/25
s e a r c h ( )
i f r - c l o s e d ( ) a n d a - c l o s e d ( ) t h e n
r e t u r n ( ) ;
e l s e f
F i n d a n a u t o m a t o n A t h a t i s n e e d e d t o c l o s e o ;
c
: = g e t c a n d i d a t e p a t h s ( A , ) ;
f o r e a c h 2
t
: = s e a r c h ( f g ) ;
i f
t
6= ; t h e n / *
t
i s v i a b l e ; e n d a l l r e c u r s i v e c a l l s * /
r e t u r n (
t
) ;
e n d f o r
/ * a l l p a t h s i n
c
f a i l e d , s o r e t u r n ; * /
r e t u r n ( ; ) ;
g
F i g u r e 7 : P a t h s e t S e a r c h A l g o r i t h m
1 4
8/8/2019 compu archi
16/25
T h e f u n c t i o n g e t c a n d i d a t e p a t h s ( A , ) r e t u r n s a s e t o f e x e c u t a b l e p a t h s f r o m a u t o m a -
t o n A t h a t a r e o r d e r - c o n s i s t e n t w i t h a l l p a t h s i n . S o m e o f t h e r e t u r n e d p a t h s m a y b e e x t e n s i o n s o f
p a t h s a l r e a d y i n . W e n o w e s t a b l i s h s o m e c o r r e c t n e s s p r o p e r t i e s o f t h e p a t h s e t s e a r c h a l g o r i t h m .
M o s t p r o o f s a r e n o t i n c l u d e d h e r e f o r b r e v i t y , b u t a p p e a r i n A S R S 9 2 ] .
L e m m a 1 F o r a n y e v e n t , " , a n d g l o b a l s t a t e s , i f s e a r c h ( ; ) t e r m i n a t e s w i t h 6= ; , t h e n i s
v i a b l e ( w . r . t . g l o b a l s t a t e s ) a n d a c c e p t s "
P r o o f s k e t c h .
W e s h o w t h a t e a c h o f t h e c l a u s e s o f t h e d e n i t i o n o f v i a b l e ( p a g e 1 2 ) i s s a t i s e d . B y c o n s t r u c t i o n
o f t h e s c h e d u l e r , t h e s e a r c h f o r a p a t h s e t b e g i n s i n t h e c u r r e n t g l o b a l s t a t e . N e w p a t h s t h a t a r e
a d d e d t o t h e c a n d i d a t e p a t h s e t (
c
) a r e e x e c u t a b l e a n d o r d e r - c o n s i s t e n t w i t h , b y d e n i t i o n o f
t h e g e t c a n d i d a t e p a t h s f u n c t i o n . S e a r c h o n l y t e r m i n a t e s w h e n e i t h e r i s e m p t y o r i s a - c l o s e d
a n d r - c l o s e d
L e m m a 2 s e a r c h ( ; ) a l w a y s t e r m i n a t e s .
P r o o f s k e t c h .
T h e e s s e n t i a l i d e a i s t h a t b e c a u s e t h e n u m b e r o f a u t o m a t a i s n i t e a n d e a c h a u t o m a t o n h a s n i t e l y
m a n y p a t h s , o n l y n i t e l y m a n y c a n d i d a t e p a t h s e t s n e e d t o b e c o n s i d e r e d . T h u s t h e a l g o r i t h m
t e r m i n a t e s .
5 . 4 T h e S c h e d u l e r
T h e s c h e d u l e r i s a n o n t e r m i n a t i n g l o o p , w h i c h o n e a c h i t e r a t i o n a t t e m p t s t o e x e c u t e a n e v e n t " t h a t
h a s j u s t b e e n s u b m i t t e d o r i s i n t h e p e n d i n g s e t ( F i g u r e 6 ) . I t d o e s t h i s b y i n v o k i n g s e a r c h ( ; )
I f t h i s i n v o c a t i o n r e t u r n s a n o n e m p t y , t h e n i s i m m e d i a t e l y e x e c u t e d . O t h e r w i s e , " i s p l a c e d i n
t h e p e n d i n g s e t . i s e x e c u t e d b y ( a ) a c c e p t i n g t h e e v e n t s t h a t a c c e p t s i n a p a r t i a l o r d e r t h a t
i s c o n s i s t e n t w i t h a n d ( b ) r e j e c t i n g a l l e v e n t s r e j e c t e d b y .
D e n i t i o n 4 ( P a t h P r o j e c t i o n ) .
T h e p r o j e c t i o n " D o f g l o b a l c o m p u t a t i o n o n t o a d e p e n d e n c y a u t o m a t o n D i s t h e p a t h o b t a i n e d
f r o m b y r e m o v i n g a l l t r a n s i t i o n s " s u c h t h a t " 62
D
L e m m a 3 L e t b e a g l o b a l c o m p u t a t i o n g e n e r a t e d b y t h e s c h e d u l e r . T h e n , f o r e v e r y d e p e n d e n c y
D , " D i s a p a t h i n A
D
1 5
8/8/2019 compu archi
17/25
P r o o f s k e t c h . B y c o n s t r u c t i o n o f t h e s c h e d u l e r .
N o t e t h a t t h e p a t h s i n
c
r e t u r n e d b y g e t c a n d i d a t e p a t h s a r e e x a m i n e d i n a r b i t r a r y o r d e r .
O p t i m a l i t y o f t h e c o n s t r u c t e d p a t h s e t c o u l d b e i m p r o v e d i f t h e p a t h s i n
c
w e r e e x a m i n e d a c c o r d i n g
t o s o m e a p p r o p r i a t e c r i t e r i o n , s u c h a s m i n i m a l l e n g t h o r m a x i m a l a c c e p t a n c e o r m i n i m a l r e j e c t i o n .
W e a r e c u r r e n t l y e x p e r i m e n t i n g w i t h s u c h c r i t e r i a .
5 . 5 E x a m p l e o f S c h e d u l e r O p e r a t i o n
W e n o w g i v e a n e x a m p l e o f h o w r e l a x e d t r a n s a c t i o n s e x p r e s s e d w i t h
8/8/2019 compu archi
18/25
6 E x e c u t i n g M u l t i d a t a b a s e T r a n s a c t i o n s
W e n o w d i s c u s s t h r e e i s s u e s i n e x e c u t i n g m u l t i d a t a b a s e t r a n s a c t i o n s : c o n c u r r e n c y c o n t r o l , s a f e t y ,
a n d r e c o v e r a b i l i t y .
6 . 1 C o n c u r r e n c y C o n t r o l
O u r s c h e d u l e r i s a p a r t o f a m u l t i d a t a b a s e e n v i r o n m e n t i n w h i c h l o c a l d a t a b a s e s y s t e m s ( L D B S )
c o o p e r a t e i n t h e e x e c u t i o n o f g l o b a l t r a n s a c t i o n s . E a c h L D B S w i l l , i n g e n e r a l , c o n t a i n a c o n c u r r e n c y
c o n t r o l m o d u l e , w h i c h e n f o r c e s l o c a l c o n c u r r e n c y c o n t r o l ( t y p i c a l l y e n s u r i n g l o c a l s e r i a l i z a b i l i t y ) .
W e m a y a s s u m e t h a t a t a s k e x e c u t i n g a t e a c h o f t h e l o c a l s y s t e m s h a s s e r i a l i z a t i o n e v e n t t h a t
d e t e r m i n e s i t s p o s i t i o n i n t h e l o c a l s e r i a l i z a t i o n o r d e r . F o r e x a m p l e , i t t h e l o c a l s y s t e m u s e s t w o -
p h a s e l o c k i n g ( 2 P L ) , t h e s e r i a l i z a t i o n o r d e r o f a l o c a l t r a n s a c t i o n i s d e t e r m i n e d b y i t s l o c k p o i n t {
t h e p o i n t w h e n t h e l a s t l o c k o f t h e t r a n s a c t i o n i s g r a n t e d .
A p r o b l e m a r i s e s i f l o c a l c o n c u r r e n c y c o n t r o l m o d u l e s i m p o s e a n i n c o n s i s t e n t o r d e r i n g o n s e -
r i a l i z a t i o n e v e n t s o f t a s k s b e l o n g i n g t o a g i v e n m u l t i d a t a b a s e a p p l i c a t i o n . W e r e s o l v e t h i s p r o b l e m
b y t r a n s f e r r i n g t h e r e s p o n s i b i l i t y f o r g l o b a l c o n c u r r e n c y c o n t r o l t o t h e s c h e d u l e r . T h i s i s a c h i e v e d
b y r e s t a t i n g t h e c o n c u r r e n c y c o n t r o l o b l i g a t i o n s a s a s e t o f d e p e n d e n c i e s , w h i c h a r e t h e n e n f o r c e d
i n t h e s a m e w a y a s a n y o t h e r d e p e n d e n c y . T h e m a i n d i e r e n c e i s t h a t , u n l i k e o t h e r s c h e d u l i n g d e -
p e n d e n c i e s , t h e c o n c u r r e n c y c o n t r o l d e p e n d e n c i e s b e t w e e n a p p l i c a t i o n s a r i s e a t t h e r u n t i m e , w h e n
a s e r i a l i z a t i o n p r e c e d e n c e b e t w e e n t h e t a s k s b e l o n g i n g t o t h e s e a p p l i c a t i o n s h a s b e e n e s t a b l i s h e d a t
a n y s i t e . H o w e v e r , o n c e t h e s e d e p e n d e n c i e s a r e d e t e c t e d , t h e y c a n b e e n f o r c e d i n t h e s a m e w a y a s
t h e o t h e r d e p e n d e n c i e s d e s c r i b e d e a r l i e r . T h u s w e h a v e a u n i f o r m m e c h a n i s m f o r b o t h d e p e n d e n c y
e n f o r c e m e n t a n d c o n c u r r e n c y c o n t r o l .
T h e m a i n d i c u l t y i n t h i s a p p r o a c h i s t h a t t h e s e r i a l i z a t i o n e v e n t s a r e n e i t h e r r e p o r t e d
b y t h e l o c a l c o n c u r r e n c y c o n t r o l l e r s , n o r c a n t h e y b e d e d u c e d f r o m t h e t e m p o r a l o r d e r o f o t h e r
s i g n i c a n t e v e n t s c o n t r o l l e d b y t h e g l o b a l s c h e d u l e r ( s t a r t , c o m m i t , t e r m i n a t e ) . I t i s p o s s i b l e f o r
a l o c a l c o n c u r r e n c y c o n t r o l l e r t o c o m p l e t e l y e x e c u t e t a s k T
i
b e f o r e t a s k T
j
h a s e v e n b e g u n , y e t
s e r i a l i z e t h e m i n s u c h a w a y t h a t t h a t T
j
p r e c e d e s T
i
. T h i s p r o b l e m c a n b e o v e r c o m e b y u s i n g
t h e i d e a o f t i c k e t s i n t r o d u c e d i n G R S 9 1 ] . A s i n G R S 9 1 ] , w e m a y a d d a t i c k e t r e a d a n d t i c k e t
w r i t e o p e r a t i o n t o e a c h t a s k o f a g l o b a l a p p l i c a t i o n . T h e s e t i c k e t r e a d / w r i t e o p e r a t i o n s c a n b e
r e g a r d e d a s s i g n i c a n t e v e n t s , a n d s o t h e i r e x e c u t i o n c a n b e c o n t r o l l e d b y d e c l a r i n g d e p e n d e n c i e s
t h a t r e f e r t o t h e m . T h u s t h e r e q u i r e d c o n c u r r e n c y c o n t r o l i s t h e n o b t a i n e d s i m p l y b y d e c l a r i n g a n
a p p r o p r i a t e s e t o f t i c k e t a c c e s s d e p e n d e n c i e s .
1 7
8/8/2019 compu archi
19/25
6 . 2 F l e x i b l e T r a n s a c t i o n S a f e t y
A e x i b l e t r a n s a c t i o n E L L R 9 0 ] i s d e n e d a s a s e t o f s u b t r a n s a c t i o n s a n d t h e i r s c h e d u l i n g p r e c o n -
d i t i o n s a l o n g w i t h a s e t o f c o n d i t i o n s o v e r t h e i r n a l s t a t e s E L L R 9 0 ] . T h e s e c o n d i t i o n s s p e c i f y t h e
a c c e p t a b l e t e r m i n a t i o n s t a t e s o f t h e e x i b l e t r a n s a c t i o n ; i t c o m p l e t e s s u c c e s s f u l l y i i t t e r m i n a t e s
i n s u c h a s t a t e .
C o n s i d e r t h e f o l l o w i n g e x a m p l e , a d a p t e d f r o m J N R S 9 1 ] . W e h a v e a t r a v e l a g e n t e x i b l e
t r a n s a c t i o n , c o n s i s t i n g o f r e s e r v e - i g h t ( F ) a n d r e s e r v e - c a r ( C ) s u b t r a n s a c t i o n s . I f w e f a i l t o
s e c u r e a c a r r e s e r v a t i o n , w e w i s h t o c a n c e l t h e p l a n e r e s e r v a t i o n . T h i s c a n c e l l a t i o n i s a c h i e v e d
b y a s u b t r a n s a c t i o n F
?
, w h i c h i s a c o m p e n s a t i n g t r a n s a c t i o n f o r F . T h u s t h e s e t o f a c c e p t a b l e
t e r m i n a t i o n s t a t e s f o r t h e o v e r a l l t r a n s a c t i o n i s g i v e n i n T a b l e 3 , w h e r e i n , c m , a n d a b i n d i c a t e
t h a t t h e s u b t r a n s a c t i o n i s i n i t s i n i t i a l s t a t e , i s c o m m i t t e d , a n d i s a b o r t e d , r e s p e c t i v e l y . T h e s e t
o f a c c e p t a b l e s t a t e s i s a c o n s t r a i n t o n t h e e x e c u t i o n o f a e x i b l e t r a n s a c t i o n . T h i s c o n s t r a i n t c a n
a l s o b e e x p r e s s e d a s t h e s e t o f d e p e n d e n c i e s g i v e n i n T a b l e 3 .
F F
?
C
c m i n c m
a b i n i n
a b i n a b
c m c m a b
i n i n i n
c m c m i n
a b
C
< c m
F
( a b
C
c m
F
) ! c m
F
c m
C
! c m
F
T a b l e 3 : A c c e p t a b l e S t a t e s o f a F l e x i b l e T r a n s a c t i o n
6 . 3 R e c o v e r a b i l i t y
W e w i l l n o t d e a l e x t e n s i v e l y w i t h t h e i s s u e o f r e c o v e r y f r o m f a i l u r e i n t h i s p a p e r . S u c e i t t o s a y
t h a t t h e f o l l o w i n g d a t a m u s t b e c h e c k p o i n t e d i n o r d e r t o e n a b l e r e c o v e r y o f t h e s c h e d u l e r f r o m a
f a i l u r e :
1 . T h e c u r r e n t s t a t e o f e v e r y d e p e n d e n c y a u t o m a t o n .
2 . A n y ( p a r t i a l l y e x e c u t e d ) p a t h s e t ( s e e S e c t i o n 5 ) , p l u s t h e c u r r e n t s t a t e a l o n g e v e r y p a t h i n
t h e p a t h s e t .
3 . T h e s e t o f p e n d i n g e v e n t s .
T h e a b o v e d a t a i s s u b j e c t t o c o n c u r r e n t u p d a t e s t h a t m u s t b e e x e c u t e d a t o m i c a l l y w i t h r e s p e c t t o
t h e c h e c k p o i n t i n g m e c h a n i s m . F o r e x a m p l e , w h e n a n e v e n t e i s e x e c u t e d , t h e c u r r e n t s t a t e o f e v e r y
1 8
8/8/2019 compu archi
20/25
d e p e n d e n c y a u t o m a t o n A
D
w h e r e " o c c u r s i n D m u s t b e u p d a t e d . W e d o n o t w i s h a c h e c k p o i n t t o
r e e c t o n l y s o m e o f t h e s e u p d a t e s . I t s h o u l d e i t h e r r e e c t n o n e o f t h e m ( c o r r e s p o n d i n g t o a s t a t e
b e f o r e " i s e x e c u t e d ) , o r r e e c t a l l o f t h e m ( c o r r e s p o n d i n g t o a s t a t e a f t e r " i s e x e c u t e d ) .
I n a d d i t i o n , w e r e q u i r e a p e r s i s t e n t c o m m u n i c a t i o n m e c h a n i s m b e t w e e n t h e s c h e d u l e r a n d t h e
t a s k s . T h i s i s t o p r e v e n t t h e l o s s o f m e s s a g e s s e n t b y t h e t a s k s t o t h e s c h e d u l e r w h i l e t h e s c h e d u l e r
i s d o w n ( i . e . , a f t e r a f a i l u r e a n d b e f o r e r e c o v e r y f r o m t h a t f a i l u r e ) . M a i l b o x e s o r p e r s i s t e n t p i p e s
m a y b e u s e d t o p r o v i d e t h i s f u n c t i o n a l i t y .
7 C o n c l u s i o n s a n d F u t u r e W o r k
W e a d d r e s s e d t h e p r o b l e m o f s p e c i f y i n g a n d e n f o r c i n g i n t e r t a s k d e p e n d e n c i e s . O u r f r a m e w o r k a l -
l o w s d e p e n d e n c i e s t o b e s t a t e d m o d u l a r l y a n d s u c c i n c t l y a s c o n s t r a i n t s a c r o s s t a s k s . I t c a n b e
e x t e n d e d t o a c c o m m o d a t e t h e i s s u e s o f c o n c u r r e n c y c o n t r o l , e x i b l e t r a n s a c t i o n s a f e t y , r e c o v e r a b i l -
i t y , a n d t h e e n f o r c e m e n t o f o t h e r d e p e n d e n c i e s t h a t a r e i n t r o d u c e d d y n a m i c a l l y a t r u n - t i m e .
W e s h o w e d h o w a d e p e n d e n c y c a n b e e x p r e s s e d a s a n a u t o m a t o n t h a t c a p t u r e s a l l t h e
c o m p u t a t i o n s t h a t s a t i s f y t h e d e p e n d e n c y . W e p r e s e n t e d a s c h e d u l i n g a l g o r i t h m t h a t e n f o r c e s
m u l t i p l e d e p e n d e n c i e s a t t h e s a m e t i m e . T h i s a l g o r i t h m u s e s t h e a u t o m a t a c o r r e s p o n d i n g t o e a c h
d e p e n d e n c y . W e s h o w e d t h a t e v e r y g l o b a l c o m p u t a t i o n g e n e r a t e d b y t h e s c h e d u l e r s a t i s e s a l l o f
t h e d e p e n d e n c i e s . W e a l s o s h o w e d h o w r e l a x e d t r a n s a c t i o n m o d e l s s u c h a s t h e S a g a m o d e l c a n
b e c a p t u r e d i n o u r f r a m e w o r k . T h e d e s i d e r a t a f o r a t a s k s c h e d u l e r f o r m u l t i d a t a b a s e t r a n s a c t i o n
p r o c e s s i n g i n c l u d e c o r r e c t n e s s ( n o d e p e n d e n c i e s a r e v i o l a t e d ) , s a f e t y ( t r a n s a c t i o n t e r m i n a t e s o n l y
i n a n a c c e p t a b l e s t a t e ) , r e c o v e r a b i l i t y , a n d o p t i m a l i t y . W e h a v e e s t a b l i s h e d t h e c o r r e c t n e s s , s a f e t y
a n d r e c o v e r a b i l i t y o f t h e s c h e d u l e r , w e a r e c u r r e t l y s t u d y i n g t h e o p t i m a l i t y i s s u e s .
A n i m p l e m e n t a t i o n o f t h i s w o r k h a s b e e n c o m p l e t e d a s p a r t o f t h e d i s t r i b u t i o n s e r v i c e s
o f t h e C a r n o t p r o j e c t C a 9 1 ] a t M C C . O u r i m p l e m e n t a t i o n i s i n t h e c o n c u r r e n t a c t o r l a n g u a g e
R o s e t t e , w h o s e a s y n c h r o n y a n d o t h e r f e a t u r e s m a k e f o r a n a t u r a l r e a l i z a t i o n o f o u r e x e c u t i o n
m o d e l . C a r n o t e n a b l e s t h e d e v e l o p m e n t o f o p e n a p p l i c a t i o n s t h a t u s e i n f o r m a t i o n s t o r e d u n d e r t h e
c o n t r o l o f e x i s t i n g c l o s e d s y s t e m s . T h e s p e c i c a t i o n a n d r u n - t i m e e n f o r c e m e n t o f d a t a d e p e n d e n c i e s
i s a n i m p o r t a n t c o m p o n e n t o f t h i s e o r t .
A c k n o w l e d g e m e n t s W e a r e i n d e b t e d t o G r e g M e r e d i t h a n d C h r i s t i n e T o m l i n s o n f o r n u m e r o u s
d i s c u s s i o n s , a n d t o A l l e n E m e r s o n f o r a d v i c e o n C T L . W e h a v e a l s o b e n e t e d f r o m c o n v e r s a t i o n s
w i t h D a r r e l l W o e l k . S r i d h a r G a n t i p r o v i d e d t h e S a g a s e x a m p l e . P h i l C a n n a t a , t h e C a r n o t p r o j e c t
d i r e c t o r , h a s p r o v i d e d t h e m o r a l s u p p o r t f o r t h i s r e s e a r c h a s w e l l a s t h e e n v i r o n m e n t t o d o i t i n .
1 9
8/8/2019 compu archi
21/25
R e f e r e n c e s
A N R S 9 2 ] M . A n s a r i , L . N e s s , M . R u s i n k i e w i c z , a n d A . S h e t h . U s i n g F l e x i b l e T r a n s a c t i o n s t o
S u p p o r t M u l t i - s y s t e m T e l e c o m m u n i c a t i o n A p p l i c a t i o n s . P r o c e e d i n g s o f t h e 1 8 t h V L D B
C o n f e r e n c e , A u g u s t 1 9 9 2 .
A E 8 9 ] P a u l C . A t t i e a n d E . A l l e n E m e r s o n , S y n t h e s i s o f C o n c u r r e n t S y s t e m s w i t h M a n y S i m i l a r
S e q u e n t i a l P r o c e s s e s , P r o c e e d i n g s o f 1 6 t h A n n u a l A C M S y m p o s i u m o n P r i n c i p l e s o f
P r o g r a m m i n g L a n g u a g e s , p a g e s 1 9 1 { 2 0 1 , 1 9 8 9 .
A S R S 9 2 ] P . A t t i e , M . S i n g h , M . R u s i n k i e w i c z , a n d A . S h e t h . S p e c i f y i n g a n d E n f o r c i n g I n t e r t a s k
D e p e n d e n c i e s . M C C T e c h n i c a l R e p o r t C a r n o t - 2 4 5 - 9 2 , N o v e m b e r 1 9 9 2 .
A S T 9 2 ] P . A t t i e , M . S i n g h , a n d C . T o m l i n s o n . A L a n g u a g e B a s e d o n T e m p o r a l L o g i c f o r S p e c i f y -
i n g I n t e r t a s k D e p e n d e n c i e s . M C C T e c h n i c a l R e p o r t , N u m b e r C a r n o t - 2 4 5 - 9 2 , N o v e m b e r
1 9 9 2 .
B S 8 8 ] Y . B r e i t b a r t a n d A . S i l b e r s c h a t z . M u l t i d a t a b a s e u p d a t e i s s u e s . I n P r o c . o f A C M S I G -
M O D I n t ' l C o n f o n M a n a g e m e n t o f D a t a , J u n e 1 9 8 8 .
C a 9 1 ] P . C a n n a t a . T h e I r r e s i s t i b l e M o v e T o w a r d s I n t e r o p e r a b l e D a t a b a s e S y s t e m s . P r o c e e d i n g s
o f t h e 1 s t I n t e r n a t i o n a l W o r k s h o p o n I n t e r o p e r a b i l i t y i n M u l t i d a t a b a s e S y s t e m s , K y o t o ,
J a p a n , A p r i l 1 9 9 1 .
C G 8 7 ] E . C l a r k e a n d O . G r u m b e r g . A v o i d i n g t h e S t a t e E x p l o s i o n P r o b l e m i n T e m p o r a l L o g i c
M o d e l C h e c k i n g A l g o r i t h m s . C a r n e g i e M e l l o n U n i v e r s i t y , P i t t s b u r g h , 1 9 8 7 .
C R 9 0 ] P . C h r y s a n t h i s a n d K . R a m a m r i t h a m . A C T A : A F r a m e w o r k f o r S p e c i f y i n g a n d R e a s o n -
i n g a b o u t T r a n s a c t i o n S t r u c t u r e a n d B e h a v i o r . P r o c e e d i n g s o f A C M S I G M O D C o n f e r -
e n c e o n M a n a g e m e n t o f D a t a , 1 9 9 0 .
C R 9 2 ] P . C h r y s a n t h i s a n d K . R a m a m r i t h a m . A C T A : T h e S A G A C o n t i n u e s . C h a p t e r 1 0 i n
E l 9 2 ] .
D H L 9 0 ] U . D a y a l , M . H s u , a n d R . L a d i n . O r g a n i z i n g L o n g - R u n n i n g A c t i v i t i e s w i t h T r i g g e r s
a n d T r a n s a c t i o n s . P r o c e e d i n g s o f A C M S I G M O D C o n f e r e n c e o n M a n a g e m e n t o f D a t a ,
1 9 9 0 .
D H L 9 1 ] U . D a y a l , M . H s u , R . L a d i n . A T r a n s a c t i o n a l M o d e l f o r L o n g - r u n n i n g A c t i v i t i e s P r o -
c e e d i n g s o f t h e 1 7 t h V L D B C o n f e r e n c e , S e p t e m b e r 1 9 9 1 .
E l 9 2 ] A h m e d E l m a g a r m i d , e d i t o r , D a t a b a s e T r a n s a c t i o n M o d e l s , M o r g a n K a u f m a n , 1 9 9 2 .
E L L R 9 0 ] A . E l m a g a r m i d , Y . L e u , W . L i t w i n , a n d M . R u s i n k i e w i c z . A M u l t i d a t a b a s e T r a n s a c t i o n
M o d e l f o r I n t e r b a s e . P r o c e e d i n g s o f t h e 1 6 t h V L D B C o n f e r e n c e , A u g u s t 1 9 9 0 .
2 0
8/8/2019 compu archi
22/25
E m 9 0 ] E . A l l e n E m e r s o n . T e m p o r a l a n d M o d a l L o g i c . I n H a n d b o o k o f T h e o r e t i c a l C o m -
p u t e r S c i e n c e , v o l . B , J . V a n L e e u w e n , e d i t o r , 1 9 9 0 .
E C 8 2 ] E . A l l e n E m e r s o n a n d E . C l a r k e . U s i n g B r a n c h i n g T i m e T e m p o r a l L o g i c t o S y n t h e s i z e
S y n c h r o n i z a t i o n S k e l e t o n s . S c i e n c e o f C o m p u t e r P r o g r a m m i n g v o l . 2 , 1 9 8 2 , 2 4 1 { 2 6 6 .
E M S S 9 3 ] E . A l l e n E m e r s o n , A . M o k , A . P r a s a d S i s t l a a n d J . S r i n i v a s a n . Q u a n t i t a t i v e T e m p o r a l
R e a s o n i n g . T o a p p e a r i n R e a l T i m e S y s t e m s J o u r n a l , v o l . 2 , J a n u a r y 1 9 9 3 , 3 3 1 { 3 5 2 .
H R 8 3 ] T . H a e r d e r a n d A . R e u t e r . P r i n c i p l e s o f t r a n s a c t i o n - o r i e n t e d d a t a b a s e r e c o v e r y . A C M
C o m p u t i n g S u r v e y s , 1 5 ( 4 ) , D e c e m b e r 1 9 8 3 .
G S 8 7 ] H . G a r c i a - M o l i n a a n d K . S a l e m . S a g a s . P r o c e e d i n g s o f A C M S I G M O D C o n f e r e n c e o n
M a n a g e m e n t o f D a t a , 1 9 8 7 .
G r a 8 1 ] J . N . G r a y . T h e T r a n s a c t i o n C o n c e p t : V i r t u e s a n d L i m i t a t i o n s . P r o c e e d i n g s o f t h e 7 t h
V L D B , S e p t e m b e r 1 9 8 1 .
G R S 9 1 ] D . G e o r g a k o p o u l o s , M . R u s i n k i e w i c z a n d A . S h e t h . O n S e r i a l i z a b i l i t y o f M u l t i d a t a b a s e
T r a n s a c t i o n s t h r o u g h F o r c e d L o c a l C o n i c t . P r o c e e d i n g s o f t h e 7 t h I n t e r n a t i o n a l C o n -
f e r e n c e o n D a t a E n g i n e e r i n g , A p r i l 1 9 9 1 .
J N R S 9 1 ] W . J i n , L . N e s s , M . R u s i n k i e w i c z a n d A . S h e t h . E x e c u t i n g S e r v i c e P r o v i s i o n i n g A p p l i c a -
t i o n s a s M u l t i d a t a b a s e F l e x i b l e T r a n s a c t i o n s ( d r a f t ) . B e l l c o r e T e c h n i c a l M e m o r a n d u m ,
1 9 9 2 .
K l 9 1 ] J . K l e i n . A d v a n c e d R u l e D r i v e n T r a n s a c t i o n M a n a g e m e n t . P r o c e e d i n g s o f t h e I E E E
C O M P C O N , 1 9 9 1 .
M W 8 4 ] Z . M a n n a , P . W o l p e r . S y n t h e s i s o f C o m m u n i c a t i n g P r o c e s s e s f r o m T e m p o r a l L o g i c
S p e c i c a t i o n s . A C M T O P L A S , v o l . 6 , n o . 1 , J a n u a r y 1 9 8 4 , 6 8 { 9 3 .
R S K 9 1 ] M . R u s i n k i e w i c z , A . S h e t h , a n d G . K a r a b a t i s . S p e c i f y i n g I n t e r d a t a b a s e D e p e n d e n c i e s
i n a M u l t i d a t a b a s e E n v i r o n m e n t . M C C T e c h n i c a l R e p o r t A C T - O O D S - 1 5 3 - 9 1 ( Q ) , M a y
1 9 9 1 . A l s o a p p e a r s i n I E E E C o m p u t e r , D e c e m b e r 1 9 9 1 . ]
A C T L S y n t a x a n d S e m a n t i c s
W e h a v e t h e f o l l o w i n g s y n t a x f o r C T L ( w h e r e p d e n o t e s a n a t o m i c p r o p o s i t i o n , a n d f ; g d e n o t e
( s u b - ) f o r m u l a e ) :
1 . E a c h o f p ; f g a n d : f i s a f o r m u l a ( w h e r e t h e l a t t e r t w o c o n s t r u c t s i n d i c a t e c o n j u n c t i o n
a n d n e g a t i o n , r e s p e c t i v e l y ) .
2 1
8/8/2019 compu archi
23/25
8/8/2019 compu archi
24/25
: A : f U : g , A F f f o r A t r u e U f , E F f f o r E t r u e U f , A G f f o r : E F : f , E G f f o r : A F : f , A f U
w
g ] f o r
: E : g U ( : f ^ : g ) , E f U
w
g ] f o r E f U g _ E G f , A X
i
f f o r : E X
i
: f , E X f f o r E X
1
f _ _ E X
k
f , A X f
f o r A X
1
f ^ ^ A X
k
f . P a r t i c u l a r l y u s e f u l m o d a l i t i e s a r e A F f , w h i c h m e a n s t h a t f o r e v e r y p a t h ,
t h e r e e x i s t s a s t a t e o n t h e p a t h w h e r e f h o l d s , a n d A G f , w h i c h m e a n s t h a t f h o l d s a t e v e r y s t a t e
a l o n g e v e r y p a t h .
A f o r m u l a o f t h e f o r m A f U g o r E f U g ] i s a n e v e n t u a l i t y f o r m u l a . A n e v e n t u a l i t y c o r r e s p o n d s
t o a l i v e n e s s p r o p e r t y i n t h a t i t m a k e s a p r o m i s e t h a t s o m e t h i n g d o e s h a p p e n . T h i s p r o m i s e m u s t b e
f u l l l e d . T h e e v e n t u a l i t y A f U g ( E f U g ] ) i s f u l l l e d f o r s i n M p r o v i d e d t h a t f o r e v e r y ( r e s p e c t i v e l y ,
f o r s o m e ) p a t h s t a r t i n g a t s , t h e r e e x i s t s a n i t e p r e x o f t h e p a t h i n M w h o s e l a s t s t a t e s a t i s e s g
a n d a l l o f w h o s e o t h e r s t a t e s s a t i s f y f . S i n c e A F g a n d E F g a r e s p e c i a l c a s e s o f A f U g ] a n d E f U g ,
r e s p e c t i v e l y , t h e y a r e a l s o e v e n t u a l i t i e s . I n c o n t r a s t , A f W g , E f W g ] ( a n d t h e i r s p e c i a l c a s e s A G g
a n d E G g ) a r e i n v a r i a n c e f o r m u l a e . A n i n v a r i a n c e c o r r e s p o n d s t o a s a f e t y p r o p e r t y s i n c e i t a s s e r t s
t h a t c e r t a i n c o n d i t i o n s w i l l n e c e s s a r i l y b e m e t .
C T L i s a p r o p o s i t i o n a l b r a n c h i n g - t i m e t e m p o r a l l o g i c . T h a t i s , i t i n c l u d e s p r o p o s i t i o n a l
l o g i c a n d t e m p o r a l o p e r a t o r s . A C T L t e m p o r a l o p e r a t o r i s c o m p o s e d o f a p a t h - q u a n t i e r ( e i t h e r
A , m e a n i n g f o r a l l p o s s i b l e c o m p u t a t i o n s , o r E , m e a n i n g f o r s o m e p o s s i b l e c o m p u t a t i o n ) , f o l l o w e d
b y a l i n e a r t e m p o r a l o p e r a t o r ( o n e o f F , G , o r U ) F p m e a n s t h a t p h o l d s a t s o m e p o i n t a l o n g
t h e g i v e n c o m p u t a t i o n ; G p m e a n s t h a t p h o l d s a t a l l p o i n t s a l o n g t h e g i v e n c o m p u t a t i o n ; a n d p U q
m e a n s t h a t q h o l d s a t s o m e p o i n t a l o n g t h e g i v e n c o m p u t a t i o n a n d p h o l d s f r o m t h e c u r r e n t p o i n t
u n t i l t h a t p o i n t .
A . 0 . 1 E x p r e s s i n g D e p e n d e n c i e s i n C T L
A t o m i c p r o p o s i t i o n s n a t u r a l l y m o d e l t h e s t a t e s o f a g i v e n s y s t e m : e a c h p r o p o s i t i o n c o r r e s p o n d s t o
a s i g n i c a n t e v e n t a n d h o l d s i n t h e s t a t e i m m e d i a t e l y f o l l o w i n g t h e o c c u r r e n c e o f t h a t e v e n t .
N o w w e s h o w h o w c e r t a i n d e p e n d e n c i e s t h a t w e r e m o t i v a t e d a n d d e n e d b y o t h e r r e s e a r c h e r s
c a n b e e x p r e s s e d u n i f o r m l y i n C T L .
O r d e r D e p e n d e n c y K l 9 1 ] : I f b o t h e v e n t s e
1
a n d e
2
o c c u r , t h e n e
1
p r e c e d e s e
2
. T h i s w a s
e x p r e s s e d a s e
1
< e
2
i n t h e a b o v e d i s c u s s i o n . I n C T L , i t b e c o m e s :
A G e
2
) A G : e
1
T h a t i s , i f e
2
o c c u r s , t h e n e
1
c a n n o t o c c u r s u b s e q u e n t l y .
E x i s t e n c e D e p e n d e n c y K l 9 1 ] : I f e v e n t e
1
o c c u r s s o m e t i m e s , t h e n e v e n t e
2
a l s o o c c u r s s o m e -
t i m e s . T h i s w a s e x p r e s s e d a s e
1
! e
2
i n t h e a b o v e d i s c u s s i o n . I n C T L , i t b e c o m e s :
: E : e
2
U ( e
1
E G : e
2
)
T h a t i s , t h e r e i s n o c o m p u t a t i o n s u c h t h a t e
2
d o e s n o t o c c u r u n t i l a s t a t e s i s r e a c h e d w h e r e
s s a t i s e s ( e
1
E G : e
2
) , i . e . , e
1
i s e x e c u t e d i n s t a t e s , a n d s u b s e q u e n t l y , e
2
n e v e r o c c u r s .
2 3
8/8/2019 compu archi
25/25
T h e f o l l o w i n g i n s t a n c e s o f t h e a b o v e d e p e n d e n c i e s h a v e a l s o a p p e a r e d i n t h e l i t e r a t u r e .
C o m m i t D e p e n d e n c y C R 9 2 ] : T r a n s a c t i o n A i s c o m m i t - d e p e n d e n t o n t r a n s a c t i o n B , i i f
b o t h t r a n s a c t i o n s c o m m i t , t h e n A c o m m i t s b e f o r e B c o m m i t s . L e t t h e r e l e v a n t s i g n i c a n t
e v e n t s b e d e n o t e d a s c m
A
a n d c m
B
A G c m
B
) A G : c m
A
A b o r t D e p e n d e n c y C R 9 2 ] : T r a n s a c t i o n A i s a b o r t - d e p e n d e n t o n t r a n s a c t i o n B , i i f B
a b o r t s , t h e n A m u s t a l s o a b o r t . L e t t h e s i g n i c a n t e v e n t s h e r e b e a b
A
a n d a b
B
, s o t h i s c a n
b e w r i t t e n a b
B
! a b
A
, a n d i s r e n d e r e d i n C T L j u s t l i k e e
1
! e
2
a b o v e :
: E : a b
A
U ( a b
B
E G : a b
A
)
C o n d i t i o n a l E x i s t e n c e D e p e n d e n c y K l 9 1 ] : I f e v e n t e
1
o c c u r s , t h e n i f e v e n t e
2
a l s o o c c u r s ,
t h e n e v e n t e
3
m u s t o c c u r . T h a t i s , t h e e x i s t e n c e d e p e n d e n c y b e t w e e n e
2
a n d e
3
c o m e s i n t o
f o r c e i f e
1
o c c u r s . T h i s c a n b e w r i t t e n e
1
! ( e
2
! e
3
) . T r a n s l a t i n g i t t o C T L i n v o l v e s t w o
a p p l i c a t i o n s o f t h e t r a n s l a t i o n o f e
1
! e
2
g i v e n a b o v e , o n e n e s t e d i n s i d e t h e o t h e r . T h e r s t
a p p l i c a t i o n , t o e
2
! e
3
, y i e l d s t h e f o l l o w i n g \ m i x e d " f o r m u l a :
e
1
! : E : e
3
U ( e
2
E G : e
3
)
T h e s e c o n d a p p l i c a t i o n , w h i c h s u b s t i t u t e s : E : e
3
U ( e
2
E G : e
3
) ] f o r e
2
i n t h e C T L t r a n s l a t i o n
o f e
1
! e
2
g i v e n a b o v e , g i v e s u s
: E : : E : e
3
U ( e
2
E G : e
3
) U ( e
1
E G : : E : e
3
U ( e
2
E G : e
3
) ] ) ]
E l i m i n a t i n g t h e d o u b l e n e g a t i o n s n a l l y y i e l d s
: E E : e
3
U ( e
2
E G : e
3
) U ( e
1
E G E : e
3
U ( e
2
E G : e
3
) ] ) ]
A . 0 . 2 E x p r e s s i n g R e a l - t i m e D e p e n d e n c i e s i n C T L
W e u s e t h e v a r i a n t o f C T L c a l l e d R T C T L
( R e a l - T i m e C o m p u t a t i o n T r e e L o g i c ) E M S S 9 3 ] .
T h i s i s t h e s a m e a s C T L e x c e p t t h a t E F
t
m e a n s \ w i l l o c c u r a f t e r t o r m o r e t i m e u n i t s a l o n g s o m e
c o m p u t a t i o n . "
R e a l - t i m e O r d e r D e p e n d e n c y : I f b o t h e v e n t s e
1
a n d e
2
o c c u r , t h e n e
1
p r e c e d e s e
2
, a n d e
2
o c c u r s w i t h i n t t i m e u n i t s o f e
1
A G ( e
2
) A G : e
1
) ( e
1
) : E F
t
e
2
)
R e a l - t i m e E x i s t e n c e D e p e n d e n c y : I f e v e n t e
1
o c c u r s s o m e t i m e s , t h e n e v e n t e
2
a l s o o c c u r s
s o m e t i m e s . F u r t h e r m o r e , e
2
o c c u r s n o l a t e r t h a n t t i m e u n i t s a f t e r e
1
: E : e
2
U ( e
1
E G : e
2
) ^ : E F e
1
E F
t
e
2
2 4