A Fault Tolerant Mutual Exclusion Algorithm in Distributed Systems
Sun-Joon Yu, Yoon Kim · Journal of the Korea Entertainment Industry Association · 2009
상호배제(mutual exclusion)는 분산시스템에서 근간이 되는 기술의 하나로 한 번에 오직 하나의 프로세스만이 임계구역에 접근하도록 제한하여야 하는 원칙에 따라 임계구역은 상호배제의 대상이 된다. 지금까지 분산시스템에서의 상호배제를 구현하기 위한 많은 알고리즘이 제안되어 왔다. Vijay K. Garg가 제안한 분산 토큰기반 상호배제 알고리즘 역시 그중의 하나인데 이는 fault-free를 전제로 한 알고리즘이다. 이러한 fault-free 환경에서는 Garg의 알고리즘이 아무런 문제없이 동작한다. 하지만 토큰을 보유한 프로세스 또는 토큰을 요청한 프로세스에서 결함이 발생한 경우에는 전체 시스템에서 토큰이 손실되어 시스템의 동작이 멈출 수밖에 없다. 이 논문에서는 Garg알고리즘이 결함허용시스템(fault-tolerant system)에서도 아무런 문제없이 동작할 수 있도록 이를 수정한 알고리즘을 제안하고 있다. 이 알고리즘에서는 시스템의 결함으로 인해 토큰의 손실이 발생할 경우에 주어진 시간(timeout) 이후 이를 즉각 감지하여 새로운 토큰을 생성함으로써 시스템 전반에 야기될 수 있는 치명적인 문제의 발생을 방지할 수 있도록 기존 알고리즘의 일부 프로시저를 수정하거나 새로운 프로시저를 삽입하였다.