k-Coteries for Tolerating Network 2-Partition

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/TPDS.2004.23

July 2004 (vol. 15 no. 7) pp. 666-672

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Takashi Harada Articles by Masafumi Yamashita

	ASCII Text	x
	Takashi Harada, Masafumi Yamashita, "k-Coteries for Tolerating Network 2-Partition," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 7, pp. 666-672, July, 2004.

	BibTex	x
	@article{ 10.1109/TPDS.2004.23, author = {Takashi Harada and Masafumi Yamashita}, title = {k-Coteries for Tolerating Network 2-Partition}, journal ={IEEE Transactions on Parallel and Distributed Systems}, volume = {15}, number = {7}, issn = {1045-9219}, year = {2004}, pages = {666-672}, doi = {http://doi.ieeecomputersociety.org/10.1109/TPDS.2004.23}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - JOUR JO - IEEE Transactions on Parallel and Distributed Systems TI - k-Coteries for Tolerating Network 2-Partition IS - 7 SN - 1045-9219 SP666 EP672 EPD - 666-672 A1 - Takashi Harada, A1 - Masafumi Yamashita, PY - 2004 KW - Distributed systems KW - complemental KW - k-coteries KW - k-semicoteries KW - k-mutual exclusion problem KW - network 2-partition KW - nondominatedness KW - quorums. VL - 15 JA - IEEE Transactions on Parallel and Distributed Systems ER -

Takashi Harada, IEEE Computer Society

Masafumi Yamashita, IEEE Computer Society

Abstract—Network partition, which makes it impossible for some pairs of precesses to communicate with each other, is one of the most serious network failures. Although the notion of k-coterie is introduced to design a k-mutual exclusion algorithm robust against network failures, the number of processes allowed to simultaneously access the critical section may fatally decrease once network partition occurs. This paper discusses how to construct a k-coterie such that the k-mutual exclusion algorithm adopting it is robust against network 2-partition. To this end, we introduce the notion of complementalk-coterie, and show that complemental k-coteries meet our purpose. We then give methods for constructing complemental k-coteries, and show a necessary and sufficient condition for a k-coteries to be complemental.

[1] 666 D. Agrawal, O. Egecioglu, and A. El Abbadi, Analysis of Quorum-Based Protocols for Distributed (k+1)- Exclusion IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 5, pp. 533-537, May 1997.
[2] D. Barbara and H. Garcia-Molina, The Vulnerability of Vote Assignments ACM Trans. Computer Systems, vol. 4, no. 3, pp. 187-213, Aug. 1986.
[3] Y.I. Chang and B.H. Chen, A Generalized Grid Quorum Strategy fork-Mutual Exclusion in Distributed Systems Information Processing Letters, vol. 80, no. 4, pp. 205-212, Nov. 2001.
[4] S. Fujita, M. Yamashita, and T. Ae, Distributedk-Mutual Exclusion Problem andk-Coteries Lecture Notes in Computer Science, vol. 557, pp. 22-31, 1991.
[5] H. Garcia-Molina and D. Barbara, How to Assign Votes in a Distributed Systems J. ACM, vol. 32, no. 4, pp. 841-860, Oct. 1985.
[6] S.T. Huang, J.R. Jiang, and Y.C. Kuo, K-Coteries for Fault-Tolerant k Entries to a Critical Section Proc. 13th Int'l Conf. Distributed Computing Systems, pp. 74-81, May 1993.
[7] T. Harada and M. Yamashita, Coterie Join Operation and Tree Structuredk-Coteries IEEE Trans. Parallel and Distributed Systems, vol. 12, no. 9, pp. 865-874, Sept. 2001.
[8] T. Harada and M. Yamashita, k-Coteries for Tolerating Network 2-Partition Proc. Sixth Int'l Conf. Principles of Distributed Systems, pp. 119-126, Dec. 2002.
[9] J.R. Jiang and S.T. Huang, Obtaining Nondominated K-Coteries for Fault-Tolerant Distributed K-Mutual Exclusion Proc. Int'l Conf. Parallel and Distributed Systems, 1994.
[10] H. Kakugawa, S. Fujita, M. Yamashita, T. Ae, Availability ofk-Coterie IEEE Trans. Computers, vol. 42, no. 5, pp. 553-558, May 1993.
[11] H. Kakugawa, S. Fujita, M. Yamashita, and T. Ae, A Distributedk-Mutual Exclusion Algorithm Usingk-Coterie Information Processing Letters, vol. 49, no. 4, pp. 213-218, Feb. 1994.
[12] Y.C. Kuo and S.T. Huang, A Geometric Approach for Constructing Coteries andk-Coteries IEEE Trans. Parallel and Distributed Systems, vol. 8, no. 4, pp. 402-411, Apr. 1997.
[13] M.L. Neilsen and M. Mizuno, Nondominatedk-Coteries for Multiple Mutual Exclusion Information Processing Letters, vol. 50, no. 5, pp. 247-252, June 1994.
[14] M.L. Neilsen and M. Mizuno, Erratum to‘Nondominatedk-Coteries for Multiple Mutual Exclusion’ Information Processing Letters, vol. 60, no. 6, p. 319, Dec. 1996.
[15] K. Raymond, A Distributed Algorithm for Multiple Entries to a Critical Section Information Processing Letters, vol. 30, no. 4, pp. 189-193, Feb. 1989.
[16] P.K. Srimani and R.L.N. Reddy, Another Distributed Algorithm for Multiple Entries to a Critical Section Information Processing Letters, vol. 41, no. 1, pp. 51-57, Jan. 1992.
[17] S.M. Yuan and H.M. Chang, Comments on‘Availability ofk-Coterie’ IEEE Trans. Computers, vol. 43, no. 12, p. 1457, Dec. 1993.

Index Terms:

Distributed systems, complemental, k-coteries, k-semicoteries, k-mutual exclusion problem, network 2-partition, nondominatedness, quorums.

Citation:

Takashi Harada, Masafumi Yamashita, "k-Coteries for Tolerating Network 2-Partition," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 7, pp. 666-672, July 2004, doi:10.1109/TPDS.2004.23

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.