I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute r  E ng in ee ring   ( I J E CE )   Vo l.   9 ,   No .   2 ,  A p r il   201 9 ,   p p .   1298 ~ 1 3 0 3   I SS N:  2088 - 8708 ,  DOI : 1 0 . 1 1 5 9 1 / i j ec e . v 9 i 2 . pp 1 2 9 8 - 1303           1298       J o ur na l ho m ep a g e :  h ttp : //ia e s co r e . co m/ jo u r n a ls /in d ex . p h p / I JE C E   Surv ey  on  replica tion tec hniques   fo r   distrib uted  sy st e m       Ah m a d S hu k ri  M o hd   No o r   1 ,   Nur  F a rha h  M a t   Z ia n 2 ,   F a t in Nurha na ni M .   Sh a if ul B a hri 3   1 ,2 S c h o o l  o f   In f o rm a ti c s an d   A p p l ied   M a th e m a ti c s,  Un iv e rsiti   M a lay sia ,   M a la y sia   3 De p a rtme n t  o f   M a th e m a ti c s ,   F a c u lt y   o f   S c ien c e ,   Un iv e rsiti   T e k n o lo g i   M a lay si a ,  M a la y sia       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   Au g   2 6 ,   2 0 1 8    R ev i s ed   Oct   1 6 ,   2 0 1 8   A cc ep ted   No v   1 0 ,   2 0 1 8       Distrib u te d   sy ste m s   m a in l y   p ro v id e   a c c e ss   to   a   larg e   a m o u n t  o f  d a ta  a n d   c o m p u tatio n a l  re so u rc e s  th ro u g h   a   w id e   ra n g e   o f  in terf a c e s.  Be sid e s  it s   d y n a m ic  n a tu re ,   w h ich   m e a n s  th a t  re so u rc e s  m a y   e n ter  a n d   lea v e   th e   e n v iro n m e n t  a t  a n y   ti m e ,   m a n y   d istri b u ted   sy s t e m s  a p p li c a ti o n s  w il l  b e   ru n n in g   i n   a n   e n v iro n m e n t  w h e re   f a u lt s  a re   m o re   li k e l y   to   o c c u r  d u e   to   th e ir   e v e r - in c re a sin g   sc a les   a n d   th e   c o m p lex it y .   Du e   to   d iv e rs e   f a u lt s  a n d   f a il u re s  c o n d i ti o n s,  f a u lt   to lera n c e   h a s  b e c o m e   a   c rit ica l  e le m e n t  f o r  d istri b u ted   c o m p u ti n g   in   o r d e r  f o r  th e   sy ste m   to   p e rf o r m   it s  f u n c ti o n   c o rre c tl y   e v e n   in   th e   p re se n t   o f   f a u lt s.  Re p li c a ti o n   tec h n iq u e s  p rim a ril y   c o n c e n trate   o n   th e   tw o   f a u lt   to lera n c e   m a n n e rs  p re c ise l y   m a s k in g   th e   f a il u re s  a s  we ll   a s   r e c o n f ig u re   th e   sy st e m   in   re sp o n se .   T h is  p a p e r  p re se n ts  a   b rief   su rv e y   o n   d if f e re n t  re p li c a ti o n   tec h n iq u e s  su c h   a s  Re a d   On e   W rit e   A ll   (RO WA ),   Qu o ru m   Co n se n su s  (QC),  T re e   Qu o ru m   (T Q)   P ro t o c o l,   G rid   Co n f ig u ra ti o n   (G C)   P r o to c o l,   T w o - Re p li c a   Distrib u ti o n   T e c h n iq u e s  (T RD T ),   Ne ig h b o u r  Re p li c a   T ria n g u lar  G rid   (NRTG )  a n d   Ne ig h b o u r  Re p li c a ti o n   Distr ib u ted   T e c h n iq u e s  (NRD T ).   T h e se   tec h n iq u e s  h a ve   it s  o w n   re d e e m in g   f e a tu re s  a n d   sh o rtco m in g   w h ich   f o r m s th e   su b jec t  m a tt e r  o f  th is  su rv e y .   K ey w o r d s :   Dis tr ib u ted   co m p u ti n g   Dis tr ib u ted   s y s te m s   Fau lt  f ail u r e  r ec o v er y     Hig h   av ailab il it y     R ep licatio n   tec h n iq u e     Co p y rig h t  ©   2 0 1 9   In stit u te o f  A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .    Al l  rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   Ah m ad   Sh u k r i b in   Mo h d   No o r ,   Dep ar t m en t o f   C o m p u ter   Scie n ce ,   Sch o o l o f   I n f o r m atic s   an d   A p p lied   Ma th e m at ics,   Un i v er s iti Ma la y s ia  T er en g g a n u   2 1 0 3 0   Ku ala  T er en g g an u   T er en g g an u ,   Ma la y s ia.   E m ail:  as h u k r i @ u m t.e d u . m y       1.   I NT RO D UCT I O N     A   d is tr ib u ted   co m p u ti n g   s y s t e m   is   a  f i n ite  s et  o f   s ite s   th a t   ar e  co n n ec ted   b y   co m m u n ic atio n   li n k s   an d   is   r esp o n s ib le  f o r   p r o v id in g   t h e  m ai n   ex ec u tio n   p la tf o r m   f o r   Hi gh - P er f o r m a n ce   C o m p u tin g   ( HP C ) .   Hig h   av a ilab ilit y   is   th e   m o s t  i m p o r tan t  ele m e n ts   o f   a  r elia b le  d is tr ib u ted   s y s te m .   S in ce   s ites   a n d   li n k s   ar e   p r o n e  to   f ailu r es,  a  p r o p er ty   o f   d is tr ib u ted   co m p u ti n g   ca ll ed   f au lt  to ler a n ce   en ab les  t h e  s ites   to   ca r r y   o n   f u n ctio n i n g   e v en   o n   t h e  in d i v id u al  co m p o n en t  h a s   f ai led   w it h o u t  ter m i n ati n g   t h e  en tir e  s y s te m .   W it h   t h e   p r esen t  o f   f a u lt  i n   th e  s y s te m ,   it  w ill  d is tu r b   th e  n o r m al  e x e cu tio n   a n d   m a y   ca u s e  t h e  s y s t e m   to   o p er ate  in   an   u n u s u al  w a y .   Fa u lt to ler an ce   c o n s is ts   o f   t w o   m ai n   co m p o n e n ts   th at  ar e  f au l t d etec tio n   an d   f au lt r ec o v er y .   A   f a u lt   is   a   d ef ec t   at  t h e  lo west  le v el  o f   ab s tr ac tio n   as   d ef in ed   i n   [ 1 ]   an d   m a y   ca u s e  a n   er r o r ,   an   in ter n a l  d ata  s tate.   Fro m   t h e  e r r o r ,   it  m a y   lead   to   ex ter n al l y   v is ib le  d ev iatio n   f r o m   th e  s y s te m   co r r ec tn es s   b eh av io u r   w h ic h   ca lled   a s   a  f ailu r e.   Desp ite  th e  f ac t  th at   a  f au lt  n ee d   n o t  r es u lt  i n   a n   er r o r   o r   an   er r o r   in   a   f ail u r e.   W h en   a  f au l t  is   d etec ted ,   th e  s y s te m   eit h er   r ec o v e r s   th ei r   s tate  b y   l u ck   o r   b y   t h e  d esi g n a ted   f a u lt   to ler an ce ,   s o   as to   w ar d   o f f   a n y   f ai lu r e.   R ep licatio n   i s   a  s i g n if ica n t  te ch n iq u e  u s ed   f o r   m a s k in g   er r o r s   in   th e  r ep licated   co m p o n e n t  i n   o r d er   to   ac h iev e  f a u lt  to ler an t  in   d is t r ib u ted   s y s te m s .   I t  is   a  p r o ce s s   o f   m a i n tai n i n g   d if f er e n t  co p ies  o f   d ata  o r   o b j ec t   an d   th e  s y n c h r o n izatio n   o f   u p d atin g   th e  d ata  in   its   r ep lica.   I t  is   n o t  a  b ac k u p   m e th o d   w h e r e  d ata  o r   o b j ec t  is   n o t  a u to m atica ll y   o v er w r itte n   w h e n ev er   t h er e  ar e  a n y   c h an g es  to   t h e  o r ig in al   d ata  a n d   i m m ed iatel y   lo s e   an y   Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2088 - 8708       S u r ve y  o n   r ep lica tio n   tech n iq u es fo r   d is tr ib u ted   s ystem   ( Ah m ad   Sh u k r i  Mo h d   No o r )   1299   h is to r ical  s tate.   I t  h as  to   d ea l  w it h   w h en   a n d   w h er e  to   co p y   th e  d ata,   r eso u r ce   o p tim izati o n   an d   g r o w in g   o r   s h r i n k in g   t h e  r ep licatio n   tr ee .   R ep licatio n   co n s i s ts   o f   t w o   t y p e s   o f   s o l u tio n   t h at  i s   s y n c h r o n o u s   a n d   as y n c h r o n o u s   r ep licatio n .   T h e  s y n c h r o n o u s   s o l u tio n   will  u p d ate  t w o   r ep licas  at  t h e  s a m e  ti m e  a n d   w ill  r o ll   b ac k   if   o n e  f ails .   T h e  b en ef it s   o f   th is   t y p e  o f   s o lu t io n   ar e  it   is   h i g h   a v a ilab ilit y ,   a u to   f ail - o v er   a n d   m i n i m al  d ata  lo s s   en co u n ter ed .   Ho w ev er ,   th i s   s o lu tio n   w ill  h a v e  to   d ea l  w ith   n et w o r k   ef f icie n c y ,   s ca lab ilit y ,   co s t   an d   it  is   les s   f le x ib ilit y .   Fo r   an   as y n c h r o n o u s   s o l u tio n ,   ch a n g es  o n   th e  p r i m ar y   r ep lica  w il l  b e  ca p tu r e d   im m ed iatel y   i n   a   ti m el y   p r o p ag ated .   T h is   s o lu ti o n   o f f er s   a   lo w   co s t,   f le x ib le  an d   s ca lab le  s o lu tio n   b u t  n ee d s   to   d ea l  w i th   d ata   lo s s   a n d   n et w o r k   b an d w id t h .   R ep licatio n   b r ea k s   in to   t w o   s ch e m es   th a t  ar e  f u l l  r ep licat io n   ( all - d ata - to - all - s ites )   an d   p ar tial  r ep licatio n   ( all - d ata - to - s o m e - s i tes).   I n   t h is   p ap er ,   th e  s y n c h r o n o u s   s o lu t i o n   is   ch o s e n   f o r   its   h ig h er   r eliab ilit y   an d   s u itab ilit y   to   av o id   co n f l icts   b ased   o n   it s   q u o r u m   e x ec u tio n   o r   co m m it m en t p r o to co l.   I n   a  co n v e n tio n al  w a y   o f   c o m p u ti n g ,   f a u lt s   av o id an ce   an d   f a u lt s   r e m o v a l  tech n iq u es  s u ch   a s   s tr u ct u r ed   p r o g r a m m i n g ,   s o f t w ar e  r e u s e,   te s ti n g   an d   s o   o n   ar e  ab le  to   d eliv er   d ep en d ab il it y   f o r   t h e  s o f t w ar e   b y   d etec tin g   a n d   e x p u n g i n g   t h e  f au l ts   i n   th e  s y s te m s .   Ho w ev er ,   in   a  lar g e   an d   d y n a m ic  d is tr ib u ted   s y s te m ,   m illi o n s   o f   co m p u ti n g   d ev ice s   co n n ec ted   to   ea ch   o t h er   v ia   co m m u n icatio n   li n k s   ar e  p r o n e  to   f ail u r es  a n d   th ese  tech n iq u e s   a r e  n o t  e n o u g h   to   to ler ate  th e  f ail u r es.  D i s tr ib u ted   s y s te m s   allo w   m a n y   u s er s   ac ce s s   to   a   co m m o n   co m p u ti n g   r e s o u r ce   h en ce   p r o v id i n g   r eso u r ce s   s h ar in g   ca u s in g   a  s i n g le  f a u lt  c an   b e  in e v itab le  in   th is   co m p u ti n g   en v ir o n m e n t.    T h e  ab ilit y   to   to ler ate  f ail u r es   w h ile  ef f icie n tl y   e x p lo itin g   t h e  co m p u t in g   r eso u r ce s   i n   an   ac ce s s ib le   m an n er   m u s t  b e  an   es s en t ial  p ar t  o f   d is tr ib u ted   co m p u t in g   i n f r a s tr u ct u r e.   T h er ef o r e,   a  f au lt - to ler an t  ap p r o ac h   w il l b e  u s e f u l i n   o r d er   to   p o ten tiall y   p r ev e n t  m al icio u s   s i tes  th at  ar e  d i s t r ac tin g   th e  o v er all  p er f o r m a n ce   o f   t h e   en v ir o n m e n t.  A   d i s tr ib u ted   s y s te m   is   e x p ec ted   to   b e  m ai n tai n ed   in   t h e  p r ese n ce   o f   p ar tial  f ail u r es  at  t h e  le v el   o f   f a u lt  is o latio n   o r   ev en   h ig h er   lev el  o f   f a u lt  to ler an t.  T o   a ch iev e  f a u lt  to ler an ce ,   w e  eit h er   r ec o n f i g u r e  t h e   s er v ice  to   ta k e  ad v a n ta g e  o f   th e  n e w   co m p o n e n t s   o r   d esig n   a  m ec h a n is m   to   m as k   f a ilu r e  o n - t h e - f l y   b y   p lacin g   r ed u n d a n t  r eso u r ce s .   R ep licatio n   tech n iq u es  p r i m ar il y   co n ce n tr ate  o n   th e s e   t w o   f a u lt  to ler an ce   m an n er s .   R ep licatio n   e n ab les  t h e  s y s te m s   to   b e  r ec o n f i g u r ed   i n   o r d er   to   allo ca te  m o r e  r ep licas  to   t h e  s y s te m s ,   in   e n s u r i n g   f lex ib il it y   o f   t h e  s y s te m   s o   as   to   p r eser v e   its   d ep en d ab ilit y .   I t  is   ca p ab le  to   p r o d u ce   th e   ag g r e g ated   co m p u ti n g   p o w er   o f   al l  t h e  r ep lica  s ites   to   w i t h s ta n d   o n   a  s in g le   lo ad   ca te g o r y   th u s   g iv e s   it   a   ca p ac it y   to   i m p r o v e  t h e  co m p u ti n g   p er f o r m an ce .   T h eo r etica ll y ,   t h e  co m p u ter   s y s te m   w i ll  b e  ab le  to   ac h iev e  h ig h er   r eliab ilit y   b y   u s i n g   m o r e  r eliab le  co m p o n en ts   w h ich   w ill  b e  m o r e  r o b u s t  as  it  i s   u s in g   m o r e  r eliab le   p ar ts   o r   m o r e  s u itab l e  m ater i als.  I n   cir cu m s tan ce s   w h er e  u s in g   m o r e  r eliab le  co m p o n e n t s   is   n o t  an   o p tio n ,   r ep licatio n   is   th e  b est  ap p r o ac h   to   p r o v id e  h ig h l y - r eliab le  s y s te m s   b y   u s i n g   less   r eliab le  co m p o n e n t s .   W h en   an   o b j ec t  is   r ep licated ,   it  w il l  h a v e  s e v er al  id en tica l  co p ies  o f   t h e  o b j ec t  ca lled   r ep lic as.  I n   t h e  ev e n t  o f   f ail u r e,   th e   f ail u r e  is   m a s k ed   b y   it s   o t h er   r ep licas  t h u s   av ailab ilit y   i s   g u ar an teed   i n   s p ite  o f   t h e  f ail u r e.   T h e  tech n iq u e s   in   r ep licatio n   h av e  b ee n   s u cc ess f u ll y   i m p l e m en ted   f o r   d is tr ib u ted   co m p u ti n g   s y s te m s   an d   allo w   s u c h   s y s te m   to   r e m ai n   d is tr ib u ted ,   at  th e  s a m e  ti m e  i n cr ea s in g   th eir   a v ailab ilit y   as  w ell  a s   p er f o r m a n ce   in   a  lar g e  d e g r ee   w h er e  t h e  s y s te m   i s   ab le  to   o p er ate  in   th e  p r esen ce   o f   f au l t  w it h o u t  u s er   in ter v en t io n   to   to ler ate  th e  f ail u r es t h at  m a y   o c cu r   in   t h e  d is tr ib u ted   co m p u ti n g   e n v ir o n m en t.       2.   RE AD  O N E   WRI T E   AL L   ( RO WA)   T h is   is   t h e  m o s t  co m m o n   a n d   s tr aig h t f o r w ar d   p r o to co l  u s e  in   r ep licati n g   t h e  s y s te m   wh ich   k ee p s   m u ltip le  co p ies  o f   r ep licas  th at  allo w   an y o n e  ca n   b e  r ea d   an d   m u s t  all  b e  u p d ated .   T h is   p r o to co l  w ill  tr a n s lat e   a  lo g ical  r ea d   o p e r atio n   o n   a  d ata  item   i n to   o n e  p h y s ical  r ea d   o n   an y   o f   its   r ep licas  an d   tr an s late s   all  its   lo g ical  w r ite s   o p er atio n   to   p h y s ical   w r ites   o p er atio n   o n e  at   ea ch   r ep lica.   T h e  ac ce s s   to   e ac h   r ep lica  w il l  b e   s y n ch r o n ized   b y   t h e  m a in   c o n cu r r en c y   co n tr o ller   th u s   m ak e s   th is   p r o to co l  is   eq u iv alen t   w ith   a  s er ial   ex ec u t io n   w h er e  ea ch   r ep lica  th at  u p d ate  th e  d ata  ite m   w il l u p d ate  all  o f   its   co p ies o r   n o n e  at  all.     R OW A   p r o v id es  a  s i m p le   an d   eleg an t   tech n iq u e  w h ich   h as  th e   ab ilit y   to   p r o ce s s   r ea d   o p er atio n   r eg ar d less   o f   a n y   co m m u n icat io n   f ail u r es  s in ce   o n e   s ite   w il l  r e m ai n   u p   a n d   r ea ch ab le.   T h e  c h ar ac ter is tic   o f   R OW A   t h at  p r o v id es   r ea d   o p er atio n   m ak e s   it   s u itab le  f o r   t h e   en v ir o n m en t t h at  m o s t   o f   its   d ata  is   i n   r ea d - o n l y   o v er h ea d .   T h e  s ig n i f ican t  d r aw b ac k s   o f   R OW A   is   th e  p r o to co l  is   r ig id   in   s elec ti n g   i t s   r ea d   av ailab ilit y   a n d   w il l  b lo ck s   all  th e  w r ites   o p er atio n   if   o n e  s ite  is   d o w n   o r   u n r ea ch ab le  u n til  t h e  f ailu r es  is   r ep air ed .   T h is   ev en t u all y   w il l c o s t in cr e m en t in   r esp o n s e  ti m e  an d   d ec r ea s es its   p er f o r m a n ce .       3.   Q UO RUM   CO NSE NS US ( Q C)   O R  VO T I N G   T h e  Qu o r u m   C o n s e n s u s   ( QC )   m e th o d   g e n er all y   al lo w   w r i tes  o p er atio n   to   b e  r ec o r d ed   o n l y   at  a   s u b s et  ( a   w r ite  q u o r u m )   o f   th e  u p   s ites ,   o n   co n d itio n   th at  r ea d s   o p er atio n   is   m ad e  to   q u er y   a  s u b s et  ( a   r ea d   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   2 ,  A p r il   201 9   :   1 2 9 8   -   1303   1300   q u o r u m )   s p ec if icall y   p r o v ed   w il l  o v er lap   w it h   w r ite   q u o r u m .   T h e  r e ad   o p er atio n   w i ll  b e  ab le  to   r etu r n   its   m o s t  r ec en t l y   w r it ten   v alu e  wh en e v er   th e  q u o r u m  in ters ec ti o n   co n d itio n   is   m et  a n d   w i ll  b e  s aid   as  h av e  vo te d   f o r   it,  g iv in g   t h e  QC   m et h o d   alter n ati v e  n a m e,   vo tin g .    T h e  q u o r u m s   ca n   b e  s tatic  o r   d y n a m ic  d ep en d s   o n   t h e   as s ig n ed   v o tes   an d   t h e  ca p ab ilit y   o f   t h e  s i te s   to   r ec o n f i g u r e  t h e  q u o r u m   s p ec if icatio n .   QC   i s   ab le  to   m as k   f ail u r es  w i th o u t  a n y   in ter v en t io n   u n til  t h e   f ail u r es  i s   to ler ated .   Ho w e v er ,   th is   tech n iq u e  w il l  co s t   th e   r ea d   o p er atio n   f air l y   e x p en s iv e   s i n ce   t h e   i m p le m en ta tio n   o f   t h e  id ea   al w a y s   a  d i f f ic u lt c h alle n g e   [ 2 ] .       4.   T RE E   Q UO RUM   ( T Q )   P RO T O CO L   T r ee   Qu o r u m   ( T Q)   w as  p r o p o s ed   b y   A g r a w al  a n d   E l - A b b ad i  [ 3 ]   th at  ap p lies   r ep licatio n   in   a  lo g ical   tr ee   s tr u ct u r e  o v er   a   d is tr ib u t ed   s ite  as   s h o w n   in   Fi g u r e  1 .   Fro m   t h i s   s tr u ct u r e,   a  r ea d   q u o r u m   is   ab le  to   b e   p er f o r m ed   b y   th e   r o o t  o r   th e   m aj o r ity   o f   its   c h ild r en   w h i le   f o r   w r ite   q u o r u m   it  i s   f o r m e d   f r o m   th e   r o o t,  a  m aj o r ity   o f   its   c h ild r en   a n d   a  m aj o r ity   o f   th eir   c h ild r en   a n d   s o   f o r th   u n ti l it  h a s   r ea ch ed   th e  leav es o f   t h e  tr ee .     I n   a  b est  ca s e,   a  r ea d   q u o r u m   w il l  co n s i s t  o f   o n l y   a  r o o t,  {1 }.   I f   th e  r o o t  f ails ,   a  q u o r u m   is   f o r m ed   b y   th e  m aj o r ity   o f   th e  co p ies  at  l ev el  1 ,   e. g .   {2 ,   3 },   {3 ,   4 }  o r   { 2 ,   4 }.   I n   th e  ca s e  o f   n o   m aj o r it y   ar e  ac ce s s ib le  at  lev el  1   o r   o n l y   n o d e  4   is   ac c es s ib le,   n o d es 2   a n d   3   w ill b e  r e p lace d   b y   t h eir   c h ild r en   i n   t h at   o r d er .   I n   th e  ev e n t   o f   all  co p ies   in   le v el  0   a n d   1   f ailed ,   a  q u o r u m   w ill   b e  p er f o r m ed   b y   th e   m aj o r it y   o f   th e  c h ild r en   o f   t h e   s elec ted   m aj o r it y   at  lev el  1 .   T h e  s ize  o f   t h e  w r ite  q u o r u m   i s   f i x ed   b u t th e  m e m b er s   m a y   b e  d if f er e n t.    T h e  ad v an tag e  o f   t h is   p r o to co l  is   th e  w r i te  o p er atio n   ca n   ac ce s s   t h e  n u m b er   o f   co p ies  al w a y s   les s   th an   a  m aj o r ity   o f   t h e  q u o r u m   w h ile  f o r   t h e  r ea d in g   o p er atio n   it  m a y   ac ce s s   o n l y   o n e   co p y .   Fo r   a  r ea d   o p er atio n ,   th e  co s t  o f   e x ec u ti n g   i s   co m p ar ab le  w i th   R OW A   b u t  f o r   a  w r ite   o p er atio n ,   it  g a v e  t h e  m u c h   b etter   r esu lt.  U n f o r t u n ate l y ,   t h e  w r i t e  o p er atio n   w ill  b e  f ailed   to   b e  ex ec u ted   if   m o r e  th a n   a  m aj o r ity   o f   th e  co p ies  at  an y   le v el  o f   t h e  tr ee   b ec o m e  u n av ai lab le.           Fig u r e  1 .   A  tr ee   q u o r u m   o r g an izatio n   o f   1 3   co p ies o f   d ata  o b j ec t       5.   G RI D  CO NF I G URA T I O N  ( G C)   P RO T O CO L   T h is   p r o to co l  is   in tr o d u ce d   b y   Ma ek a w a  [ 4 ]   w h er e  all  q u o r u m s   ar e  o f   eq u al  s ize  in   o r d er   to   o b tain   a   d is tr ib u ted   m u t u al  e x clu s io n   a lg o r ith m   w h ic h   later   e x ten d ed   b y   C h eu n g   et  a l.   [ 5 ]   an d   Ku m ar i  an d   Me e n u   [ 6 ]  f o r   r ep licated   d ata  o b j ec ts .   T h is   p r o to co l  in tr o d u ce d   n   co p ies  o f   d ata  o b j ec ts   ar e  lo g ica l l y   o r g a n ized   i n   th e   f o r m   o f   a  √   n   x   √   n   as d ep icted   in   Fig u r e  2 .   R ea d   q u o r u m   co n s i s t  o f   a  co p y   f r o m   ea c h   co lu m n   in   t h e  g r id   w ill  b e  ac q u ir ed   in   o r d er   to   p er f o r m   r ea d   io n   o n   th e  d ata  item s .   W h ile  f o r   w r ite  o p er atio n s   to   b e  p er f o r m ed ,   w r ite  q u o r u m   co n s is ts   o f   all  co p ies  i n   o n e  co lu m n   a n d   a  co p y   f r o m   ea ch   o f   t h e   r e m ai n i n g   co lu m n s   w ill   b e  n ee d ed .   T h is   p r o to co l  in tr o d u c ed   t h e   r ea d   an d   w r ite  o p er atio n   in   t h e   s ize  o f   O  ( √ n ) .     Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2088 - 8708       S u r ve y  o n   r ep lica tio n   tech n iq u es fo r   d is tr ib u ted   s ystem   ( Ah m ad   Sh u k r i  Mo h d   No o r )   1301       Fig u r e  2 .   A   g r id   co n f i g u r atio n   w it h   2 5   co p ies o f   d ata  o b j ec t       I n   th e  co n f i g u r atio n   d ep icted   in   Fi g u r e  2 ,   to   ex ec u te  a  w r i t e  o p er atio n ,   co p ies  {1 ,   6 ,   1 1 ,   1 6 ,   2 1 ,   7 ,   1 3 ,   1 9 ,   2 5 }  is   r eq u ir ed   w h ile   t o   ex ec u te  r ea d   o p er atio n   co p ies  {1 ,   2 ,   3 ,   4 ,   5 }  is   s u f f ic ien t   en o u g h .   Gen er all y ,   th is   p r o to co l  h as  a  le n g th   o f   x   an d   a  w id t h   o f   y   s o   ca n   b e  p r esen ted   a s   ( x ,   y ) .   A   r ea d   o p er atio n   is   p er f o r m ed   w h e n   r etr iev in g   a  r ea d   q u o r u m   ( x ,   y )   th at  f o r m ed   f r o m   x   co p ies  in   ea ch   o f   y   d if f er e n t  co lu m n s .   Fo r   a  w r it e   o p er atio n ,   th e  w r ite  q u o r u m   i s   f o r m ed   f r o m   x   co p ies  in   ea ch   o f   y   co lu m n s   an d   an y   √n – x + 1   co p ies  in   ea ch   o f   √ n + y + 1   co lu m n .   T h e  q u o r u m   in ter s ec tio n   p r o p er ty   b et w ee n   r ea d in g   an d   w r ite  q u o r u m   i s   d et er m in ed   b y   th e   r ea d   g r id   q u o r u m   s ize  w h er e  if   th e  s ize  ( x ,   y )   t h e n   w r i te  g r id   q u o r u m   m u s t b e  ( √ n – x + 1 ,   √ n – y +1 ) .     T h e  d r aw b ac k s   o f   t h is   tec h n iq u e  ar e  th i s   s tr u ctu r e  d eg r ad e  th e  co m m u n icatio n   co s t  an d   th e   av ailab ilit y   o f   d ata  as  th e  n u m b er   o f   co p ies  f o r   b o th   r ea d   an d   w r ite  q u o r u m   is   b ig   as  well  as  p r o n e  to   f ailu r e   o f   th e  e n tire   r o w   a n d   co lu m n   i n   th e  g r id .       6.   T WO - RE P L I C A  DIS T R I B UT I O N  T E CH N I Q UE   ( T R DT )   T w o - r ep lica  d is tr ib u tio n   tec h n iq u e  ( T R DT )   h as  b ee n   p r o p o s ed   b y   S h en   et  a l.   [ 7 ] .   T h is   tech n iq u e  in tr o d u ce d   th a t  o n   ea c h   n o d e  h as  a n   eq u al  ca p ac it y   f o r   s to r ag e  an d   all  d ata  h a v e  t w o   r e p licas  o n   d i f f er e n t   n o d es  an d   a ll  n o d es  h a v e  t w o   d ata  r ep licas.  Fo r   N  n o d es,  it  i s   d iv id ed   to   n   s et  o f   n o d es  ( N =2 n )   w h er e  ea c h   o f   th e  s et  co n s is ts   o f   t w o   n o d es a s   illu s tr ated   in   F ig u r e  3 .           Fig u r e  3 .   Data   r ep lic a  d is tr ib u tio n   tech n iq u e  w h e n   N= 2 n       E ac h   r ec tan g le  r ep r esen ts   t h e  n o d e  w h ile  f o r   ea ch   o v al  r ep r esen t s   a  s et  th at  co n s i s ts   o f   t w o   n o d es.   Data   x   a n d   y   h as  t w o   r ep lica s ,   th at  i s   i n   n o d es  f r o m   s et  1   an d   s o   as  d ata  f r o m   s et  b   al s o   h as  t w o   r ep lica s   lo ca ted   in   n o d es  f r o m   s et  2   a n d   s o   o n .   T h e  r ep licatio n   is   d ir ec tl y   d o n e  o n   it s   r ep lica  w h en ev er   t h e  p r i m ar y   n o d e  r ec eiv es a   r eq u est  f r o m   t h e  r ep licatio n   li n k   a n d   th i s   r ep licatio n   tec h n iq u e  u s es a s y n ch r o n o u s   r ep licatio n .   T h e  w ea k n e s s   o f   th i s   tec h n iq u e  is   e v e n   t h o u g h   t h e  i n cr e m en t  o f   t h e   av ailab il it y   is   n o t   tr iv i al,   T R DT   d o u b le  u p   th e  r eso u r ce s   a s   it  ad d ed   u p   to   ea ch   o f   th e  s er v e s   w ith   s ec o n d   r ep lica  [ 4 ] .   T R DT   also   ac q u ir e  th e  s y s te m   to   h av e   r ep lica - a v aila b ilit y   o f   m o r e  t h an   9 9 %  i n   o r d er   to   a ch ie v e  h ig h   r el iab ilit y   p lu s   t h e  o p er atio n   ca n n o t  b e  co m p leted   if   o n e  o f   th e  s et s   is   u n a v ailab le  [ 8 ] .   T h is   tech n iq u e  al s o   ex p o s es  t h e  n o d e  to   ex p er ien ce   d o u b le  f au lt s   in   ca s e  o f   b o th   r ep licas is   d a m a g ed   o r   lo s t.       Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I n t J   E lec  &   C o m p   E n g ,   Vo l.  9 ,   No .   2 ,  A p r il   201 9   :   1 2 9 8   -   1303   1302   7.   NE I G H B O UR  RE P L I C A  T RIA G UL AR  G RID ( NR T G )   Neig h b o u r   R ep lica  T r ian g u la r   Gr id   ( NR T G)   w as  p r o p o s ed   b y   Ma m at   et  a l.   [ 9 ] .   T h e  co n ce p t  o f   n eig h b o u r   r ep licatio n   is   p ar ti al  r ep licatio n   ( all - d ata - to - s o m e - s ite s )   w h er e  r ep licated   d ata  o n l y   co p ied   to   th e  n o d e’ s   n eig h b o u r s .   I n   t h is   te ch n iq u e,   all  s ites   ar e  lo g icall y   o r g a n ized   in   t h e  f o r m   o f   th e  tr ian g u lar   g r id   s tr u ct u r e.   T h is   s tr u ct u r e  is   in h er ited   f r o m   t h e  b in ar y - tr ee   s tr u ct u r e  w h er e  th e  i n n er   lea v es  o f   t h e  tr ee   ar e  lin k ed   to g eth er   a s   s h o w n   i n   Fig u r e  4 .   E ac h   o f   th e  s ites   i n   th e  s tr u ctu r e  h as  a  m aster   d ata  f ile .   I f   t h e  s i te  is   o p er atio n al,   th e  co p ies  w il l b e  av ailab le  at  th e  s ites   o t h er w is e   it is   u n av a ilab le.     E ac h   o v a l  r ep r esen t s   a   n o d e.   Data   f r o m   n o d e  1   w il l  b e  r ep licated   to   n o d e  2   an d   n o d e  3   w h ic h   ar e   n eig h b o u r s   to   n o d e  1 .   Fo r   n o d e  5 ,   it  h as  f o u r   n ei g h b o u r s ,   w h ich   ar e  n o d es  2 ,   3 ,   8   an d   9 .   T h er ef o r e  n o d e  5   h as   f i v e  r ep licas.  T h is   s h o w s   th at  ea ch   n o d e  in   th e  tr ee   r eq u ir ed   th e  m a x i m u m   n u m b er   o f   r ep licatio n s   is   5   h e n ce   th is   tec h n iq u e  m in i m ize s   th e  s to r ag e  ca p ac it y   as  co m p ar ed   w it h   f u ll  r ep licatio n   s c h e m e.   NR T G  r eq u ir es  a   m i n i m u m   n u m b er   o f   q u o r u m   s izes   th u s   p r o v id i n g   h ig h   a v ailab ilit y   o f   ex ec u ti n g   w r ite   o p er atio n s   in   th e  r ep licated   d atab ase.           Fig u r e  4 .   T r ian g u lar   n ei g h b o r   o r g an izatio n   o f   n   s ites       8.   NE I G H B O UR  RE P L I C AT I O N  DIS T RIB UT E D  T E CH NIQU E   ( NRD T )   Neig h b o u r   R ep licatio n   Dis tr ib u ted   T ec h n iq u e  ( NR DT )   w a s   in tr o d u ce d   b y   Ma m at  et  a l.   [ 8 ] .   I n   th i s   tech n iq u e,   al l  n o d es  ar e  lo g i ca ll y   o r g an ized   i n   t h e  f o r m   o f   t w o - d i m e n s io n al   n x n   g r id   s tr u c tu r e.   I t   w ill   lo g icall y   o r g an ize  i n   t h e  f o r m   o f   n   x   n   w h en   t h er e  ar e  n o d es in   th e  e n v ir o n m en t  w h er e  N= n 2 .     Fro m   F ig u r e  5   w e   as s u m e  th at   th e   en v ir o n m e n t  co n s i s ts   o f   9   n o d es  r ep r esen ted   b y   th e   cir c les  s o   th a t   it  w ill  b e  lo g ic all y   o r g an ized   in   th e  f o r m   o f   3 x 3   g r id   s tr u ct u r e.   E ac h   o f   th e  n o d es  h as  i ts   o w n   m aster   d ata  f ile.   I n   th i s   tec h n iq u e,   u p d ates  o n   t h e  p r i m ar y   co p y   w ill  b e  f ir s t  co m m i tted   at  th e  p r i m ar y   n o d e  th en   w ill  later   b e   u p d ated   as y n c h r o n o u s l y   to   its   n eig h b o u r   co p ies  w it h in   a  s ep ar ate  tr an s ac tio n .     I n   NR DT ,   all  d ata  h as  s o m e  r ep licas  o n   d if f er en t  n o d es  an d   all  n o d es  h av e  s o m e  d at a  u n d er   th e   en v ir o n m e n t.  T h e  d ata  is   r ep licated   to   its   n eig h b o u r s   f r o m   its   p r i m ar y   n o d es  w h er e  t h e  n u m b er   o f   d ata  r ep licatio n   f r o m   ea c h   n o d e  is   less   o r   eq u a l  to   th e  n u m b er   o f   n eig h b o u r s   + a  d ata  f r o m   t h e  n o d e  its el f .   NR DT   ab le  to   in cr ea s e  th e  av ailab ilit y   o f   th e  d is tr ib u ted   en v ir o n m en t  m u ch   b etter   th a n   T R DT   m o d el  w it h   th e  les s   o v er h ea d   co s t  s in ce   i n   T R DT   m o d el  t h e  s y s te m   is   co m p r i s e d   f r o m   t w o   r ed u n d an t  co m p o n en t  [ 2 ] .   Ov er   ti m e,   th e  av ailab il it y   o f   t h e  NR DT   m o d el  r ed u ce s   i n   a  s m al l  p er ce n tag e  p er   y ea r   w i th   o n l y   p r ed icted   to   b e   1 . 2 %  f o r   th e  p er io d   o f   ten   y ea r s .           Fig u r e  5 .   Dis tr ib u ted   en v ir o n m en t  w it h   9   n o d es         Evaluation Warning : The document was created with Spire.PDF for Python.
I n t J   E lec  &   C o m p   E n g     I SS N:  2088 - 8708       S u r ve y  o n   r ep lica tio n   tech n iq u es fo r   d is tr ib u ted   s ystem   ( Ah m ad   Sh u k r i  Mo h d   No o r )   1303   9.   CO NCLU SI O N   T h is   p ap er   p r esen ts   a  b r ief   s u r v e y   o f   r ep licatio n   tec h n iq u es,  its   i m p o r ta n ce   in   d i s tr ib u t ed   s y s te m s   an d   th e  d if f er en t  tech n iq u es  t h at  ca n   b e  u s ed   to   im p le m e n t   th e  r ep licatio n .   T h e  d if f er en t   tech n iq u es  th at  ar e  av ailab le  in   c u r r en t  w o r k s   h av e  b ee n   ap p r o p r ia tel y   d is cu s s ed   u n d er   d if f er en t  h ea d in g s .   T h e  d escr ip tio n ,   co n ce p ts   an d   ill u s tr atio n   f o r   e ac h   o f   t h e  r ep licatio n   m o d els  h av e  b ee n   a n al y s ed   an d   p r ese n ted .         RE F E R E NC E S   [1 ]   He lal  A . A . ,   Bh a rg a v a   B. K.,   He d d a y a   A . A . ,   “ Re p li c a ti o n   T e c h n iq u e s  in   Distrib u ted   S y ste m s , ”   Kl u w e r  A c a d e m ic   P u b l ish e rs,  Un i ted   S tate s o f   Am e r ica ,   2 0 0 2 .   [2 ]   No o r  A . S . M . ,   He ra wa n   T . ,   De ris,   M . M . ,   “ Ne ig h b o r - Re p li c a   Distrib u ti o n   T e c h n iq u e   M o d e l  f o r  Av a il a b il it y   P re d ictio n   i n   Distri b u ted   In ter d e p e n d e n t  En v iro n m e n t , ”   In t’l   J o u rn a l  o f  Clo u d   Ap p li c a ti o n s  a n d   Co mp u ti n g ,   2 0 1 3 .   [3 ]   Ag ra w a l  D.  a n d   A b b a d i,   A . E. ,   “ Us in g   th e   T re e   Qu o ru m   P ro to c o l :  A n   E ff icie n t  A p p ro a c h   f o r  M a n a g in g   Re p li c a ted   Da ta , ”   Pro c   1 6 ,   In t’l   Co n f.   o n   Ver y   L a rg e   Da t a b a se ,   p p   2 4 3 - 2 5 4 ,   1 9 9 8 .   [4 ]   M a e k a wa   M .,   “ A   V n   A lg o rit h m   f o r  M u tu a l  Ex c lu si o n   in   De c e n tr a li z e d   S y ste m s , ”   ACM   T ra n sa c ti o n   o n   C o mp u ter   S y ste ms ,   V o l.   3   ( 2 ) ,   p p   1 4 5 - 1 5 9 ,   1 9 9 2 .   [5 ]   Ch e u n g   S . Y.,   Am m a r  M . H.,   Ah m a d   M . ,   “ T h e   G rid   P ro to c o l:   A  Hig h   P e rf o r m a n c e s   S c h e m a   f o r  M a in tain in g   Re p li c a ted   Da ta , ”   IEE E  T r a n sa c ti o n s  o n   K n o wle d g e   a n d   Da t a   E n g i n e e rin g ,   V o l. 4   ( 6 ) ,   p p .   5 8 2 – 5 9 2 ,   1 9 9 2 .   [6 ]   Ku m a ri  T . ,   M e e n u   S . ,   “ Dia g o n a l  Re p li c a ti o n   w it h   In ters e c ti o n   o f   Qu o ru m s  in   2 D  M e sh   (IQ2 DM)   P r o to c o l  f o r  G rid   En v iro n m e n t , ”   In ter n a ti o n a l  J o u r n a l  o f  I n n o v a ti o n s &   Ad v a n c e me n t  i n   Co m p u ter   S c ien c e ,   Vo l.   4 ,   2 0 1 5 .     [7 ]   S h e n   H.H. ,   Ch e n   S . M . ,   Z h e n g   W . M . ,   S h i  S . M . ,   “ Re se a rc h   o n   Da ta  Re p li c a   Distrib u ti o n   T e c h n iq u e   f o r  S e rv e r  Clu ste r , ”   IEE E  Pro c .   4 th   I n t’l .   Co n fer e n c e   o n   Pef o rm a n c e   C o mp u ti n g ,   Be ij in g ,   p p .   9 6 6 - 9 6 8 ,   2 0 0 0 .   [8 ]   M a m a t  R. ,   De ris  M . M . ,   Ja li l  M . ,   “ Ne ig h b o u r   Re p li c a   Distrib u ti o n   T e c h n iq u e   f o r  Cl u ste r  S e rv e r  S y s tem s ,”   M a la y sia   J o u rn a l  o f  Co m p u ter   S c ien c e ,   Vo l.   1 7   ( 2 ) ,   p p .   1 1 - 2 0 ,   2 0 0 4 .   [9 ]   M a m a t  A . ,   De ris  M . M . ,   A b a w a j y   J.H.,   Ism a il   S . ,   “ M a n a g in g   Da ta   Us in g   Ne ig h b o r  Re p li c a ti o n   o n   T rian g u lar - G rid   S tru c tu re , ”   6 th   In t e rn a ti o n a l  C o n f e re n c e ,   Rea d in g ,   UK ,   p p   1 0 7 1 - 1 0 7 7 ,   2 0 0 6 .         B I O G RAP H I E S O F   AUTH O RS       Ahm a d   S h u k r i  B in   M o h d   N o o r   Cu rre n tl y ,   h e   is  a n   a ss o c iate   p ro fe ss o r  o f   c o m p u ter  sc ien c e   a n d   De p u ty   De a n   a t  S c h o o l   o f   In f o r m a ti c s  A p p li e d   M a t h e m a ti c s,  U n iv e rsiti   M a lay sia   T e r e n g g a n u   (UMT ).   He   h a s  p u b li sh e d   m o re   th a n   5 0   re se a rc h   p a p e rs  in   v a rio u s   re f e rre d   jo u rn a ls,   c o n f e re n c e s,   se m in a rs  a n d   s y m p o siu m s.  He   a ls o   a p p o in ted   a s  Ch ief   Ed it o r  f o r  v a rio u s  S c o p u s  in d e x e d   jo u rn a l   a n d   c o n f e re n c e s.  He   re v ie w s  v a ri o u s  p a p e rs  i n   re f e re e d   jo u rn a ls  s u c h   a s  IEE E  a n d   E lse v ier.  He   w a s  a p p o in ted   a s  G e n e ra l  Ch a ir  a n d   tec h n ica l  c o m m it te e   f o r  v a ri o u s  ico n f e re n c e s.  He   re c e iv e d   se v e r a l  in v it a ti o n s as   in v it e d   sp e a k e r  f o r  v a rio u s co n f e re n c e s.  He   is   a   G o o g le On li n e   P r o f e ss io n a l   Ce rti f ied   a n d   C lo u d   P ro f e ss io n a l  Ce rti f ied .         Nu r   Fa r h a h   M a t  Z i a n   h a s  g r a d u a ted   f ro m   UMT ,   Tere n g g a n u   in   B. S c .   (Ho n s)  In f o rm a ti o n   T e c h n o lo g y   (S o f t w a r e   En g in e e rin g )  w it h   CG P A   o f   3 . 6 9 .   S h e   h a s   b e e n   a w a rd e d   w it h   d e a n ’s  li st   f o r  5   c o n se c u ti v e   se m e ste rs  a n d   w a s   a   B e st  G ra d u a te  f o r  D e p a rtm e n t  o f   Co m p u ter  S c ien c e ,   UMT ,   2 0 0 9   S o f tw a re   En g in e e rin g   Co u rse . S h e   o b tain e d   M S c   in   C o m p u ter  sc ien c e   in   2 0 1 5 .   F o r  h e r  m a ste r,   4   p a p e rs  h a v e   b e e n   w rit ten ,   3   h a v e   b e e n   p u b li sh e d   a n d   1   u n d e r  re v iew   o f   Jo u rn a l’s  re v ie w e r’ s  c o m m it tee .   Cu rre n tl y ,   sh e   is  a   P h .   D  c a n d i d a te  a   S c h o o l  o f   In f o rm a ti c s  a n d   A p p li e d   M a th e m a ti c s,  UM T .         Fa tin   Nurha n a n i  M .   S h a ifu l  B a h r i   Cu rre n tl y ,   stu d ied   a t  Un iv e rsiti   T e k n o lo g i  M a lay sia ,   Jo h o r   Ba h ru   in   Ba c h e lo r  o f   S c ien c e   ( M a th e m a ti c s)   w it h   CG P A   3 . 1 5 .   S h e   h e ld   h e r  p o siti o n   a s  Cre w  T u n   F a ti m a h   Co ll e g e   f o r  f o u r  y e a rs.  In   a d d i ti o n ,   sh e   h o l d s  th e   p o si ti o n   o f   se c re tar y   in   tw o   m a jo r   p ro g ra m s  n a m e l y   th e   In sp iratio n a l  W o m e n   S y m p o siu m   2 0 1 7 ,   o r g a n ize d   b y   th e   T u n   F a ti m a h   Co ll e g e ,   Un iv e rsiti   T e k n o lo g i  M a la y sia   a n d   th e   Ac a d e m ic   Ex c e ll e n c e   P ro g ra m   o f   th e   M a la y sia n   Hig h   S c h o o l  o rg a n ize d   b y   th e   F e d e ra ti o n   o f   M a lay   S tu d e n t  Un i o n s.  Be sid e s,  sh e   a lso   h e ld   a s  t h e   p ro t o c o l  u n i t  i n   th e   S c ien c e   In n o v a ti o n   C h a ll e n g e   P ro g ra m   (S IC),   F a c u lt y   o f   S c ien c e .     Evaluation Warning : The document was created with Spire.PDF for Python.