توسعه الگوریتم بولی اصلاح‌شده جهت حذف پدیده افزونگی انتخابات در انتخاب هماهنگ‌کننده در سیستم‌های توزیع‌شده

نویسنده
رضا نورمندی‌پور
استادیار، دانشکده فنی و مهندسی، واحد سیرجان، دانشگاه آزاد اسلامی، سیرجان، ایران
چکیده
در سیستم‌های توزیع‌شده که دارای فرایندها و منابع متعددی هستند، همگام‌سازی فرایندها برای برخی مسائل نظیر ورود به ناحیه بحرانی و استفاده از منابع مشترک امری اجتناب‌ناپذیر است. فرایند هماهنگ‌کننده نقش کلیدی را برای همگام‌سازی فرایندها ایفا می‌کند. بنابراین، انتخاب هماهنگ‌کننده یکی از مسائل مهم نه‌تنها در سیستم‌های توزیع‌شده بلکه در بسیاری از زمینه‌ها نظیر شبکه‌های ارتباطی، الگوریتم‌های انحصار متقابل، تخصیص منابع مشترک و غیره است. یکی از چالش‌های موجود در الگوریتم‌های انتخاب هماهنگ‌کننده کاهش پیام‌ها بین فرایندها است که تأثیر زیادی بر روی میزان ترافیک شبکه خواهد داشت. هرچند تلاش‌های زیادی در کاهش پیام‌ها بین فرایندها صورت گرفته است، ولی همچنان پدیده افزونگی انتخابات یکی از محدودیت‌هایی است که الگوریتم‌های انتخاب هماهنگ‌کننده با آن مواجه هستند. ایده اصلی در این مقاله ارائه رویکردهایی نوین در توسعه الگوریتم بولی اصلاح‌شده است با این هدف که پدیده افزونگی انتخابات در انتخاب هماهنگ‌کننده حذف شود. با بکارگیری این رویکردها در توسعه الگوریتم بولی اصلاح‌شده نه‌تنها پیچیدگی پیامی برابر‌ (O(n حفظ شده است، بلکه تضمین می‌کنند که تنها یک فرایند درگیر انتخابات شود که این باعث حذف پدیده افزونگی انتخابات و درنتیجه باعث کاهش ازدحام و ترافیک شبکه می‌شود.

کلیدواژه‌ها

  • [1] G. L. Lan, ”Distributed System–Towards a Formal Approach”‚ IFIP world congress, pp.155-160, 1977.
  • [2] E. J. Chang, R. Roberts, “An improved algorithm for the decentralized extrima-finding in circular configurations of processes‚” Communication of ACM, vol. 22, no.5, pp. 281- 283, 1979.
  • [3] H. Garcia-Molina, “Elections in Distributed Computing System”‚ IEEE Transaction on Computer, vol. 31,no.1, pp. 48-59, 1982.
  • [4] M. M. Rahman, A. Nahar, “Modified Bully Algorithm using Election Commission”, Journal of Computing, vol. 1 no.3, pp. 439-446, 2009.
  • [5] A. Arghavani, E. Ahmadi, A. T. Haghighat, “Improved Bully Election Algorithm in Distributed Systems”, proceedings of the 5th international conference on information technology & multimedia, pp. 1-6, 2011.
  • [6] R. Gajre, L. Ragha, “Optimized Bully Election Method for Selection of Coordinator Process and Recovery of Crashed Process”, International Journal of Scientific and Research Publications, vol 3, no. 5, pp. 1-4, 2013.
  • [7] A. Datley, B. Patel, S. Soni, “Amelioration on Coordinator Election Algorithm in synchronous distributed system”, International Journal of Engineering Research & Technology, vol. 2, no 11, pp. 2375-2378, 2013.
  • [8] M. S. Kordafshari, M. Gholipour, M.Jahanshahi, A.T. Haghighat, “Modified bully election algorithm in distributed system”, WSEAS Conferences, Cancun, Mexico, pp.11-14, 2005.
  • [9] A. Silberschatz, P. Galvin, Operating Systems Concetsp ‚4th EditionWesley publishing, 1994.
  • [10] Q. E. K. Mamun, S. M. Masum, “Modified Bully Algorithm for electing coordinator in distributed system”‚ proceedings of 3rd international conference on software Engineering, parallel & distributed system, pp.13-15, 2004.
  • [11] P. D. Bhute, “A New Approach for Electing a Coordinator in Anonymous System”, International Journal of Computer Science and Information Technologies, vol. 5, no. 3, pp. 3883-3886, 2014.
  • [12] M. Al Refai, “Dynamic Leader Election Algorithm in 2D Torus Network with Multi Links Failure”, International Journal of Computer Science Trends and Technology, vol. 2, no. 5, pp. 150-156, 2014.
  • [13] M. Gholipour, M. S. Kordafshari, M. Jahanshahi, A. M. Rahmani, “A New Approach For Election Algorithm in Distributed Systems”, Second International Conference on Communication Theory, Reliability, and Quality of Service, pp.70-74, 2009.
  • [14] P.K. Sinha, Distributed Operating Systems Concepts and Design, Prentice-Hall of India private Limited, 2008.
علوم رایانش و فناوری اطلاعات
دوره 17، شماره 2
پاییز و زمستان
پاییز 1398