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

목차

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

키워드

저자

• 이충세 [ Chung Sei Rhee | 충북대학교 전자정보대학 컴퓨터공학부 ]

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  보안공학연구논문지 [Journal of Security Engineering]

• 간기

  계간

• pISSN

  1738-7531

• 수록기간

  2005~2017

• 십진분류

  KDC 505 DDC 605