Nowadays distributed computer systems are widely used and their technology has reached a certain degree of maturity. However, even with substantial research efforts on this topic, understanding the behavior of a distributed program still remains to be a challengeable work. This is caused mainly by distributed program's nondeterminism which complicates the design, understanding, and analysis of distributed programs. Causal order algorithm ensures that every transmitted message is delivered in causal order. It provides a built-in message synchronization and relieves the programmer from inconsistencies due to transmission delays in a distributed computation. It should be noted that control information should be transmitted with each message in order to enforce causal order. Hence, it is important to reduce this communication overhead because the impact of the overhead increases proportionally with the number of recipients.
To reduce communication overhead, we analyze all valid communication patterns and group them into 5 abstract communication patterns. From these abstract communication patterns, we identify redundant information which is not strictly required in preserving causal order. Efficient causal order algorithms should transmit redundant information as small as possible. We classify redundant information into two categories: first order redundant information and second order redundant information. First order redundant information is control information which is not strictly necessary for enforcing causal order and is classified into four types: information regarding just delivered, already delivered, just replaced, and already replaced messages. Elimination of first order redundant information results in retaining only causal dependents that are explicitly required for preserving causal order. But, if control information which is not included in the first order redundant information is sent more than once to a certain process, then it becomes second order redundant information regarding already informed messages.
In this thesis, we propose two efficient causal multicast algorithms which send less amount of control information than other existing algorithms. The first one is causal multicast algorithm for reliable distributed systems, and the other one is delta causal multicast algorithm for multimedia systems. Our algorithms are based on pruning redundant information as early as possible. Even though the worst case communication overhead complexity of our algorithm is not superior to other existing algorithms, average communication overheads are much smaller than other existing algorithms. Application area of our algorithm is not restricted to systems whose communication channels are FIFO. Also, unicast, multicast, and broadcast communications are supported through the same program without modification. We proved correctness of our algorithms and comparative savings of our algorithm in the amount of communication overhead and communication delay are shown by simulation. Simulation results show that average communication overhead and communication delay of our algorithm are extremely smaller than that of other existing algorithms and our algorithm has better scalability feature than other algorithms. Especially in multicast communication, efficiency of our algorithm is remarkable.
분산시스템은 이제 보편적으로 사용되고 있고 그에 대한 기술도 상당히 성숙되었다. 그러나 수많은 노력에도 불구하고 아직 분산시스템의 특성을 정확히 파악하고 활용하지는 못하고 있다. 이것은 주로 분산시스템의 설계와 이해, 분석을 어렵게 하는 분산프로그램 실행의 불특정성에서 기인된다.
인과순서화 알고리즘은 분산프로그램의 실행시 전송되는 메시지들이 인과순서를 유지하도록 해주는 것으로 메시지들 간의 동기를 맞춰주고 분산실행에서 발생할 수 있는 불일치가 발생하지 않도록 하여 프로그래머들이 분산프로그램을 쉽게 할 수 있도록 해준다. 인과순서를 유지하기 위해서는 전송되는 모든 메시지가 제어정보를 가지고 다녀야 하고, 제어정보의 크기는 관련된 프로세스의 수에 비례하여 커지게 되므로 제어정보의 크기를 줄이는 것은 분산시스템의 주요한 관심사가 되어왔다.
본 논문에서는 전송부하를 줄이기 위하여 모든 유효한 통신패턴을 분석하여 5가지의 추상적인 통신패턴으로 나누고 이로부터 인과순서를 유지하는데 필수적이지 않은 중복정보를 찾아낸다. 효율적인 인과순서화알고리즘은 이런 중복정보의 전송을 최소화시켜야 한다.
중복정보는 일차적중복정보와 이차적중복정보로 분류된다. 일차적 중복정보는 인과순서유지에 반드시 필요하지 않은 정보들로, 직전에 전달된 메시지에 대한 정보, 과거에 전달된 메시지에 대한 정보, 직전에 대치된 메시지에 대한 정보, 과거에 대치된 메시지에 대한 정보의 4가지 종류로 구분된다. 일차적 중복정보를 제거한 뒤에 남는 정보는 모두 인과순서를 유지하는데 반드시 필요한 정보들이다. 그러나 이러한 정보들도 동일 프로세스에게 두 번 이상 전달될 경우에는 인과순서를 유지하는데 반드시 필요한 정보가 되지 않게 된다. 이러한 정보들이 이차적중복정보가 된다.
본 논문에서는 두 가지 인과순서화 알고리즘을 제안한다. 하나는 신뢰성있는 분산시스템을 위한 인과순서화 알고리즘이고 다른 하나는 실시간 성격을 가지는 멀티미디어 시스템을 위한 델타인과순서화 알고리즘이다.
제안하는 알고리즘들은 중복정보를 가능한 이른 시기에 제거하는 방식을 취한다. 비록 최악의 경우에는 우리의 알고리즘이 기존 알고리즘보다 뛰어나지 않을 수도 있으나 일반적인 경우에는 기존 알고리즘보다 훨씬 적은 전송부하를 가지게 된다. 또 우리의 알고리즘은 통신회선이 FIFO 순서를 보장하지 않는 일반적인 망에서도 적용될 수 있으며 단일전송, 다중전송, 동보전송 모두를 한꺼번에 지원한다.
모의실험을 통하여 제안하는 알고리즘과 기존 알고리즘의 통신부하와 통신지연을 비교한다. 모의실험의 결과 평균전송부하와 평균전송지연이 기존 알고리즘보다 훨씬 적음을 알 수 있었고 확장성도 뛰어남을 알 수 있다. 특히 다중전송의 경우, 제안하는 알고리즘은 기존 알고리즘보다 더욱 효과적이다.