earticle

영어

In 1974 Dijkstra introduced 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. Self-stabilizing algorithm is important topic in communication and security area. A system which is not self-stabilizing may stay in an illegitimate forever. In this paper, we propose a simple self-stabilizing distributed algorithm that create an arbitrary spanning tree in a connected graph. We develop a new technique without using a bounded function which is customary method. The new approach is simple and can be applied to other self-stabilizing algorithm.

한국어

1974년에 Dijkstra는 분산시스템에 적용하는 자율 안정(self-stabilizing) 알고리즘의 개념을 처음 도입하였다. Dijkstra는 초기상태에 관계없이 유한한 과정 안에 합리적인 상태로 시스템이 도달을 수 있는 것을 보증할 경우 이를 자율안정 알고리즘이라 정의하였다. 자율안정 알고리즘은 통신이나 보안분야에 많이 응용되고 있다. 이 논문에서는 연결된 그래프에서 임의의 생성트리를 유지하는 자율 안정 분산 알고리즘을 제안한다. 알고리즘의 정확성을 증명을 위하여 일반적으로 사용하는 경계값을 가진 함수 대신에 새로운 방법을 제시한다. 이러한 알고리즘은 시스템이 유한한 시간 내에 안정화를 취할 수 있도록 보증해 준다. 새로운 기법은 또한 간단하고 다른 자율 안정 알고리즘의 정확성을 증명하는데도 사용될 수 있을 것으로 기대된다.