분산시스템에서 일관성 유지를 위한 개선된 보우팅 기법

유헌창(Heon-Chang Yu),손진곤(Jin-Gon Shon),황종선(Chong-Sun Hwang) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.1

여러 지역에 분산되어 있는 컴퓨터 시스템들이 각 지역에 저장되어 있는 데이타를 이용하기 위하여 통신망을 이용할 때, 이러한 지역에 이상(failure)이 발생한다면 각 지역에 중복된 데이타들의 가용성이 떨어지고 일관성 유지가 어렵게 된다. 따라서 본 연구는 지역 이상이 발생함으로써 생기는 가용성 및 일관성 문제를 해결하기 위해 개선된 일관성 유지기법을 제안한다. 제안된 기법은 재생성(regeneration)기법을 기반으로 하고 기존의 보우팅(voting) 기법을 보완한 계층적 보우팅 기법을 사용한다. 본 연구는 제안된 기법을 설계하고 이에 대한 성능을 기존의 기법들과 비교 평가한다.

분산시스템에서 보우팅을 위한 계층구조의 변환 방법

유헌창(Heon Chang Yu),손진곤(Jin Gon Shon),황종선(Chong Sun Hwang) 한국정보과학회 1995 정보과학회논문지 Vol.22 No.3

중복데이타를 여러 지역에서 이용하기 위해서는 데이타를 항상 일관성있게 유지해야 한다. 일관성 유지기법 중 정족수 동의기법은 투표를 통해 데이타의 일관성을 유지하는데, 가용성의 향상을 위해 제안된 기법으로 계층적 정족수 동의기법이 있다. 그러나 이 기법은 계층구조로 보우팅이 수행되는데 불완전 계층구조를 형성할 때는 보우팅을 불가능하게 한다. 따라서 이 논문에서는 불완전 계층구조를 완전 계층구조로 변환하여 보우팅을 수행할 수 있도록 하는 방법을 제안한다. It is very important to use replicated data that they must be maintain consistency. Among methods for maintaining consistency, quorum consensus methods maintain consistency of data via voting. Among them, the method to improve an availability is a hierarchical quorum consensus method. In this method, voting is performed in a hierarchical structure. However, it is impossible to perform a voting if the structure is an incomplete structure, i.e., an incomplete tree. In order to perform a voting, we propose a method that converts an incomplete structure to a complete one.

메시지 구간을 이용한 복귀가 없는 파손 회복 기법

김기범(Kibom Kim),황종선(Chong-Sun Hwang),정광식(GwangSik Chung),유헌창(HeonChang Yu) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A

분산 시스템의 성능 향상에 비례하여 결함 포용에 대한 연구의 중요성이 점점 증가하고 있다. 결합 포용에 대한 기존 연구들은 파손 발생시 복귀를 고려한 일관적 전역 상태에 기반한 방법과 메시지를 받은 프로세스가 메시지를 로깅하여 프로세스의 수행을 계속 진행시키는 방법들이 주류를 이루어 왔다. 그러나 이들 방법은 정상 실행시 결함 포용을 보장하기 위한 프로세스들 사이의 동기화와 결함발생시의 일관성 유지에 많은 오버헤드를 유발시킨다. 본 연구에서는 메시지 구간 MI와 송신 프로세스의 메시지를 로깅함으로써 이러한 오버헤드를 감소시키는 파손 회복 기법을 제안한다. 제안하는 회복 알고리즘은 파손 발생시 복귀를 통하여 일관된 전역 상태를 만드는 것이 아니라, 파손이 발생한 프로세스만을 재실행함으로써 일관된 전역 상태가 되도록 하였다. 결국, 제안하는 방법은 정상실행시 검사점을 취하기 위한 프로세스간의 동기화를 위한 오버헤드를 감소시키고 파손 발생시 정상인 프로세스의 복귀를 없앰으로써 프로세스들의 진행의 정도를 높인다.

정보보호를 위한 능력(capability)의 선택적 및 부분적 취소

김영호(Young-Ho Kim),유헌창(Heon-Chang Yu),허용도(Young-Do Her),손진곤(Jin-Gon Shon),황종선(Chong-Sun Hwang) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.2

임의 보호수단중의 하나인 능력(capability)은 소유자의 의사를 존중하며 정교한 제어를 수행하는 방법으로서 널리 쓰이고 있다. 그러나 이러한 능력은 취소의 어려움으로 인해 능력이 지향하는 정교한 제어가 어렵고 소유자의 의사가 반영되지 못하는 문제가 발생한다. 따라서 본 논문에서는 능력의 구현방식중 분산환경에서 사용되는 희소능력(sparse capability)의 선택적 및 부분적 취소를 위한 확장된 능력과 객체테이블을 제안한다. 그리고 제안한 구조를 이용하는 메카니즘에 의한 능력의 선택적 및 부분적 취소과정을 보여 준다.

컴퓨터 네트워크의 통신프로토콜을 위한 통합적 설계방법론

