Abstract
A leader election protocol for timed asynchronous distributed systems is presented. The proposed scheme is based on reliable multicast where all participating processes of the group will receive protocol messages. In this protocol, the group members do not need to know each other’s addresses to communicate. Also, they do not have to make any reconfiguration if some members crash, join or leave the group. The paper describes the proposed protocol, estimates its performance in simulation and compares this simulation with an analytical model. It is found that the communication complexity of the protocol is of O(N). As simulation formalism, a class of extended Petri nets was used.
This is a preview of subscription content, log in via an institution to check access.
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
Garcia-Molina, H.: Elections in a Distributed Computing System. IEEE Transaction on Computers 31(1), 47–59 (1982)
Itai, A., Kutten, S., Wolfstahl, Y., Zaks, S.: Optimal Distributed t-Resilient Election in Complete Networks. IEEE Trans. on software Engineering 16(4), 415–420 (1990)
Li, V.O.K., Zhang, Z.C.: Internet multicast routing and transport control protocols. Proc. IEEE 90(3), 360–391 (2002)
Donahoo, M.J., Ainapure, S.R.: Scalable multicast representative member selection. In: Proc. IEEE Infocom, March 2001, pp. 259–268 (2001)
Cidon, I., Mokryn, O.: Propagation and Leader Election in a Multihop Broadcast Environment. In: Kutten, S. (ed.) DISC 1998. LNCS, vol. 1499, pp. 104–118. Springer, Heidelberg (1998)
Kostin, A., Ilushechkina, L.: Winsim: A Tool for Performance Evaluation of Parallel and Distributed Systems. In: Yakhno, T. (ed.) ADVIS 2004. LNCS, vol. 3261, pp. 312–321. Springer, Heidelberg (2004)
Banks, J., Carson, J.S., Nelson, B.L., Nicol, D.M.: Discrete- Event System Simulation, 3rd edn. Prentice-Hall, Englewood Cliffs (2001)
Amintabar, A., Kostin, A., Ilushechkina, L.: Simulation of a Novel Leader Election Protocol with the Use of Petri Nets. In: 9th IEEE International Symposium on Distributed Simulation and Real-time Applications (DS-RT) Canada, pp. 283–289 (2005)
Cristian, F., Fetzer, C.: The timed asynchronous distributed system model. IEEE Transactions on Parallel and Distributed Systems 10(6), 642–657 (1999)
Raz, D., Shavitt, Y., Zhang, L.: Distributed council election. IEEE/ACM Transactions on Networking 12(3), 483–492 (2004)
Vasudevan, S., DeCleene, B., Immerman, N., Kurose, J., Towsley, D.: Leader Election Algorithms for Wireless Ad Hoc Networks. In: Proceedings of the DARPA Information Survivability Conference and Exposition (DISCEX 2003), vol. 1, pp. 261–273. IEEE, Los Alamitos (2003)
Singh, G.: Leader Election in the Presence of Link Failures. IEEE Transactions on Parallel and Distributed Systems 7(3), 231–236 (1996)
Nakano, K., Olariu, S.: A Survey on Leader Election Protocols for Radio Networks. In: International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN 2002), May 2002, pp. 71–76 (2002)
Yamashita, M., Kameda, T.: Leader Election Problem on Networks in which Processor Identity Numbers Are Not Distinct. IEEE Transactions on Parallel and Distributed Systems 10(9), 878–887 (1999)
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
Amintabar, A., Kostin, A., Ilushechkina, L. (2006). A Leader Election Protocol for Timed Asynchronous Distributed Systems. In: Levi, A., Savaş, E., Yenigün, H., Balcısoy, S., Saygın, Y. (eds) Computer and Information Sciences – ISCIS 2006. ISCIS 2006. Lecture Notes in Computer Science, vol 4263. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11902140_91
Download citation
DOI: https://doi.org/10.1007/11902140_91
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-47242-1
Online ISBN: 978-3-540-47243-8
eBook Packages: Computer ScienceComputer Science (R0)