In a distributed computer system, where a set of autonomous hosts are geographically dispersed and integrated by a distributed operating system or distributed database system, processes often engage into cooperative or competing efforts to exploit the potential benefits of distributed computer system. An abstract entity usually has the responsibility of the coordination of process. The abstract entity is called a distributed control system, when it consists of two or more controllers, and when each controller has different and only limited view of the global state.
Due to the limited view of global state, distributed control system should provide a means to all controllers, which enables these controllers to obtain a consistent and identical view of the global state of the system without a unique centralized database structure. However, since the message passing (i.e., no global memory) is the only means of communications and since the message propagation time is finite and unpredictable, the complete and consistent state information of the entire system may not be available to any controller. As a result, in distributed environment, controllers have to decide their actions based on the partially correct and outdated information, but the actions do not violate the consistency of the global state. Moreover, communication overheads occur considerably, which is caused by the exchange of the state information and coordination of the activities. Thus, it is important to make the distributed control system impose extra traffic to the communication channels as little as possible.
In this thesis, a model of distributed control for resource management systems with less communication overhead is proposed. One of the main idea is to replicate the state information to several sites, and relax the copy consistency constraint resulting from the replication. The other is to make each process deduce the global state from known state information to itself, which may be outdated due to the finite and unpredictable communication delays. To do it theoretically, at first uncertainty of the global state is defined by reviewing the logical and physical characteristics of distributed control. Using the uncertainty of state, we relax the copy consistency constraint resulting from replication of state variables, more weakly than the ones used in distributed databases, and propose an optimistic copy consistency, which explains the retardation of information dissemination in distributed environment. It is shown that the proposed copy consistency can reduce the communication overheads considerablely by making each controller estimate the global state of the entire system from the approximated information known to itself.
We apply our model to two different applications: Load Balancing and Distributed Mutual Exclusion. We also develop efficient algorithms for the applications. In the application to load balancing, we derive the necessary and sufficient conditions, under which each controller (i.e., scheduler) can guarantee load balance of the global state without communication. The proposed algorithm for distributed mutual algorithm requires less number of message transmissions per the critical section invocation than the previously published algorithms. And it is proved by the simulations.
본 논문에서는 적은 통신량으로도 효과적으로 자원(resource)를 관리할 수 있는 분산 제어 모형을 제안하고, 부하 평형(Load Balancing)과 분산 상호 배타(Distriubuted Mutual Exclusion)문제에 적용하였다.
분산 환경하에서의 제어기(controller)는 단지 지역 자원 혹은 지역 상태 정보만을 관리하므로, 시스템 전체의 자원 상태를 알 수 없다. 따라서 지역 자원의 상태가 변하면, 변화된 지역 정보만으로는 전체 시스템 자원의 상태가 자원 관리 규칙을 만족하는지를 알 수 없으므로, 다른 제어기들과 통신하므로 이를 확인하여야 한다. 하지만 분산 환경하에서의 유일한 통신 수단은 메세지 교환(message passing)이고 메세지를 전송하는데 걸리는 비용(혹은 시간)이 유한하므로 통신량이 증가하면, 전체 자원 관리 시스템의 성능은 감퇴된다. 따라서 효율적인 자원 관리를 위한 분산 제어 모형은 가능한한 제어기 상호간의 통신량을 감소시키는 것이 필수적이다.
본 논문에서 제안된 모형은 각 지역 자원의 상태 정보를 여러곳에 복제하고, 복제된 상태 정보의 상호 일치 (Mutual Consistency)를 완화시킴으로써 상호일치에 필요한 통신량을 감소케하고, 각 제어기가 전체 상태를 쉽고 빠르게 예측하게 함으로써, 전체 통신량을 감소시킬 수 있다. 또한 부하 평형 문제에 적용하여 제어기간의 메세지 교환 없이도 각 제어기들이(이 경우는 스케쥴러) 시스템 전체의 부하 상태가 평형을 이룸을 알 수 있는 필요·충분조건을 유출해 냄으로써 기존의 방법보다 효율적으로 자원을 관리할 수 있게 하였으며, 이를 모의 실험을 통해 입증하였다.
또한 제안된 모형을 분산 상호 배타 문제에 적용하여 얻은 Algorithm은 critical section을 한번 수행하는데 평균적으로 n/2에서 n까지의 (n은 전체 제어기의 수) 메세지 전송을 필요로 함으로써 기존의 Algorithm 보다 우수하며 이를 모의 실험으로 입증하였다.
