Commenced in January 2007
Paper Count: 30184
A Fault Tolerant Token-based Algorithm for Group Mutual Exclusion in Distributed Systems
Abstract:The group mutual exclusion (GME) problem is a variant of the mutual exclusion problem. In the present paper a token-based group mutual exclusion algorithm, capable of handling transient faults, is proposed. The algorithm uses the concept of dynamic request sets. A time out mechanism is used to detect the token loss; also, a distributed scheme is used to regenerate the token. The worst case message complexity of the algorithm is n+1. The maximum concurrency and forum switch complexity of the algorithm are n and min (n, m) respectively, where n is the number of processes and m is the number of groups. The algorithm also satisfies another desirable property called smooth admission. The scheme can also be adapted to handle the extended group mutual exclusion problem.
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1057393Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1282
 Y. J. Joung, "Asynchronus group mutual exclusion (extended abstract)," in Proc. of the 17th annual ACM Symposium on Principles of Distributed Computing (PODC), 1998, pp. 51-60.
 P. Kean, and M. Moir, " A simple local spin group mutual exclusion algorithm," in Proc. 18th Annual ACM Symposium on Principles of Distributed Computing, 1999, pp. 23-32.
 Y. J. Joung, "The congenial talking philosopher problem in computer networks", Distributed Computing, vol. 15, 2002, pp. 155-175.
 S. Cantarell, A.K. Dutta, F. Pilit, and V. Villain, "Token based group mutual exclusion for asynchronous rings," in Proc. IEEE International Conference on Distributed Computing Systems, 2001, pp. 691- 694.
 D. Lin, T. S. Moh, and M.. Moh, "Brief announcement: improved asynchronous group mutual exclusion in token passing networks," in Proc. Annual ACM Symposium on Principles of Distributed Computing, 2005, pp. 275-275.
 Q. E. K. Mamun, and H. Nakazato, "A new token based protocol for group mutual exclusion in distributed systems," in Proc. 5th International Symposium on Parallel and Distributed Computing, 2006, pp. 34-41.
 O.Thiare, M. Gueroui, and M. Naimi, "Distributed group mutual exclusion based on client/servers model," in Proc. 7th International Conference on Parallel and Distributed Computing, Applications and Technologies, 2006, pp. 67-73.
 N. Mittal, and P. K. Mohan, "A priority-based distributed group mutual exclusion algorithm when group access is non uniform," Journal of Parallel and Distributed Computing, vol. 67, no. 7, 2007, pp. 797-815.
 K. P. Wu, and Y. J. Joung "Asynchronous group mutual exclusion in ring networks," in Proc. 13th International Parallel Processing Symposium, 1999, pp. 539-543.
 A. Swaroop, and A. K. Singh, "A distributed group mutual exclusion algorithm for soft real time systems," in Proc. WASET International Conference on Computer, Electrical and System Science and Engineering CESSE-07, vol. 26, December 2007, pp. 138-143.
 Y. Manabe, and J. Park "Quorum based extended group mutual exclusion algorithm without unnecessary blocking," in Proc. 10th International Conference on Parallel and Distributed Systems, 2004, pp. 341-348.
 R. Attreya, and N. Mittal, "A dynamic group mutual exclusion algorithm using surrogate quorums," in Proc. 25th IEEE Conference on Distributed Computing Systems, 2005, pp. 251-260.
 M. Toyomura, and S. Kamei, and H. Kakugawa, "A quorum-based distributed algorithm for group mutual exclusion," in Proc. International Conference on Parallel and Distributed Computing, Applications and Technologies PDCAT-03, 2003, pp. 742-746.
 I. Suzuki, and T. Kasmi, "A distributed mutual exclusion algorithm," ACM Transactions on Computer Systems, vol. 3, no. 4, 1985, pp. 344- 349.
 Y. I. Chang, M. Singhal, and M. T. Liu, "A dynamic token based distributed mutual exclusion algorithm," in Proc. 10th Annual International Phoenix Conference on Computers and Communications, 1991, pp. 240-246.
 B, Selic, "Fault tolerance techniques in distributed systems," Available at URL: www-128.ibm.com/developerworks /rational/library/114.html, 2004.
 M. Takamura, and Y. Igarashi, "Group mutual exclusion based on ticket orders," COCON 2003, LNCS 2697, 2003, pp. 232-41.
 D. Manivannan, and M. Singhal, "A decentralized token generation scheme for token-based mutual exclusion algorithms," International Journal of Computer Systems Science and Engineering, vol. 11, no. 1, 1996, pp. 45-54.