비동기적 검사점 기록을 고려한저 비용 인과적 메시지 로깅 기반 회복 알고리즘
Low-Cost Causal Message Logging based Recovery AlgorithmConsidering Asynchronous Checkpointing
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
인과적 메시지 로깅을 위한 기존 회복 알고리즘들에 비해, Elnozahy가 제안한 회복 알고리즘은 안전한 저장소 접근횟수를 매우 줄이고, 회복과정을 수행하는 동안 살아있는 프로세스들이 자신의 계산을 계속해서 수행할 수 있도록 한다. 그러나, 인과적 메시지 로깅 기법이 비동기적 검사점 기록 기법과 함께 사용된다면, 동시적 고장들이 발생하는 경우 이 알고리즘 수행 후 전체 시스템 상태가 일관적이지 못하게 될 수 있다. 본 논문에서는 이러한 일관적이지 못한 경우들을 보여주고, 이러한 문제점을 해결하는 인과적 메시지 로깅을 위한 저 비용의 회복 알고리즘을 제안한다. 시스템 일관성을 보장하기 위해, 이 알고리즘은 회복 리더가 모든 살아있는 프로세스들뿐만 아니라 다른 회복 프로세스들로부터 회복정보를 얻을 수 있도록 한다. 또한, 제안된 알고리즘은 Elnozahy 회복 알고리즘에 비해 어떠한 부가적인 메시지도 요구하지 않으며, 메시지 피기백에 의해 발생되는 제안된 알고리즘의 부가적인 비용이 매우 낮다. 이를 입증하기 위해, 시뮬레이션 결과는 제안된 알고리즘이 Elnozahy 알고리즘에 비해 회복정보 수집시간을 단지 1.0%～2.1% 정도로 증가시킴을 보여준다.
Abstract
Compared with the previous recovery algorithms for causal message logging, Elnozahy's recovery algorithm considerably reduces the number of stable storage accesses and enables live processes to execute their computations continuously while performing its recovery procedure. However, if causal message logging is used with asynchronous checkpointing, the state of the system may be inconsistent after having executed this algorithm in case of concurrent failures. In this paper, we show these inconsistent cases and propose a low-cost recovery algorithm for causal messge logging to solve the problem. To ensure the system consistency, this algorithm allows the recovery leader to obtain recovery information from not only the live processes, but also the other recovering processes. Also, the proposed algorithm requires no extra message compared with Elnozahy's one and its additional overhead incurred by message piggybacking is significantly low. To demonstrate this, simulation results show that the first only increases about 1.0%～2.1% of the recovery information collection time compared with the latter.
참고문헌 (15)
- "Nonblocking and Orphan-Free Message Logging Protocols", pp.145~154 (1993)
- "Parsec : A Parallel Simulation Environ- ments for Complex Systems", pp.77~85 (1998)
- "Scalable Causal Message Logging for Wide-Area Environments", 15(3), pp.873~889 (2003)
- "a Fault Tolerant MPI for Volatile Nodes based on Pessimistic Sender Based Message Logging" (2003)
- "Distributed Snapshots: Determining Global States of Distributed Systems", 3(1), pp.63~75 (1985)
- "On the Relevance of Communication Costs of Rollback Recovery Protocols", pp.74~79 (1995)
- "A Survey of Rollback-Recovery Protocols in Message- Passing Systems", 34(3), pp.375~408 (2002)
- "Manetho: Transparent rollback-recovery with low overhead, limited rollback and fast output commit", 41, pp.526~531 (1992)
- "On the impossibility of non-blocking consistent causal recovery", E83-D(2), pp.291~294 (2000)
- "A non-blocking recovery algorithm for causal message logging", pp.3~9 (1998)
- M. L. Powell, "Publishing:A reliable broadcast communication mechanism", pp.100~109 (1983)
- R. D. Schlichting, "Fail-stop processors: an approach to designing fault-tolerant distributed computing systems", 1, pp.222~238 (1985)
- R. B. Strom, "Optimistic recovery in distributed systems", 3, pp.204~226 (1985)
- S. Venkatesan, "Optimistic crash recovery without changing application messages", 8, pp.263~271 (1997)
- B. Yao, "Message Logging in Mobile Computing", pp.14~19 (1999)