결함을 제한하는 자율안정 알고리즘을 이용한 중심과 반경을 찾는 시스템 = A fault-containment self-stabilizing algorithm to find a center and radius

국문 초록 (Abstract)

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

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 자율안정의 정의
• 2.1 Dijkstra의 모델
• 2.2 정형화된 네트워크와 비정형화 된 네트워크
• 2.3 Dijkstra의 해
• 3. 결함을 제한하는 자율안정 알고리즘
• 3.1 자율안정 알고리즘의 제한성
• 3.2 결함을 제한하는 자율안정 알고리즘
• 3.3 결함제한의 문제점
• 4. 중심과 중앙을 찾기 위한 자율안정 알고리즘
• 4.1 중심과 중앙을 찾는 알고리즘
• 4.2 알고리즘의 정확성
• 4.3 알고리즘의 유한성
• 5. 결론
• 참고 문헌

참고문헌 (Reference)

1 L.Lamport, "Unsolved problems, Solved problems, and non-problems in concurrency" 1984

2 E.W.Dijkstra, "Self-Stabilizing Systems in spite of Distributed Control" 17 (17): 643-644, 1974

3 M.Flatebo,A.K.Datta, "Self-Stabilization in Distributed Systems"

4 M.Schneider, "Self-Stabilization"

5 Z.Shi, "Handbook on Theoretical and Algorithmic Aspects of Sensor/ Ad-Hoc Wireless and Peer-to-Peer Networks" Auerbach Publications 393-402, 2005

6 S. T. Hedetniemi, "Fault Tolerant Distributed Coloring Algorithms That Stabilize in Linear Time" 2002

7 W.Goddard, "An anonymous self-stabilizing algorithm for 1-maximal matching in trees" 2006