A distributed system can be viewed as a set of processes that share many types of resources, such as processors, memory cells, buses, and printers. Emerging network technologies require efficient distributed processing ability. A distributed algorithm in distributed system deals with how to make the computers connected together work well. Main focus of distributed algorithm is mutual exclusion problem that means many shared resources must be accessed in a mutually exclusive manner.
This thesis gives a new quorum-based distributed group mutual exclusion algorithm. In the group mutual exclusion problem, multiple processes can enter critical section at the same time if they belong to the same group. The former quorum-based group mutual exclusion algorithm has a case when two processes cannot enter critical section at the same time even if they can do so. We call the above situation as unnecessary blocking. We give a new algorithm which prevents unnecessary blocking. Also, in this thesis, we present a method to control the access to a secure database based on group mutual exclusion algorithm using quorum systems. The security of algorithm is based on the secret sharing scheme. The main goal of our algorithm is to integrate security with distributed algorithm.
컴퓨터 기술의 발달과 인터넷 보급의 확산은 전통적인 중앙집중적 네트워크 관리환경에서 분산 컴퓨팅 환경으로 변화를 이끌고 있다. 분산 시스템은 프로세서나 메모리 셀, 버스, 프린터등과 같은 많은 타입의 리소스를 공유하는 프로세스 집합들로 구성된다. 분산시스템의 분산알고리즘은 많은 분산된 컴퓨터들이 어떻게 하면 협력적으로 작업을 수행할 수 있는지를 목표로 하고 있다. 현존하는 많은 분산알고리즘은 리소스를 공유하는 프로세스간의 서로 충돌이 이루어지는 상호배제문제를 해결하는데 초점을 맞추고 있다. 특히 최근에는 그룹단위의 상호배제 문제의 연구가 이루어지고 있다. 그룹 상호배제는 하나의 리소스를 같은 그룹내의 모든 프로세스에 의해서 공유되도록 할 수 있는 상호배제의 일반화이다. 하지만, 다른 그룹의 프로세스들은 상호 배타적인 방법으로 하나의 리소스를 사용하도록 요청된다. 즉, 다른 그룹의 프로세스들은 이미 임계영역에 있는 프로세스가 그 리소스에 대한 사용이 끝난 후 임계영역에 들어갈 수 있다. 그룹상호배제를 통해 효율성을 증가시킬 수 있는 장점이 있다.
분산된 환경에서 프로세스간의 충돌을 막고 효율적으로 컴퓨팅이 가능하도록 하는 것이 중요하나, 기본적인 인터넷의 개방성과 분산된 환경은 전송되는 정보에 대한 안전성에 큰 취약성을 노출한다. 따라서, 분산알고리즘의 설계 시 상호배제를 통한 프로세스간의 효율성과 함께 안전성을 보장하는 것은 가치 있는 일이다.
이러한 목적을 달성하기 위한 방법론으로 본 논문에서는, 우선 기존의 제안된 그룹상호배제 알고리즘의 문제점을 소개하고, 그런 문제점을 해결하는 새로운 알고리즘을 제안한다. 두번째로, 제안된 알고리즘을 기반으로 하여 보안성을 고려한 안전한 쿼럼 기반의 분산알고리즘을 제안한다. 제안되는 알고리즘은 분산알고리즘을 기반으로 하기 때문에 기본적인 요구사항을 만족하며, 또한 보안요구사항을 동시에 만족한다.
