Danial Rahdari; Amir Masoud Rahmani; Afsane Arabshahi

Fault Tolerant Message Efficient Coordinator Election Algorithm in High Traffic Bidirectional Ring Network

Full Text (PDF, 635KB), PP.15-25

Views: 0 Downloads: 0

Author(s)

Danial Rahdari ^1,* Amir Masoud Rahmani ¹ Afsane Arabshahi ²

1. Department of computer Engineering, Science and research branch, Islamic Azad University, Tehran, Iran

2. Department of Computer Engineering, Sistan and Baloochestan University, Zahedan, Iran

* Corresponding author.

DOI: https://doi.org/10.5815/ijitcs.2013.01.02

Received: 3 Mar. 2012 / Revised: 10 Jul. 2012 / Accepted: 4 Sep. 2012 / Published: 8 Dec. 2012

Index Terms

Distributed System, Bidirectional Ring, Coordinator Election, Improvement of Ring Algorithm

Abstract

Nowadays use of distributed systems such as internet and cloud computing is growing dramatically. Coordinator existence in these systems is crucial due to processes coordinating and consistency requirement as well. However the growth makes their election algorithm even more complicated. Too many algorithms are proposed in this area but the two most well known one are Bully and Ring. In this paper we propose a fault tolerant coordinator election algorithm in typical bidirectional ring topology which is twice as fast as Ring algorithm although far fewer messages are passing due to election. Fault tolerance technique is applied which leads the waiting time for the election reaching to zero.

Cite This Paper

Danial Rahdari, Amir Masoud Rahmani, Afsane Arabshahi, "Fault Tolerant Message Efficient Coordinator Election Algorithm in High Traffic Bidirectional Ring Network", International Journal of Information Technology and Computer Science(IJITCS), vol.5, no.1, pp.15-25, 2013.DOI:10.5815/ijitcs.2013.01.02

Reference

[1]Y.Afek and A. Gafni, “Time and message bounds for election in synchronous and asynchronous complete networks,” in Proc. 4th Annu. ACM Symp. on Principles of Distributed Computing, Minaki, Canada, Aug. 1985, pp. 186-195.

[2]R. Gallager, P. Humblet and P. Spira, “A Distributed Algorithm for Minimum Weight Spanning Trees,” In ACM Transactions on Programming Languages and Systems,vol.4, no.1, pages 66-77, January 1983.

[3]N. Malpani, J. Welch and N. Vaidya, “Leader Election Algorithms for Mobile Ad Hoc Networks,” In Fourth International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications, Boston, MA, August 2000

[4]P. Basu, N. Khan and T. Little, “A Mobility based metric for clustering in mobile ad hoc networks,” In International Workshop on Wireless Networks and Mobile Computing,, April 2001 Page(s):658 – 663

[5]A. Obeidat and V. Gubarev. “Leader Election in peer to peer systems. Siberian conference on control and communications SIBCON-2009.

[6]N. Fredrickson and N. Lynch, “Electing a Leader in a Synchronous Ring.” J.ACM, 1987, vol.34, no.1, pp.98-115.

[7]H. Garcia Molina, “Elections in a Distributed Computing System. Y. Afek and A. Gafni, “Time and message bounds for election in synchronous and asynchronous complete networks,” in Proc. 4th Annu. ACM” IEEE Trans. Comp, 1982, vol.31, no. 1, pp.48-59.

[8]E. Chang and R. Roberts, “An improved algorithm for decentralized extrema finding in circular configurations of processes, ”Communications of the ACM}, pp. 281-283, 22,5, 1979.

[9]R. Bakhshi, W. Fokkink, J. Pang, and J. van de Pol. µCRL speciﬁcation of probabilistic Franklin leader election algorithm. http://www.few.vu.nl/~ rbakhshi alg/franklin.mcrl

[10]R. Bakhshi, W. Fokkink, J. Pang, and J. van de Pol.Leader. Election in Anonymous ring, Franklin Goes probabilistic, http://www.few.vu.nl/~ rbakhshi/ alg/franklin.mcrl

[11]L. Higham and S. Myers. Self-stabilizing token circulation on anonymous message passing. In Proc. 2nd Conf. on Principles of Distributed Systems, pages 115– 128z Hermes, 1998.

[12]J. Burns and J. Pachl. Uniform self-stabilizing rings. ACM Trans. Program. Lang. Systems, 11(2):330–344, 1989.

[13]F. Fich and C. Johnen. A space optimal, deterministic, self-stabilizing, leader election algorithm for unidirectional rings. In Proc. 15th Conf. on Distribute Computing, volume 2180 of LNCS, pages 224–239. Springer, 2001. S.-T. Huang. Leader election in uniform rings. ACM Trans. Program. Lang. Systems, 15(3):563–573, 1993.

[14]M. Zargarnataj, “New Election Algorithm based on Assistant in Distributed Systems”IEEE 2007.

[15]M. EffatParvar, MR.Effatparvar, A.Bemana and M.Dehghan” Determining a Central Controlling Processor with Fault Tolerant Method in Distributed System”, ITNG apos;07, 2-4 April 2007 Page(s):658 – 663.

[16]M. Shirali, A.Hagighattoroghi and M.Vojdani. “Leader Election Algorithms: History and Novel Schemes” ICCIT 2008.57, pp.1001-1006

[17]M. Gholipour,M.S.Kordafshari,M.Jahanshahi and A.M.Rahnami.“A new approach for election algorithm in distributed systems”.CTRQ 2009.32, pp 70-74.

[18]R. Ingram,P.Shield,J.E.Walter,J.L.Welch. “An asynchronous leader election algorithm for dynamic networks”.IEEE 2009

[19]J. E. Burns. “A formal model for message passingsystems,” Tech. Rep. TR-91, Indiana University, Sep. 1980

[20]D. Dolev, M. Klawe, and M. Rodeh, “An O(nlogn) unidirectional distributed algorithm for extrema finding in a circle,” Journal of Algorithms, vol. 3, no. 3, pp. 245-260,Sep. 1982.

[21]G. Fredrickson and N. Lynch, “The impact of synchronous communication on the problem of electing a leader in a ring,” in Proc. 16th Annu. ACM Symp. onTheory of Computing, Washington, D.C., 1984, pp. 493-503.

[22]M. R.Effatparvar, N.Yazdani, M.Effatparvar, A.Dadlani, A.Khonsari. “Improved Algorithm for Leader Election in Distributed Systems”. 2nd international conference on computer engineering and technology. 2010.

[23]Y. Xie, Hong.L. “A BI-directional Election Algorithm based on Ring Topology”. International conference on information science and technology. March 26-28, 2011 Nanjing Jiangsu, China

International Journal of Information Technology and Computer Science (IJITCS)