동기적 분산 시스템에서 효율적인 조정자 선출 알고리즘 = An Efficient Coordinator Election Algorithm in Synchronous Distributed Systems

다국어 초록 (Multilingual Abstract)

Leader election is an important problem in developing fault-tolerant distributed systems. As a classic solution for leader election, there is Garcia-Molina's Bully Algorithm based on time-outs in synchronous systems. In this paper, we re-write the Bully Algorithm to use a failure detector instead of explicit time-outs. We show that this algorithm is more efficient than the Garcia-Molina's one in terms of the processing time. That is because the Bully_FD uses FD to know whether the process is up or down so fast and it speed up its execution time. Especially, where many processes are connected in the system and crash and recovery of processes are frequent, the Bully_FD algorithm is much more efficient than the classical Bully algorithm in terms of the processing time.

국문 초록 (Abstract)

결함 허용(fault-tolerant) 분산 시스템 구축 시 리더 선출(leader election)은 중요한 문제이다. 전통적인 방법으로 타임아웃에 기초한 동기적 분산 시스템을 위한 불리(Bully) 알고리즘이 있다. 본 논문에서는 타임아웃 보다는 Failure Detector를 이용한 수정된 불리 알고리즘을 제시하고, 또한 전통적인 불리 알고리즘과 비교하여 수정된 불리 알고리즘의 수행 속도가 빠름을 보여주고 있다. 그 이유는 수정된 불리 알고리즘 수행 시 각 프로세스의 정상적인 작동 여부를 FD를 이용하여 빠르게 처리함으로써 처리 속도의 효율성이 높다는 점이다. 특히 다수의 프로세스들이 시스템으로 연결 되어 있고, 각 프로세스에서 작동하는 프로세스들의 고장과 회복이 빈번히 발생하는 분산 시스템에서 FD를 이용하는 불리 알고리즘의 수행 속도는 전통적인 불리 알고리즘에 비해 훨씬 빠름을 보여 준다.

참고문헌 (Reference)

1 "unidirectional algorithm for circular extrima problem" 4 : 758-762, 1982.

2 "message distributed algorithm for minimum weighted spanning trees Proc. Foundations of Computer Science Conf." 257-166, 1985.

3 "Zohar Manna and Amir Pnueli. The temporal logic of reactive systems. Springer-Verlag" 1992.

4 "Unreliable failure detectors for reliable distributed systems Journal of ACM" 43 (43): 225-267, 1996

5 "Reaching agreement on processor group membership in Synchronous distributed systems" 4 : -4, 1991.

6 "Proc. 5th International Workshop on distributed Algorithms Vol. 579 of Lecture Notes in Computer Science" pp. 167-180. Springer-Verlag 1991.

7 "Michal Politi. Modeling Reactive System with Statecharts." McGraw-Hill 1998.

8 "Improvement in time complexity of two message optimal algorithm Proc. Principles of Distributed Computing Conf." 175-185, 1985.

9 "Impossibility of distributed consensus with one fault process" 32 (32): 374-382, 1985.04

10 "Elections in a distributed computer system. IEEE Trans. on computer" 31 : 48-59, 1982.

11 "Decentralized extrima finding in circular configurations of Processors Communications of the ACM" [ 3 ] D. S. Hirshberg and J. B. Sinclair. 23 : 627-628, 1980.

12 "An optimal distributed algorithm for failure driven leader election in bounded-degree networks Proc. IEEE Workshop on Future Trends of Distributed Computing Systems" 136-141, 1992.

13 "An improved algorithm for the decentralized extrima-finding in circular configurations of processes Communication of ACM" 22 (22): 281-283, 1979.

14 "Agreeing on processor group membership in asynchronous distributed systems" university of california 1995.

15 "A distributed algorithm for minimum weighted spanning trees ACM trans. On Programming language and Systems" 5 : 66-77, 1983.

16 ", constant space, self-stabilizing leader election on uniform rings" 972 : 288-302, 1995.