Abstract
The (m,h,k)-resource allocation is a conflict resolution problem to control and synchronize a distributed system consisting of n nodes and m shared resources so that the following two requirements are satisfied: at any given time at most h (out of m) resources can be used by some nodes simultaneously, and each resource is used by at most k concurrent nodes. The problem is a natural generalization of several well-studied conflict resolution problems such as mutual exclusion, k-mutual exclusion, generalized mutual exclusion and group mutual exclusion. The problem can be solved by employing an ℓ-mutual exclusion algorithm, however, it is inefficient in terms of the message complexity and the maximum degree hk of concurrency may not be achieved. We thus propose a new algorithm and a new quorum system (m, h, k)-coterie used in it, and show that all requirements of the problem are guaranteed and the maximum concurrency degree is achieved as desired. We also present a natural extension of the new quorum system which resolves a more general problem with distinct bounded capacities and also achieves the maximum degree of concurrency, \(\sum^{h}_{i=1}{k}_{i}\), of the problem.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, D., Abbadi, A.E.: An efficient and fault-tolerant algorithm for distributed mutual exclusion. ACM Trans. Computer Systems 9, 1–20 (1991)
Bernstein, P., Goodman, N.: The failure and recovery problem for replicated databases. In: Proc. Principles of Distributed Computing (PODC), pp. 114–122 (1983)
Garcia-Molina, H., Barbara, D.: How to assign votes in a distributed system. Journal of the ACM 32, 841–860 (1985)
Maekawa, M.: A \(\sqrt{N}\) algorithm for mutual exclusion in decentralized systems. ACM Transaction on Computer Systems 3, 145–159 (1985)
Ibaraki, T., Kameda, T.: A theory of coteries: Mutual exclusion in distributed systems. IEEE Trans. on Parallel and Distributed Computing 4, 779–794 (1993)
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)
Kakugawa, H., Fujita, S., Yamashita, M., Ae, T.: Availability of k-coterie. IEEE Transaction on Computers 42, 553–558 (1993)
Joung, Y.J.: Quorum-based algorithms for group mutual exclusion. IEEE Transaction on Parallel and Distributed Systems 14, 463–476 (2003)
Lawi, A., Yamashita, M.: A quorum based m-group (h,k)-exclusion algorithm. In: Proc. International Symposium on Information Science and Electrical Engineering (ISEE 2003), pp. 405–408 (2003)
Joung, Y.-J.: On Quorum Systems for Group Resources with Bounded Capacity. In: Guerraoui, R. (ed.) DISC 2004. LNCS, vol. 3274, pp. 86–101. Springer, Heidelberg (2004)
Kakugawa, H., Yamashita, M.: Local coteries and a distributed resource allocation algorithm. Trans. Information Processing Society of Japan 37, 1487–1498 (1996)
Vidyasankar, K.: A simple group mutual ℓ-exclusion algorithm. Information Processing Letters 85, 79–85 (2003)
Lawi, A., Oda, K., Yoshida, T.: A Quorum Based Group k-Mutual Exclusion Algorithm for Open Distributed Environments. In: Pan, Y., Chen, D.-x., Guo, M., Cao, J., Dongarra, J. (eds.) ISPA 2005. LNCS, vol. 3758, pp. 119–125. Springer, Heidelberg (2005)
Manabe, Y., Tajima, N.: (h,k)-arbiters for h-out-of-k mutual exclusion problem. Theoretical Computer Science 310, 379–392 (2004)
Datta, A.K., Hadid, R., Villain, V.: A New Self-Stabilizing k-out-of-ℓ Exclusion Algorithm on Rings. In: Huang, S.-T., Herman, T. (eds.) SSS 2003. LNCS, vol. 2704, pp. 113–128. Springer, Heidelberg (2003)
Lamport, L.: Time, clocks and the ordering of events in a distributed system. Communications of the ACM 21, 558–565 (1978)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lawi, A., Oda, K., Yoshida, T. (2006). Quorum Based Distributed Conflict Resolution Algorithm for Bounded Capacity Resources. In: Min, G., Di Martino, B., Yang, L.T., Guo, M., Rünger, G. (eds) Frontiers of High Performance Computing and Networking – ISPA 2006 Workshops. ISPA 2006. Lecture Notes in Computer Science, vol 4331. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11942634_15
Download citation
DOI: https://doi.org/10.1007/11942634_15
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49860-5
Online ISBN: 978-3-540-49862-9
eBook Packages: Computer ScienceComputer Science (R0)