손진곤(Jin-Gon Shon),유헌창(Heon-Chang Yu),황종선(Chong-Sun Hwang) 한국정보과학회 1990 한국정보과학회 학술발표논문집 Vol.17 No.1

본 논문에서는 컴퓨터 네트워크의 통신 프로토콜을 설계하기 위한 통합적 설계 방법론을 제시하였다. 즉, 프로토콜의 내부 설계를 위해서는 Timed Petri Net 모델을 이용하고, 프로토콜의 외부와의 관련성을 표현하기 위해서는 시뮬레이션 분야의 DEVS(Discrete EVent system Specification) 모델을 사용하였다. 또한, 중요한 연구결과로서 Timed Petri Net 모델이 DEVS 모델로 변환될 수 있다는 정리를 얻었는데, 이것은 Timed Petri Net 모델로 설계한 통신 프로토콜을 시뮬레이션하기 위해 또 다른 모델을 설계할 필요없이 곧바로 DEVS 모델로 변환됨으로써 쉽게 시뮬레이션 기법으로 분석할 수 있는 가능성을 제공한다.

동기적 검사점 기법에서 불필요한 복귀를 회피하기 위한 쓰레기 처리 기법

정광식(Kwang Sik Chung),유헌창(Heon-Chang Yu),이원규(Won-Gyu Lee),이성훈(Seong Hoon Lee),황종선(Chong-Sun Hwang) 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.5·6

This paper presents a garbage collection protocol for checkpoints and message logs which are saved on the stable storage or volatile storage for fault tolerancy. The previous works of garbage collections in coordinated checkpointing protocol delete all the checkpoints except for the last checkpoints on each processes. But implemented on top of reliable communication protocol like as TCP/IP, rollback recovery protocol based on only last checkpoints makes sympathetic rollback. We show that the old checkpoints or message logs except for the last checkpoints have to be preserved in order to replay the lost messages. And we define the conditions for garbage collection of checkpoints and message logs for lost messages and present the garbage collection algorithm for checkpoints and message logs in coordinated checkpointing protocol. Since the proposed algorithm uses process information for lost message piggybacked with messages, the additional messages for garbage collection is not required The proposed garbage collection algorithm makes 'the lazy garbage collectioneffect', because relying on the piggybacked checkpoint information in send/receive message. But ‘the lazy garbage collection effect’ does not break the consistency of the whole systems. 이 논문은 동기적 검사점 기법에서 결함 포용을 목적으로 불안전 저장 장치(volatile storage)에 저장되는 메시지 로그와 안전 저장 장치에 저장되는 검사점의 쓰레기 처리 기법을 제안한다 . 기존의 동기적 검사점 기법을 기반으로 한 결함 포용 정보 쓰레기 처리 기법은 가장 최근의 검사점을 제외한 모든 결함 정보를 쓰레기 처리하였다. 하지만 TCP/IP와 같은 신뢰적 통신 기법을 기반으로 한 동기적 검사점 기법이 가장 최근의 검사점만을 복귀 회복 기법에서 사용한다면, 손실 메시지(lost message)로 인한 불필요한 복귀(sympathetic rollback)가 발생된다. 이 논문은 동기적 검사점 기법에서 손실 메시지로 인한 불필요한 복귀 문제를 해결하기 위해 각 프로세스가 동기화된 가장 최근의 검사점외에 검사점이나 메시지 로그를 유지해야 한다는 것을 보였다. 또한 손실 메시지로 인한 불필요한 복귀 문제의 해결을 위해 관리되어야 하는 검사점이나 메시지 로그가 쓰레기 처리되어지기 위해 필요한 조건을 새롭게 정의하며, 이 정의를 기반으로 한 검사점과 메시지 로그의 쓰레기 처리 알고리즘을 제안한다. 제시된 조건을 기반으로 한 검사점과 메시지 로그의 쓰레기 처리는 송수신 메시지에 부가된 손실 메시지 관련 프로세스 정보를 이용하므로 쓰레기 처리를 위한 부가적인 메시지를 발생시키지 않는다. 제안된 기법은 손실 메시지 관련 정보가 부가된 메시지가 송수신되기 전까지 쓰레기 처리가 지연되는 ‘지연 쓰레기 처리 현상(lazy garbage collection)’을 발생시킨다. 하지만 ‘지연 쓰레기 처리 현상’은 분산 시스템의 일관성을 위배하지 않는다.

통신 패턴에 기반한 메시지 로깅

김기범(Kibom Kim),유헌창(HeonChang Yu),안진호(JinHo Ahn),황종선(Chong Sun Hwang) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.2Ⅲ

