Journal of KIISE:Computer Systems and Theory (한국정보과학회논문지:시스템및이론)

Korean Institute of Information Scientists and Engineers (한국정보과학회)
권호 표지

A Garbage Collection of Message Logs without Additional Messages on Causal Message Logging Protocol

인과적 메시지 로깅 기법에서 부가적 메시지 교환 없는 메시지 로그 쓰레기 처리 기법

  • 정광식 (고려대학교 컴퓨터학과) ;
  • 유헌창 (고려대학교 컴퓨터교육과) ;
  • 백맹순 (고려대학교 컴퓨터학과) ;
  • 손진곤 (한국방송통신대학교 컴퓨터과학과) ;
  • 황종선 (고려대학교 컴퓨터학과)
  • Published : 2001.08.01
Download PDF
⟨ Previous Next ⟩

Abstract

이 논문은 인과적 메시지 로깅 기법에서 결함 포용을 목적으로 안전 저장 장치(stable storage)에 저장되는 메시지 내용 로그와 메시지 순서 로그의 쓰레기 처리 기법을 제안한다. 기존의 인과적 메시지 로깅을 기반으로 한 메시지 로그 쓰레기 처리 기법은 메시지 순서 로그의 쓰레기만을 처리하였다. 메시지 내용 로그는 불필요한 복귀를 피하기 위해 유지해야 하며, 메시지내용 로그의 쓰레기 처리를 위해서는 부가적인 메시지를 필요로 하였다. 이 논문은 인과적 메시지 로깅 기법에서 메시지 내용 로그와 메시지 순서 로그가 쓰레기 처리되어지기 위해 필요한 조건을 새롭게 정의하며, 이 정의를 기반으로 한 메시지 내용 로그와 메시지 순서 로그의 쓰레기 처리 알고리즘을 제안한다. 제시된 조건을 기반으로 한 메시지 내용 로그와 메시지 순서 로그의 쓰레기 처리는 송수신 메시지에 부가된 MAG(Modified Antecednce Graph)를 이용하므로 쓰레기 처리를 위한 부가적인 메시지를 발생시키지 않는다. 하지만 제안된 기법은 일반 메시지가 송수신되기 전까지 쓰레기 처리가 지연되는 '지연 쓰레기 처리 현상(lazy garbage collection)'을 발생시킨다. 하지만 '지연 쓰레기 처리 현상'은 분산 시스템의 일관성을 위배하지 않으며, 쓰레기 처리를 위한 부가적인 메시지 교환을 필요로 하지 않는다.

Keywords

References

  1. R. Koo, S. Toueg. 'Checkpoint and Rollback-Recovery for Distributed Systems,' IEEE Trans. S. E., Vol. 13, pp.23-31, Jan. 1987
  2. Sean W. Smith, et al, 'Completely Asynchronous Optimistic Recovery with Minimal Rollbacks,' Proc. of IEEE FTCS-25, 1995, pp361-370
  3. Sylvain R. Y. Louboutin, Vinny Cahill, 'On Thorough Garbage Collection in distributed Systems,' IEEE, pp. 576-581, 1998
  4. M. V. Sreenivas, Subhash Bhalla, 'Garbage Collection in Message Passing Distributed Systems,' IEEE, pp. 213-218, 1995
  5. Lorenzo Alvisi, Keith Marzullo. 'Message Logging: Optimistic, Causal and Optimal,' In Pro IEEE Int. Conf. Distributed Computing Systems, pages 229-236, March 1995
  6. Lorenzo Alvisi, Bruce Hoppe, Keith Marzullo. 'Nonblocking and orphan-free message logging protocols,' In Proceedings of 23rd Fault-Tolerant Computing Symposium, pages 145-154, June 1993 https://doi.org/10.1109/FTCS.1993.627318
  7. E. L. Elnozahy, W. Zwanepoel. 'Manetho: Transparent rollback-recovery with low overhead,' limited rollback and fast output commit. IEEE Transactions on Computers, 41(5):526-531, March 1992 https://doi.org/10.1109/12.142678
  8. Mootaz Elnozahy, Lorenzo Alvisi, Yi-Min Wang, David B. Johnson. 'A Survey of RollbackRecovery Protocols in Message-Passing Systems,' Technical Report CMU-CS-96-181. Department of Computer Science. Carnegie Mellon University. Sept. 1996
  9. Jian Xu, Robert H. B. Netzer, Milon Mackey, 'Sender-based Message Logging for Reducing Rollback Propagation,' IEEE, pp.602-609, 1995
  10. D. Manivannan, Mukesh Singhal, 'A Low-Overhead Recovery Technique Using Quasi-Synchronous Checkpointing,' Proceedings of the 16th ICDCS, pp100-107. 1996
  11. D. B. Johnson, W. Zwaenepoel, 'Sender-based Message Logging,' In Digest of papers:17 Annual International Symposium on Fault-Tolerant Computing, 14-19, IEEE Computer Society, June 1987