임의의 생성트리를 구축하는 자율 안정 알고리즘 = A self-stabilizing algorithm to build an arbitrary spanning tree

국문 초록 (Abstract)

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

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 계산 모델
• 3. 생성트리에 대한 자율안정 알고리즘
• 4. 알고리즘의 정확성
• 5. 결론
• 참고문헌

참고문헌 (Reference)

• 1 G. M. Brown, "Token systems self-stabilize" 38 (38): 845-852, 1989
• 2 M. Gouda, "Stabilizing union" 5 (5): 171-175, 1990
• 3 Z. Collins, "Self-stabilizing depth-first search" 49 : 287-301, 1994
• 4 P. Chaudhuri, "Algorithm for finding and updating minimum depth spanning trees" 87 : 171-183, 1995
• 5 N. S. Chen, "A self-stabilizing depth-first search" Inform. Process. Lett 147-151, 1991
• 6 S. Sur, "A self stabilizing distributed algorithm for for BFS spanning trees of a symmetric graph" 2 : 171-179, 1992
• 7 S. T. Huang, "A self stabilizing algorithm for constructing BFS" 41 : 109-117, 1992
• 8 E. W. Dijkstra, "A belated proof of self-stabilizing" 1 (1): 5-6, 1986