분산 시스템에서 개선된 O(logN) 상호배제 알고리즘 제안 = AN IMPROVED O(logN) MUTUAL EXCLUSION ALGORITHM FOR DISTRIBUTED SYSTEMS

국문 초록 (Abstract)

본 논문은 분산 시스템에서 수행시간이 O(logN)으로 개선된 토큰 중심의 상호배제 알고리즘을 제안하였다. 이 알고리즘에서, 논리적 트리는 완전 연결(fully connected) 네트워크를 유지하며, 루트(Root)는 메세지 전송이 없을때 병행 요청 사이트들 가운데 토큰을 갖는 마지막 사이트이다. 사이트가 상호배제를 필요로 할 때, 그사이트는 토큰을 갖을 수 있는 사이트에 요청 메세지를 보내는 작업을 요청 메세지가 Root에 도착할 때까지 계속해 나간다. 따라서, 토큰을 탐색하는 메세지의 수는 Root에 도달하는 길(path)의 사이트 수에 비례한다. 토큰의 탐색속도를 향상시키기 위하여 알고리즘은 논리적 트리의 높이(hight)를 줄인다. 알고리즘의 메세지 수행시간은 N이 사이트의 수 일때 가벼운 traffic에서는 O(logN)이고, 복잡한 traffic에서는 3개를 감소한다. 본 알고리즘의 중요한 특성은 분산된 큐자료 구조를 사용하며, 이 구조는 토큰으로 자료 구조를 간단히 할 뿐 아니라 타임스탬프나 무한 수열의 사용을 제거하므로 신뢰도를 높여준다.

다국어 초록 (Multilingual Abstract)

In this paper, we present an O(logN) token-based mutual exclusion algorithm for distributed systems. In the algorithm, a logical tree is maintained in a fully connected network, and the root is the last site to get the token among the current requesting sites when no message is in transmission. When a site invokes mutual exclusion, it send its request to the site possibly holding the token. The request is continuously forwarded until it arrives at the root. Therefore, the number of messages for the search of the token is proportional to the number of sites on the path leading to the root. To speed up the research for the token, the algorithm reduces the hight of the logical tree. The message complexity of the algorithm is O(logN) in light traffic, where N is the number of sites, and is reduced to three in the heavy traffic. An interesting characteristic of the algorithm is the use of distributed queue data structure. The distributed queue data structure simplifies the data structure in the token, dispenses with the use of unbounded sequence numbers or timestamps, and provides a high degree of reliability.