A Mutual Exclusion Algorithm in Asynchronous Distributed System with Failure Detectors

국문 초록 (Abstract)

본 논문에서는 토큰과 고장추적 장치를 이용한 상호배제 알고리즘을 비동기적인 분산시스템 환경에서 설계 하고 분석하고자 한다. 고장추적 장치란 독립된 프로그램으로 다른 프로세스의 크래시 여부를 알려주는 기능을 한다. 이러한 고장추적 장치를 이용하여 토큰기반 ME 알고리즘을 재 작성하는 경우 많은 유익함이 있다. 기존에 동기적인 분산 시스템에서 제안 되었던 토큰기반의 상호배제 (Mutual Exclusion)은 고장 추적 장치를 이용하여 재설계 되는 경 우 전통적인 토큰기반 상호배제 알고리즘 보다 훨씬 효율적으로 구현 될 수 있음을 보인다.

다국어 초록 (Multilingual Abstract)

In this paper, we design and analyze a mutual exclusion algorithm, based on the Token and Failure detector, in asynchronous distributed systems. A Failure Detector is an independent module that detects and reports crashes of other processes. There are some of advantages in rewriting the Token-based ME algorithm using a Failure Detector. We show that the Token-based ME algorithm, when using Failure Detector, is more effectively implemented than the classic Token-based ME algorithm for synchronous distributed systems.

참고문헌 (Reference)

• 1 T. D. Chandra, "Unreliable failure detectors for reliable distributed systems" 43 (43): 225-267, 1996
• 2 T. D. Chandra, "The weakest failure detector for solving consensus" 43 (43): 685-722, 1996
• 3 Carole Delporte-Gallet, "The weakest Failure Detector to Solve certain Fundamental Problems in Distributed computing" ACM Press 2004 2004
• 4 L. Lamport, "The mutual exclusion problem. Parts I&II" 33 (33): 313-348, 1986
• 5 E. W. Dijkstra, "Solution of a problem in concurrent programming control" 8 (8): 569-, 1965
• 6 M. J. Fischer, "Impossibility of distributed consensus with one faulty process" 32 (32): 374-382, 1985
• 7 N. A. Lynch, "Distributed Algorithms" Morgan Kaufmann Publishers 1996
• 8 G. Chockler, "Backo. protocols for distributed mutual exclusion and ordering" 2001
• 9 M. Maekawa, "A√N algorithm for mutual exclusion in decentralized systems" 3 (3): 145-159, 1985
• 10 Y.-J. Joung, "Asynchronous group mutual exclusion" 1998
• 11 E. Gafni, "Analysis of timing-based mutual exclusion with random times" 31 (31): 816-837, 2001
• 12 D. Manivannan, "An efficient fault-tolerant mutual exclusion algorithm for distributed systems" 525-530, 1994
• 13 D. Agrawal, "An efficient and fault-tolerant solution for distributed mutual exclusion" 9 (9): 1-20, 1991
• 14 P. Keane, "A simple local-spin group mutual exclusion algorithm" 12 (12): 673-685, 2001
• 15 V. Hadzilacos, "A note on group mutual exclusion" 2001
• 16 L. Lamport, "A new solution of Dijkstra’s concurrent programming problem" 17 (17): 453-455, 1974
• 17 S. Lodha, "A fair distributed mutual exclusion algorithm" 11 (11): 537-549, 2000
• 18 I. Suzuki, "A distributed mutual exclusion algorithm" 3 (3): 344-349, 1985