Bully Algorithm for Election in Distributed Systems
Abstract
One of the most indispensable circumstances that distributed systems encounter is an inconvenience and delay in the leader process, however, electing an authoritative leader is the imperative procedure for recovering from partial failure and continuing to perform the goal without any repercussions for main duties until a proper redress has been accomplished. Therefore, this paper aims to investigate and resolve the problem of the coordinator's failure with full interaction of message passing. However, for these spectacular distinguishing features of fault tolerance; the study utilized the bully algorithm with modern techniques of the PVM (Parallel Virtual Machine) software to think through this issue. The purpose of this, is choosing a new process with the highest number of coordinators, as PVM tool is mainly designed to be employed by a concurrent and heterogeneous environment, particularly, the possibility of providing a virtual view.
The implementation section shows the simulation of communication failure and the program testing steps. A clear description of the interaction of executed messages for all nodes is given. The proposed algorithm has been achieved and yielded varied outcomes, including full topology architecture with free crush during the election operations; moreover, the election algorithm has successfully elected the leader, the node which containing the highest figure. The source code program documentation was illustrated; as well as the entire PVM simulations of casting communications. The algorithm’s ambiance has been written in the C language, which supports concurrent computers and UNIX environment on Clusters Systems.
Keywords:
Election Algorithms
Bully Algorithm
Distributed Systems
Parallel Virtual Machine
Concurrent Computers
Heterogeneous Environment
How to Cite
Amer Saleh Musbah Gadowa. (2024). Bully Algorithm for Election in Distributed Systems . Bani Waleed University Journal of Humanities and Applied Sciences, 9(5), 538-555. https://doi.org/10.58916/jhas.v9i5.635
Issue
Section
Articles
References
1.
Andrea, C. (2001). Implicit Co-scheduling: Coordinated Scheduling with Implicit information in Distributed Systems. ACM Transactions on Computer Systems, 19(3), 283–331.
2.
Basim, A., Laith, H., Mohammed, H. & Mohammed A. (2013). Reducing Massage Passing and Time Complexity in Bully Election Algorithms Using Two Successors. International Journal of Electronics and Electrical Engineering, 1(1), 1-4.
3.
Basu, S. (2011). An efficient approach of election algorithm in distributed systems. Indian Journal of Computer Science and Engineering (IJCSE), 2(1), 16-21.
4.
Ben-Ari, M. (2006). Principles of Concurrent and Distributed Programming. 2nd ed. USA: Addison-Wesley.
5.
Biswas, A., Tripathi, K. & Aknine, S. (2021). Lea-TN: leader election algorithm considering node and link failures in a torus network. The Journal of Supercomputing, 77, 13292-13329
6.
Chang, E. & Roberts, R. (1979). An improved algorithm for Decentralized extrema-finding in circular configurations of processes. Communications of the ACM, 22(5), 281-283.
7.
Chen, Z., Gul, M. & Kantarci, B. (2023). Practical byzantine fault tolerance-based robustness for mobile crowdsensing. Distributed Ledger Technologies: Research and Practice, 2(2), 1-24.
8.
Coulouris, G., Dollimore, J. & Kindberg, T. (2005). Distributed Systems Concepts and design. 4th ed. USA: Addison Wesley.
9.
Daymude, J., Gmyr, R., Richa, W., Scheideler, C. & Strothmann, T. (2017). Improved leader election for self-organizing programmable matter. In Algorithms for Sensor Systems: 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, Vienna, Austria, 127-140.
10.
Frans, M. Kaashoek (1992). PHD Thesis: Group communication in Distributed Computer Systems.
11.
Geist, Al., Beguelin, A., Dongarra, J., Jiang, W., Manchek, R., & Sunderam, V. (1994). PVM: Parallel Virtual Machine – A users’ Guide and Tutorial for Networked Parallel Computing. USA: The MIT press- Massachusetts Institute of Technology.
12.
Grama, A. Gupta, A., Karypis, G. & Kumar, V. (2003). Introduction to Parallel Computing. 2nd edition. USA: PEARSON Addison-Wesley.
13.
Hector, G. (1982). Election in a Distributed Computing System. IEEE Transactions on Computers, C-31 (1), 48-59.
14.
Index for PVM3 Library (n.d.). Retrieved from: http://www.netlib.org/pvm3/
15.
Kordafshari, S., Gholipour, M., Jahanshahi & Haghighat, T. (2005). Modified Bully Election Algorithm in Distributed Systems. Department of Electrical, Computer & IT, Islamic Azad University, Qazvin Branch, Atomic Energy Organization of Iran (AEOI), NPPD, Tehran, Iran.
16.
Kutten, S., Pandurangan, G., Peleg, D., Robinson, P. & Trehan, A. (2015). On the complexity of universal leader election. Journal of the ACM (JACM), 62(1), 1-27.
17.
Marc, B. (2019). Leader election in distributed systems. Amazon Web Services. Retrieved from: https://d1.awsstatic.com/builderslibrary/pdfs/leader-election-in-distributed-systems.pdf
18.
Ozalp, B., & Andre, S. (1995). On Group Communication in Large-Scale Distributed Systems. SIGOPS Operating Systems Review, 29 (1).
19.
Peterson, L. (1982). An O(nlogn) Unidirectional Algorithm for Circular Extrema Problem. ACM Transaction on Programming Language and systems, 4(4), 758-762.
20.
PVM Home Page. (n.d.). Retrieved from: http://www.csm.ornl.gov/pvm/
21.
Quazi, M., Salahuddin, M., & Mohammad, M. (2004). Modified Bully Algorithm for Electing Coordinator in Distributed Systems. The 3rd WSEAS International Conference on Software Engineering, Parallel and Distributed Systems.
22.
Rafailescu, M. (2017). Fault-tolerant leader election in distributed systems. International Journal of Computer Science and Information Technology, 9(1), 13-20
23.
Rahman, M., & Nahar, A. (2009). Modified Bully Algorithm using Election Commission. MASAUM Journal of Computing, 1(3).
24.
Refai, M., Sharieh, A. & Alshammari, F. (2010). Leader Election Algorithm in 2D Torus Networks with the Presence of One Link Failure. The International Arab Journal of Information Technology, 7(2).
25.
Refai, M. & Naim M., A. (n.d.). Leader Election Algorithm in Hypercubes with the Presence of One Link Failure. Amman Arab University for Graduate Studies.
26.
Riccardo, G. & Stefano Z. (1985). An Election Algorithm for a Distributed Clock Synchronization Program. University of California: Report No. UCB/CSD 86/275.
27.
Sanjay, G., Howard, G. & Shunk-Tak, L. (2003). The Google File System. ACM SIGOPS Operating Systems Review. 37(5), 29-43.
28.
Scalable Computing Laboratory (n.d.). Retrieved from: http://www.scl.ameslab.gov
29.
Scott, S. (1999). Leader Election in Asynchronous Distributed Systems. Computer Science Department, Indiana University, Bloomington, IN 47405, USA.
30.
Seema, B. & Kavita K. (2014). Leader Election Algorithms in Distributed Systems. International Journal of Computer Science and Mobile Computing, 3(6), 374-379
31.
Sergey, B. & Lawrence, P. (n.d.). The Anatomy of a Large-Scale Hyper textual Web Search Engine. Computer Science Department, Stanford University. Retrieved from: http://infolab.stanford.edu/~backrub/google.html
32.
Shital, S. & Jayshree, P. (2023). A Robust, Preference-Based Coordinator Election Algorithm for Distributed Systems. International Information and Engineering Technology Association, 28(4), 843-851.
33.
Singh, G. (1992). Leader Election in Complete Networks. Department of Computing and Information Sciences, Kansas State University, Manhattan, KS 66506.
34.
Supase, S. & Ingle, B. (2021). A novel algorithm for secure and reliable coordinator election in distributed networks. International Journal of Advanced Technology and Engineering Exploration, 8(85), 1682-1694
35.
Supase, S. & Ingle, B. (2020). Are coordinator election algorithms in distributed systems vulnerable. In 11th International Conference on Computing, Communication and Networking Technologies (ICCCNT), 1-5
36.
Tanenbaum, A. & Van, M. (2007). Distributed Systems Principles and Paradigms. 4th ed. USA: Pearson Prentice Hall.
37.
The Spider’s Apprentice: Search Engine Ranking Algorithms. (n.d.). Retrieved from: http://www.monash.com/spidap4.html
38.
Wei S., Bouabdalla, A. & Pradip, S. (2005). Leader Election in Oriented Star Graphs. Networks, 45, 169-179.
39.
Wm, F. (1982). On an improved Algorithm for decentralized Extrema Finding in Circular Configurations of Processors. ACM Communication, 25(5), 336-337.
40.
Yann, L., Collet, P., Prost, T. & Lutton, E. (2003). Introducing Lateral Thinking in Search Engines with Interactive Evaluation Algorithm. ACM symposium on Applied Computing, 1-58113
