earticle

영어

Dijkstra introduced to computer science the notion of Self-Stabilization in the context of distributed system. He defined a system as Self-Stabilizing when "regardless of initial state, it is guaranteed to arrived at a legitimate state in a finite number of steps". A system which is not Self-Stabilizing may stay in an illegitimate forever. Dijkstra's notion of Self-Stabilization, which originally had a very narrow scope of application, is proving to encompass a formal and unified approach to fault tolerance under a model of transient failures for distributed system. In this paper, we define Self-Stabilization, examine its significance in the context of fault-containment. Furthermore, the problem of locating center and median of graphs has a variety of applications in the areas of transportation and communication in distributed system. This paper presents simple Self-Stabilizing algorithm for locating center and median of graphs and the correctness of the algorithm is proven.

한국어

Dijkstra가 분산시스템과 관련한 자율안정의 개념을 컴퓨터 과학에 처음 도입하였다. 그는 시스템이 초기 상태와 관계없이 유한한 수의 과정 안에 합리적인 상태에 도달한다는 것이 보증될 때 이러한 시스템을 “자율안정”이라고 정의하였다. 자율안정이 아닌 시스템은 불합리한 상태에 머무르게 된다. Dijkstra의 자율안정의 개념은, 처음에는 매우 협의의 단순한 응용이었는데, 분산시스템 상의 일시적인 결함 모델 하의 결함 허용으로의 정형적이며 일체화된 접근을 내포함을 증명하게 되었다. 본 논문에서는 자율 안정을 정의하고, 결함 억제와 관련해서 자율안정의 의미를 검사한다. 더욱이, 그래프의 중심과 중앙을 찾는 문제는 분산 환경의 통신 분야와 전송 분야에의 다양한 응용을 가진다. 본 논문은 그래프의 중심과 중앙을 찾기 위한 자율 안정 알고리즘을 보이고, 그 알고리즘의 정확성을 검증한다.