In this thesis, we investigate problems of distributed fault-tolerant method for a faulty hypercube and replicated database. The fault-tolerance can be provided by a combination of established hardware fault-tolerance and the fault-tolerant software techniques. We are mainly concerned with the fault-tolerant software techniques.
We consider two distributed fault-tolerant methods in this thesis: One is a distributed shortest path search algorithm and an efficient fault-tolerant routing algorithm in the presence of faulty components in a hypercube. The hypercube computer system is a well known parallel processing system because of their structural regularity and powerful embedding properties.
Our distributed shortest path search algorithm overcomes the drawbacks of the depth-first and the best-first search methods, and always finds a shortest path in the presence of faults in hypercubes. Also, we show that the distributed shortest path search algorithm is efficiently applied to a fault-tolerant routing in faulty hypercubes with static faults. The proposed fault-tolerant routing algorithm attempts to route every message to its destination via a shortest path in the presence of an arbitrary number of faulty components. To reduce the amount of information at each node required for the shortest path routing, the unnecessary propagation of information on faulty components should be avoided. Therefore, when only backtracking is enforced at a node, all network information of that node are added to a backtracking message.
Another is a replicated data concurrency control protocol for a replicated database. A replicated database is a distributed database in which multiple copies of some data items are stored redundantly at multiple sites. The replcation of a data is used for improving the availability and read performance of data.
We present the replicated data concurrency control algorithm based on the dynamic voting scheme in the presence of site and network failures. In voting scheme, each copy of a replicated data item is assigned number of votes. To read a data item, a user transaction has to gain a read quorum of votes. Also, to write a data item, a write quorum of vote is needed. However, the voting scheme is inefficient in that a read transaction must access multiple copies for reading a data item. This will degrade the performance since read operations occur more than write operations in most applications.
By allowing different weights to each copy involved in each update operation the proposed algorithm exhibits high read performance in that, in normal cases where a specific failure (a current primary site is isolated because of site or network failures) does not occur, the number of copies accessed for each read operation in fixed to 2 regardless a number of copies.
Comparing with existing dynamic voting schemes, it improves read efficiency of the algorithm. Also, the algorithm preserves high availability in the presence of site of network failures. It is shown that the proposed algorithm has the same availability as that of dynamic voting with linearly ordered copies (dynamic-linear) algorithm [Jajo 90]. Also, an extension of the proposed algorithm which has the same availability as that of Jajodia's hybird scheme [Jajo 89] is presented. Also, we propose a distributed mutual exclusion that uses weak copy consistency to create mutual exclusion in a distributed computer system. The weak copy consistency is deduced from the uncertainty of state which occurs due to the finite and unpredictable communication delays in a distributed environment. Also, the algorithm correlates outdated state information to current state. The average number of messages to enter critical section in the algorithm is n/2 to n messages where is n is the number of sites. We show that the algorithm achieves mutual exclusion and the fairness and liveness of the algorithm is proven. We study the performance of the algorithm by simulation.
본 논문에서는 고장이 허용되는 하이퍼큐브 컴퓨터 시스템과 중복 데이타베이스 시스템에서 고장을 극복하여 시스템의 높은 신뢰도와 높은 이용도를 유지시키는 두 가지 분산 처리 기법에 대하여 연구하였다. 이러한 분산 처리 기법은 하드웨어와 소프트웨어의 결합으로 이루어진다. 그러나, 본 논문의 주 관심은 분산 처리 기법에서의 소프트웨어 이다.
첫번째 분산 처리 기법으로는 병렬 컴퓨터 시스템으로 잘 알려져있는 하이퍼큐브 컴퓨터 시스템에서 노드 컴퓨터의 통신 링크 혹은 노드 컴퓨터의 고장이 존재하는 데에도 불구하고 임의 송신 노드와 수신 노드 사이에 최단 거리를 찾는 탐색 알고리즘(Distributed Shortest Path Search Algorithm) 을 제시하였다. 이 알고리즘은 고장이 있는 하이퍼큐브에서 기존의 Depth-first 그리고 Best-first search 알고리즘의 단점을 보완한 것이다. 또한, 이 분산 최단 거리 탐색 알고리즘은 고장 통신 링크 혹은 고장 노드 컴퓨터의 갯수에 관계없이 송신 노드와 수신 노드 사이에 연결 링크가 존재하기만 하면 반드시 최단 거리를 찾는다. 이 알고리즘의 성능이 평균적으로 우수함을 보였다. 또한, 수학적 분석을 통하여 n-차원 하이퍼큐브 에서 거리가 n 인 두 노드사이에 최적 최단거리를 찾을 확률이 매우 높음을 증명하였다. 그리고, 이 최단 거리 탐색 알고리즘을 이용하여 고장이 있는 하이퍼큐브에서 메시지를 라우팅 (Routing) 하는 고장 허용 라우팅 알고리즘 (Efficient Fault-Tolerant Routing Algorithm) 을 제시하고 그 성능을 시뮬레이션으로 보였다. 효율적으로 메시지를 라우팅 하기 위하여 각 노드 컴퓨터가 관리하는 고장에 대한 정보량도 전체의 네트웍에 대한 정보를 요구하는 다른 알고리즘보다 매우 적다는 것을 보였다. 특히 임의 송신 노드와 수신 노드 사이에 메시지가 많은 경우 고장 허용 라우팅 알고리즘은 매우 효율적이다.
두 번째 분산 처리 기법은 분산 처리 시스템인 중복 데이타베이스 (Replicated Database)에서 중복 데이타 동시 제어 알고리즘 (Replicated Data Concurrency Algorithm)을 제시하였다. 중복 데이타베이스는 하나의 데이타를 분산 되어 있는 서로 다른 여러 컴퓨터들에 복사한 분산 데이타베이스 이다. 이 중복 데이타 베이스의 장점은 시스템의 높은 이용도를 제공하고 데이타를 효율적으로 임의 컴퓨터에서 읽을 수 있다는 것이다. 그러나, 중복 데이타베이스 시스템에서 컴퓨터들의 고장과 통신 링크의 고장으로 인한 네트웍의 분열 (Partition) 등은 중복 데이타베이스의 효율적인 사용을 어렵게한다. 즉, 고장이 있는 중복 데이타베이스에서 중복 데이타의 모든 값을 일정하게 유지하는 것은 어렵다. 이러한 중복데이타의 일관성 (Consistency)을 잘 유지하는 대표적인 방법이 보팅 (Voting) 방법이다. 보팅은 사용자의 읽기 요구(Read request)와 쓰기 요구(Write request)에 대하여 네트웍의 분열이 있을 때 정족수 (Quorum) 를 얻은 분열이 사용자의 요구를 받아들인다. 중복 데이타베이스에 속한 한 컴퓨터에 읽기 요구가 받아지면 이 컴퓨터는 주변의 다른 컴퓨터들과 통신을 통하여 투표수 (Vote) 를 모아 이 컴퓨터가 속한 분열이 정족수를 갖는 지를 판단 한다. 만약, 정족수를 얻었다면 사용자의 요구를 받아 수행한다. 그렇지 않다면, 사용자의 요구를 거절한다. 이 처럼 데이타를 읽을 때 마다 정족수를 통신을 통하여 얻으므로서 생기는 통신 오버헤드(Overhead)를 줄이기 위하여 제안된 알고리즘은 다이나믹보팅 (Dynamic Voting) 을 기반으로 각 컴퓨터의 활당된 투표수를 조정하여 다이나믹 보팅의 단점인 읽기 단점을 극복하면서 동시에 높은 이용도를 유지하는 Read-Efficient Dynamic Voting Algorithm 이다. 제안된 알고리즘은 특정한 컴퓨터 (Primary Site) 가 시스템의 다른 컴퓨터들과 통신 네트웍이 완전히 분리되지 않는 한 데이타가 복사된 컴퓨터 수에 관계없이 두 개의 컴퓨터와의 통신만으로 정족수를 구하고 사용자의 요구를 수행 할 수 있다.
마지막으로 본 논문에서는 분산 시스템에서 Critical Section 을 보장하기 위하여 Weak Copy Consistency를 기반으로 하는 Distributed Mutual Exclusion Algorithm을 제시하였다. Distributed mutual exclusion algorithm에서는 n 개의 컴퓨터 (Site) 로 구성된 분산 시스템에서 critical section에 들어가기 위하여 필요로 하는 통신 메시지 수는 사용자 요구의 빈도에 따라 n/2에서 n이다. 그리고, 제안된 알고리즘이 critical section을 보장함을 증명 하였다.
