Abstract

Leader election is the most critical part of any distributed system and also challenging one. By optimizing the performance of leader election, performance of system can be improved. There is already number of algorithms but in this paper there is a proposal of a new Leader Election algorithm for synchronous ring. In this proposal we are trying to tradeoff among time, message and space complexity. By adding new concept Adoption we can proposed a new ring algorithm which performs better as compare to original classic HS algorithm for ring.

References

• Princy Francis and Sanjeev Saxena ,IEEE conference ,1998,Optimal Distributed Leader Election Algorithm For Synchronous complete Network .
• Mohammad Reza EffatParvar , Nasser Yazdani, Mehdi EffatParvar , Aresh Dadlani and Ahmad Khonsari,IEEE conference,2010, Improved Algorithms for Leader Election in Distributed Systems .
• Vandana Sharma, Parvinder S. Sandhu, Satwinder Singh, and Baljit Saini, World Academy of Science, Engineering and Technology 42, 2008,Analysis of Modified Heap Sort Algorithm on Different Environment
• Xio Dong Wang, Ying Jie Wu, Journal of Computer Science and Technology. 22(6): 898-903 An improved heap sort algorithm with nlogn –0. 788928n comparisons in worst case
• McDiarmid C J H, Journal of Algorithms, 1989, 10(3): 352~365,Reed B A. Building Heaps Fast.
• H. Gracia-Molina, IEEE Trans. on Computers, vol. C-31, no. 1, Jan. 1982 "Elections in a distributed computing system"
• N. Fredrickson and N. Lynch,Journal of ACM, vol. 34, no. 1, pp. 98-115", 1987 "Electing a leader in a synchronousring"
• E. Chang and R. Roberts, Communications of the ACM, vol. 22, no. 5, pp. 281-283, May 1979 "An improved algorithm for decentralized extrema-finding in circular configurations of processes".
• G. L. Peterson, ACM Trans. Programming Languages and Systems, pp. 758-762, Oct. 1982 "An O(n log n) unidirectional algorithm for the circular extrema problem".
• G. LeLann, Information Processing Letters, pp. 155-160, 1977 "Distributed systems - towards a formal approach".
• W. R. Franklin, Communication of the ACM, pp. 336-337, 1982 "On an improved algorithm for Misra and Kate N. Nagaraj,"Security in Wireless Ad Hoc
• H. GaFcia-Molina. " IEEE Trans. on Computers, Vol C-31, Jan 1982, 48-59 "Elections in a Distributed Computing System"
• G. Fredrickson and N. Lynch, in Proc. 16th ACM Symp. on Theory of Computing, Washington, USA, pp. 493-503, 1984 "The impact of synchronous communication on the problem of electing a leader in a ring"
• E. Korach, S. Moran, and S. Zaks, in Proc. 3rd ACM Symp. on Principles of Distributed Computing, Vancouver, Canada, pp. 199-207,Aug. 1984, "Tight lower and upper bounds for some distributed algorithms for a complete network of processors".
• Gonnet G H, Munro J I, 1986, 15(6): 964-971, Heaps on Heaps. SIAM Journal on Computing.
• P. M. B. Vitanyi, "Distributed election in an Archimedean ring of processors", USA, pp. 542-547, 1984,in Proc. 16th ACM Symp. on Theory of Computing, Washington
• Thomas H. Cormen,Charles E. Leiserson, Ronald L. Rivest, Clifford Stein,"Introduction to Algorithms,Second Edition"