메시지로깅을 이용한 기존의 메시지 로깅기법에서는 모든 메시지에 대한 처리를 동일하게 수행하였다. 반면, 이 논문에서는 통신 패턴에 대한 연구를 바탕으로 통신시에 발생하는 중요한 성질인 통신국부성을 발견하였다. 이를 기반으로 프로세스의 통신 집합을 유지하도록 함으로써 결함 발생 후 모든 프로세스에게 도움을 요청하는 메시지를 보는 것이 아니라 오직 자신과 통신을 수행했던 프로세스에게만 메시지를 보내는 기법을 제안한다.

문서 편집을 위한 모음 중심 스트링 탐색 방법

정광식(Gwang-Sik Chung),유헌창(Heon-Chang Yu),황종선(Chong-Sun Hwang) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.1

컴퓨터를 이용한 문서 편집의 기능 중 문장내에서 원하는 스트림을 찾는 것으로 스트링 탐색(string searching) 방법이 있다.본 연구에서 제안한 방법은 탐색의 효율을 높이기 위하여 스트링의 구성특성, 즉 스트링내의 모음의 발생빈도를 고려하여 스트링 탐색을 수행한다. 이에 따라 최악의 경우와 최선의 경우의 차이가 없이 패턴의 길이나 특성에 영향을 받지 않고 문장내에 패턴의 위치에 의해서만 수행시간이 결정되는 특성을 보이는 알고리즘을 제안한다.

접근제어에서 다단계 보안 개념의 적용을 위한 확장된 능력

안미림(Mirim Ahn),유헌창(Hoen-chang Yoo),황종선(Chong-sun Hwang) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.1

능력(Capability)은 공용되는 자원의 보호를 위한 임의보호방식 중 하나로 객체 소유자 중심의 접근제어방식이다. 이 방법은 접근권한 부여에 있어서 접근주체의 소유자 의사만을 존중하고 객체의 내용은 전혀 고려하지 않는 단점이 있다. 따라서 이 논문에서는 주체와 객체의 보안 등급에 따라서 접근이 제어되는 다단계 보안 개념을 능력 기반 시스템에 적용하기 위한 확장된 능력을 제안하였다. 또한 전파상황에서 보안정책에 맞는 객체에 대한 접근제어 부여 알고리즘을 제안하였다.

이동 클라이언트/서버 컴퓨팅 환경에서의 캐싱 및 동시성 제어

이상근(Sang-Keun Lee),황종선(Chong-Sun Hwang),이원규(Won-Gyu Lee),유헌창(Heon-Chang Yu) 한국정보과학회 1999 정보과학회논문지(B) Vol.26 No.8

이동 컴퓨팅 환경에서 자주 접근하는 데이터에 대한 캐싱은 무선 채널의 좁은 대역폭에서 경쟁을 줄일 수 있는 유용한 기술이다. 그러나, 트랜잭션 캐시 일관성을 지원하는 전통적인 클라이언트/서버 전략은 클라이언트와 서버간에 많은 양의 통신을 필요로 하기 때문에 이동 클라이언트/서버 컴퓨팅 환경에서는 적절하지 않다. 본 논문에서는 브로드캐스트-기반 캐시 모효화 정책을 사용하면서 트랜잭션 캐시 일관성을 지원하는 OCC-UTS (Optimistic Concurrency Control with Update TimeStamp) 프로토콜을 제안한다. 접근한 데이터에 대한 일관성 검사 및 완료 프로토콜은 캐시 모효화 과정의 내부 과정으로 완전 분산 형태로 효율적으로 구현되며, 일관성 체크의 대부분이 이동 클라이언트에서 수행된다. 또한, 분석 모델에 기반한 성능 비교를 통해, 본 논문에서 제안하는 OCC-UTS 프로토콜이 다른 경쟁 프로토콜보다 높은 트랜잭션 처리율을 얻으며, 데이터 항목을 자주 접근하면 할수록 지역 캐시를 사용하는 OCC-UTS 프로토콜이 더 효율적임을 보인다. 이동 클라이언트의 접속 단절에 대해서는 무효화 브로드캐스트 윈도우를 크게 하여 접속 단절에 적절히 대처할 수 있다. In a mobile computing environment, caching of frequently accessed data has been shown to be a useful technique for reducing contention on the narrow bandwidth of the wireless channels. However, the traditional client/server strategies for supporting transactional cache consistency that require extensive communications between a client and a server are not appropriate in a mobile client/server computing environment. In this paper, we propose a new protocol, called OCC-UTS (Optimisitic Concurrency Control with Update TimeStamp), to support transactional cache consistency in a mobile client/server computing environment by utilizing the broadcast-based solutions for the problem of invalidating caches. The consistency check on accessed data and the commitment protocol are implemented in a truly distributed fashion as an integral part of cache invalidation process, with most burden of consistency check being downloaded to mobile clients. Also, our experiments based on an analytical model substantiate the basic idea and study the performance characteristics. Experimental results show that OCC-UTS protocol without local cache outperforms other competitor protocol, and the more frequent a mobile client accesses data items the more efficient OCC-UTS protocol with local cache is. With respect to disconnection, the tolerance to disconnection is improved if the invalidation broadcast window size is extended.