home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / comp / os / research / 839 < prev    next >
Encoding:
Internet Message Format  |  1992-07-25  |  4.5 KB
  1. Path: sparky!uunet!cis.ohio-state.edu!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!ames!agate!darkstar.UCSC.EDU!osr
  2. From: ymwang@crhc.uiuc.edu (Yi-Min Wang)
  3. Newsgroups: comp.os.research
  4. Subject: Summary: Checkpointing for Parallel and Distributed Systems
  5. Message-ID: <14pmr6INNniv@darkstar.UCSC.EDU>
  6. Date: 24 Jul 92 19:48:54 GMT
  7. Organization: Center for Reliable and High-Performance Computing, UIUC
  8. Lines: 99
  9. Approved: comp-os-research@ftp.cse.ucsc.edu
  10. NNTP-Posting-Host: ftp.cse.ucsc.edu
  11. Originator: osr@ftp
  12.  
  13. I am making an effort to construct the big picture for the area 
  14. of "checkpointing and rollback recovery for parallel and distributed 
  15. systems". The following list contains 26 papers and in no way covers 
  16. the whole area. Any additions, corrections and comments are welcome 
  17. and greatly appreciated.
  18.  
  19. My personal point of view starts from a general model with independent
  20. (uncooridnated) checkpointing for possibly non-deterministic execution,
  21. and the checkpointing pattern is independent of the communication 
  22. pattern. Such a model suffers from possible domino effect. Other 
  23. approaches are then classified according to their ways of handling 
  24. the domino effect, for example, checkpoint coordination, 
  25. communication-induced checkpointing and deterministic execution. 
  26.  
  27. =====================================================================
  28. (0) >>> The general model described above <<<
  29.  
  30.    (0.1) Tsuruoka, Kaneko and Nishihara [SRDSDS 1981]
  31.    (0.2) Bhargava and Lian              [SRDS   1988]
  32.    (0.3) Wang and Fuchs                 [SRDS   1992]
  33.  
  34. (1) >>> Checkpoint coordination <<<
  35.  
  36.    (1.1) Tamir and Sequin               [ICPP     1984]
  37.    (1.2) Chandy and Lamport             [ACM-TOCS 1985]
  38.    (1.3) Lai and Yang                   [IPL      1987]
  39.    (1.4) Koo and Toueg                  [IEEE-TSE 1987]
  40.  
  41.    (1.5) >>> Multicomputer <<< 
  42.         (1.4.1) Li, Naughton and Plank  [SRDS     1991]
  43.  
  44.    (1.6) >>> Clock synchronization and/or bounded message delay <<< 
  45.     (1.6.1) Ramanathan and Shin     [SRDS      1988]
  46.     (1.6.2) Cristian and Jahanian   [SRDS      1991]
  47.     (1.6.3) Tong, Kain and Tsai     [IEEE-TPDS 1992]
  48.     (1.6.4) Long and Fuchs          [Submitted 1992]
  49.  
  50. (2) >>> Communication-induced (message-triggered) checkpointing <<<
  51.  
  52.    (2.1) >>> Extra checkpoints at the sender side <<<
  53.     (2.1.1) Wu and Fuchs            [IEEE-TC   1990]
  54.  
  55.    (2.2) >>> Extra checkpoints at the receiver side <<<
  56.     (2.2.1) Briatico, Ciuffoletti and Simoncini [SRDSDS  1984] 
  57.     (2.2.2) Kim, You and Abouelnaga             [FTCS    1986]
  58.     (2.2.3) Venkatesh, Radhakrishnan and Li     [IPL     1987]
  59.  
  60. (3) >>> Piecewise deterministic execution (or the capability of 
  61. detecting/recording/replaying internal non-deterministic events) <<<
  62.  
  63.    (3.1) >>> Receiver-based message logging <<<
  64.  
  65.         (3.1.1) >>> Synchronous (pessimistic) logging <<<
  66.                (3.1.1.1) Borg, Baumbach and Glazer  [SOSP     1983]
  67.            (3.1.1.2) Powell and Presotto        [SOSP     1983]
  68.                (3.1.1.3) Borg et al                 [ACM-TOCS 1989]
  69.      
  70.         (3.1.2) >>> Asynchronous (optimistic) logging <<<
  71.                (3.1.2.1) Strom and Yemini           [ACM-TOCS  1985]
  72.                (3.1.2.2) Sistla and Welch           [SPDC      1989]
  73.                (3.1.2.3) Johnson and Zwaenepoel     [JA        1990]
  74.            (3.1.2.4) Juang and Venkatesan       [ICDCS     1991]
  75.  
  76.    (3.2) >>> Sender-based message logging <<<
  77.     (3.2.1) Johnson and Zwaenepoel              [FTCS      1987]
  78.     (3.2.2) Strom, Bacon and Yemini             [FTCS      1988]
  79.         (3.2.3) Elnozahy and Zwaenepoel             [IEEE-TC   1992]
  80.  
  81.  
  82. SRDSDS   : IEEE Symp. on Reliability in Distributed Software 
  83.        and Database Systems
  84. SRDS     : IEEE Symp. on Reliable Distributed Systems
  85. ICPP     : Intl. Conf. on Parallel Processing
  86. ACM-TOCS : ACM Trans. on Computer Systems
  87. IPL      : Information Processing Letters
  88. IEEE-TSE : IEEE Trans. on Software Engineering
  89. IEEE-TPDS: IEEE Trans. on Parallel and Distributed Systems
  90. IEEE-TC  : IEEE Trans. on Computers
  91. FTCS     : IEEE Fault-Tolerant Computing Symposium
  92. SOSP     : ACM Symp. on Operating Systems Principles
  93. SPDC     : ACM Symp. on Principles of Distributed Computing
  94. JA       : Journal of Algorithms
  95. ICDCS    : IEEE Intl. Conf. on Distributed Computing Systems
  96.  
  97. =====================================================================
  98.  
  99. Thanks,
  100.  
  101. Yi-Min
  102.  
  103. --------------------------------------------------
  104. Yi-Min Wang 
  105. ymwang@crhc.uiuc.edu
  106.  
  107. Center for Reliable and High-Performance Computing
  108. Coordinated Science Laboratory
  109. University of Illinois at Urbana-Champaign
  110.  
  111.     
  112.