One of the important features of distributed computing systems(DCSs) is the possibility of having high reliability. When the hardware configuration of a DCS is fixed, the system reliability mainly depends on the allocation of various resources such as various files. This thesis considers a file allocation problem for maximizing the system reliability of a DCS in a situation where a DCS has a tree network structure, each file is unique, and nodes and links are both subject to stochastic failures. In the analysis, the proposed file allocation problem is decomposed into two subproblems including a bin packing problem and a cardinality rooted tree problem. An optimal two phase algorithm is proposed for the file allocation problems. Numerical problems are solved to evaluate the efficiency of the algorithm.
분산시스템의 중요한 장점 중의 하나는 높은 신뢰도를 얻을 수 있다는 것이다. 분산시스템의 하드웨어 배치가 결정되면, 시스템의 신뢰도는 파일과 같은 여러 가지 자원들의 배치에 크게 의존하게 된다. 본 논문에서는 분산시스템에서 파일 배치에 관계된 신뢰도 문제를 다루었다. 이 문제는 프로그램 수행 시 프로그램이 위치한 노드로부터 떨어진 노드에 위치한 파일들을 필요하다고 할 때 프로그램 수행 신뢰도를 최대화 시키기 위해 파일을 어떤 노드에 배치 할 것인가에 관한 것이다. 본 논문에서는 각 파일은 한 개의 복사본만을 가질 수 있고, 노드와 링크의 고장을 고려한 트리구조를 가진 분산시스템을 가정하였다. 이러한 제한을 주면 파일 배치 문제는 bin packing 문제와 cardinality rooted tree 문제로 나뉘어 질 수 있다. 본 논문에서는 최적해를 구하는 이단계 방법과 불필요한 계산을 줄여 주는 트리 축소 알고리즘을 제안하였다. 또 제안된 알고리즘들을 모든 가능해를 찾는 방법과 비교하여 효율을 평가하였다.
