A Fault Tolerant Token-based Algorithm for Group Mutual Exclusion in Distributed Systems

Authors: Abhishek Swaroop, Awadhesh Kumar Singh

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.

Keywords: Dynamic request sets, Fault tolerance, Smoothadmission, Transient faults.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1057393

References:

[1] 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.
[2] 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.
[3] Y. J. Joung, "The congenial talking philosopher problem in computer networks", Distributed Computing, vol. 15, 2002, pp. 155-175.
[4] 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.
[5] 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.
[6] 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.
[7] 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.
[8] 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.
[9] 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.
[10] 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.
[11] 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.
[12] 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.
[13] 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.
[14] I. Suzuki, and T. Kasmi, "A distributed mutual exclusion algorithm," ACM Transactions on Computer Systems, vol. 3, no. 4, 1985, pp. 344- 349.
[15] 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.
[16] B, Selic, "Fault tolerance techniques in distributed systems," Available at URL: www-128.ibm.com/developerworks /rational/library/114.html, 2004.
[17] M. Takamura, and Y. Igarashi, "Group mutual exclusion based on ticket orders," COCON 2003, LNCS 2697, 2003, pp. 232-41.
[18] 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.