A Fault-tolerant Mutual Exclusion Algorithm in Asynchronous Distributed Systems
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Mutual Exclusion is one of the most studied topics in distributed systems where processes communicate by asynchronous message passing. It is often necessary for multiple processes at different sites to access a shared resource or data called a critical section (CS) in distributed systems. A number of algorithms have been proposed to solve the mutual exclusion problem in distributed systems. In this paper, we propose the new algorithm which is modified from Garg's algorithm[1] thus works properly in a fault-tolerant system. In our algorithm, after electing the token generator, the elected process generates a new token based on the information of the myreqlist which is kept by every process and the reqdone which is received during election. Consequently, proposed algorithm tolerates any number of process failures and also does even when only one process is alive.
Abstract
Mutual Exclusion is one of the most studied topics in distributed systems where processes communicate by asynchronous message passing. It is often necessary for multiple processes at different sites to access a shared resource or data called a critical section (CS) in distributed systems. A number of algorithms have been proposed to solve the mutual exclusion problem in distributed systems. In this paper, we propose the new algorithm which is modified from Garg's algorithm[1] thus works properly in a fault-tolerant system. In our algorithm, after electing the token generator, the elected process generates a new token based on the information of the myreqlist which is kept by every process and the reqdone which is received during election. Consequently, proposed algorithm tolerates any number of process failures and also does even when only one process is alive.
참고문헌 (13)
- Vijay K. Garg, "Elements of Distributed Computing" (2002), A John Wiley & Sons Inc., Publication
- D. Agrawal, "An efficient solution to the distributed mutual exclusion problem", Proc. 8th ACM Symposium on Principles of Distributed Computing, pp.193~200 (1989)
- G. Ricart, "An optimal algorithm for Mutual Exclusion in Computer Networks", Communications of the ACM (1981)
- M. Singhal, "A dynamic information structure for mutual exclusion algorithm for distributed systems", IEEE Transactions on Parallel Distributed Systems, 3(1), pp.121~125 (1992)
- M. Maekawa, "A Square Root N Algorithm for Mutual Exclusion in Decentralized Systems", ACM Transactions on Computer Systems(TOCS), (324), pp.145~159 (1985)
- I. Suzuki, "A distributed mutual exclusion algorithm", ACM Transactions on Computer Systems (TOCS), 3(4), pp.344~349 (1985)
- M. Singhal, "A Heuristically Aided Algorithm for Mutual Exclusion in Distributed Systems", IEEE Transactions on Computers, 38(5), pp.651~662 (1989)
- Quazi Ehsanul Kabir Mamun, "A New Token Based Protocol for Group Mutual Exclusion in Distributed Systems", IEEE Proceedings of the fifth International Symposium on Parallel and Distributed Computing (2006)
- K. Raymond, "A tree-based algorithm for distributed mutual exclusion", ACM Transactions on Computer Systems (TOCS), 7(1), pp.61~77 (1989)
- J. Sopena, "A Fault- Tolerant Token-Based Mutual Exclusion Algorithm Using a Dynamic Tree", In EuroPar 2005 (2005), LNCS
- S. Mishra, "Fault-tolerant mutual exclusion algorithms", Journal of Systems Software, 11(2), pp.111~129 (1990)
- M. Singhal, "A heuristically-aided algorithm for mutual exclusion in distributed systems", IEEE Transactions on Computers, 38(5), pp.651~662 (1989)
- Chang, M. Singhal, "A fault tolerant algorithm for distributed mutual exclusion", Proc. of 9th IEEE Syrup. On Reliable Dist. Systems, pp.146~154 (1990)