Abstract
This paper presents a quorum-based group k-mutual exclusion algorithm for open distributed computing systems that can evolve their behavior based on membership changes in the environment. The algorithm consists of two main layers; the quorum-consensus and quorum-reconfiguration. The quorum consensus layer is used to handle requests from and to the application layer, and it directly adopts a proposed k-coterie based algorithm of the group k-mutual exclusion in the static environments without any change to its protocol. Thus, the message complexity and quorum availability are the same as in the static environments. The quorum reconfiguration reconstructs information structure of the k-coterie by simply implementing the properties of two quorum input operations called coterie-join and coterie-cross. The reconfiguration layer is simple to use and has a great ability to complete any operation during reconfiguration powerfully thus system does not enter the halt state.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Vidyasankar, K.: A simple group mutual ℓ-exclusion algorithm. Information Processing Letters 85, 79–85 (2003)
Agrawal, D., Abbadi, A.E.: An efficient and fault-tolerant algorithm for distributed mutual exclusion. ACM Trans. Computer Systems 9, 1–20 (1991)
Garcia-Molina, H., Barbara, D.: How to assign votes in a distributed system. Journal of the ACM 32, 841–860 (1985)
Joung, Y.J.: Quorum-based algorithms for group mutual exclusion. IEEE Transaction on Parallel and Distributed Systems 14, 463–476 (2003)
Schlichting, R., Schneider, F.: Fail-stop processors: an approach to designing fault-tolerant computing systems. ACM Trans. Computer Systems 1, 222–238 (1983)
Lawi, A., Oda, K., Yoshida, T.: A simple quorum reconfiguration for open distributed environments. In: Proc. International Conference on Parallel and Distributed Systems (ICPADS), July 2005, vol. II, pp. 664–668 (2005)
Fujita, S., Yamashita, M., Ae, T.: Distributed k-mutual exclusion problem and k-coteries. In: Hsu, W.-L., Lee, R.C.T. (eds.) ISA 1991. LNCS, vol. 557, pp. 22–31. Springer, Heidelberg (1991)
Neilsen, M.L., Mizuno, M.: Coterie join algorithm. IEEE Trans. Parallel and Dist. Systems 3, 582–590 (1992)
Jiang, J.R., Huang, S.T.: Obtaining nondominated k-coteries for fault-tolerant distributed k-mutual exlusion. In: Proc. International Conference on Parallel and Distributed Systems (ICPADS), pp. 582–587 (1994)
Maekawa, M.: A \(\sqrt{N}\) algorithm for mutual exclusion in decentralized systems. ACM Trans. Computer Systems 3, 145–159 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lawi, A., Oda, K., Yoshida, T. (2005). A Quorum Based Group k-Mutual Exclusion Algorithm for Open Distributed Environments. In: Pan, Y., Chen, D., Guo, M., Cao, J., Dongarra, J. (eds) Parallel and Distributed Processing and Applications. ISPA 2005. Lecture Notes in Computer Science, vol 3758. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11576235_16
Download citation
DOI: https://doi.org/10.1007/11576235_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29769-7
Online ISBN: 978-3-540-32100-2
eBook Packages: Computer ScienceComputer Science (R0)