A Comprehensive Review of Self-stabilization Algorithm and Its Applications in Wireless Networks
Keywords:
Self-stabilization algorithm, FT, convergence,self-stabilizing time, distributed systems.
Abstract
Distributed computing is a field of the vast computer science that deals with distributed systems. These systems have a significant role in computing with high efficiency. One of the important cases with a great role in distributed systems is the self-stabilizing concept. One of the new algorithms with a critical role in engineering and computer science is self-stabilization algorithm. This algorithm is known as a lightweight and convenient property relative to other classic solutions and methods of fault tolerance in obtaining fault tolerance (FT). Moreover, in terms of time and space, the art of this algorithm is that it needs less time and space. These features have made the self-stabilization algorithm highly promising for use in distributed systems that are equipped with low computing and low memory processes.
References
[1] Edsger W. Dijkstra., “Self-stabilization in spite of distributed control.” , Technical
Report EWD 391, University of Texas, 1973. Published in 1982 as Selected Writings on Computing: A Personal Perspective, Springer-Verlag, OPT.
[2] Gerard Tel, “Introduction to Distributed Algorithms” , 2nd ed., Cambridge University
Press, 2001.
[3] Shlomi Dolev, “Self-Stabilization” , MIT Press, 2000.
[4] Sébastien Tixeuil, “Toward Self-Stabilizing Large-Scale Systems”, Habilitation à
diriger des recherches, Université Paris Sud - Paris XI, 2006. 4
[5] Chi-Hung Tzeng, Jehn-Ruey Jiang, and Shing-Tsaan Huang, ”Size-independent self-stabilizing asynchronous phase synchronization in general graphs”, Journal of Information Science and Engineering, 26(4):1307–1322, 2010
[6] Binh-Minh Bui-Xuan, Afonso Ferreira, and Aubin Jarry, “Computing shortest, fastest, and foremost journeys in dynamic networks”, International Journal of Foundations of Computer Science, 14(2):267–285, 2003
[7] Jeffrey O. Kephart and David M. Chess, “The vision of autonomic computing” ,Computer, 36(1):41-50, 2003
(8] Markus C. Huebscher and Julie A. McCann. “A survey of autonomic computing:Degrees, models, and applications.” , ACM Computing Surveys, 40(3):1–28, 2008.
[9] Ted Richard Herman, “ Adaptivity through distributed convergence” , Ph.D. thesis,University of Texas at Austin, 1992.
[10] Ajoy K. Datta, Eugene Outley, Visalakshi Thiagarajan, and Mitchell Flatebo,” Stabilization of the x.25 connection management protocol” , International Conference on Computing and Information (ICCI), pages 1637-1654, 1994
[11] Yu Chen, Ajoy K. Datta, and Sébastien Tixeuil, “Stabilizing inter-domain routing in the internet”, Journal of High Speed Networks, 14(1):21-37, 2005
[12] Shlomi Dolev, Mohamed G. Gouda, and Marco Schneider., “Memory requirements for silent stabilization.”, Acta Informatica, 36(6):447--462, 1999
[13] Sukumar Ghosh., “Distributed Systems: An Algorithmic Approach.”, 2nd ed., Chapman& Hall/CRC, 2014
[14] Shlomi Dolev, Amos Israeli, and Shlomo Moran., “Self-stabilization of dynamic systems assuming only Read/Write atomicity.”, Distributed Computing, 7(1):3–16, 1993
[15] Alain Cournier, Ajoy K. Datta, Franck Petit, and Vincent Villain., “Snap stabilizing PIF algorithm in arbitrary networks. “, Proc. of the 22nd International Conference on Distributed Computing Systems (ICDCS), pages 199–206, 2002.
[16] Alain Bui, Ajoy K. Datta, Franck Petit, and Vincent Villain., “ State-optimal snap-stabilizing PIF in tree networks.”, Anish Arora, Ed., Workshop on Self-stabilizing Systems, pages 78–85, IEEE Computer Society, 1999
[17] Ted Richard Herman., “ Adaptivity through distributed convergence.” , Ph.D. thesis, University of Texas at Austin, 1992.
[18] Colette Johnen., “ Memory efficient, self-stabilizing algorithm to construct BFS spanning trees.” , James E. Burns and Hagit Attiya, Eds., Proc. of the 16th Annual ACM Symposium on Principles of Distributed Computing, page 288, 1997
[19] Mohamed G. Gouda and Nicholas J. Multari., “ Stabilizing communica tion protocols.”, IEEE Transactions on Computers, 40(4):448-458, 1991
[20] Yehuda Afek and Anat Bremler-Barr., “ Self-stabilizing unidirectional network algorithms by power supply.”, Chicago Journal of Theoretical Computer Science, 1998.
[21] Edsger W. Dijkstra., “ Self-stabilizing systems in spite of distributed control.”, Communications of the ACM, 17(11):643–644, 1974.
[22] Mohamed G. Gouda and Ted Herman., “ Stabilizing unison.”, Information Processing Letters, 35(4):171-175, 1990
[23] Alain Cournier, Ajoy K. Datta, Stéphane Devismes, Franck Petit, and Vincent Villain., “ The expressive power of snap-stabilization.”, Theoretical Computer Science, 626:40–66, 2016
[24] Shmuel Katz and Kenneth J. Perry., “ Self-stabilizing extensions for message-passing systems.”, Distributed Computing, 7(1):17–26, 1993
[25] Lélia Blin, Maria Potop-Butucaru, Stéphane Rovedakis, and Sébastien Tixeuil., “Loop-free super-stabilizing spanning tree construction.” ,In Proc. of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 50–64, Springer LNCS 6366, 2010
[26] Shing-Tsaan Huang and Nian-Shing Chen., “ Self-stabilizing depth-first token circulation on networks.”, Distributed Computing, 7(1):61-66, 1993
[27] Alain Bui, Ajoy K. Datta, Franck Petit, and Vincent Villain., “ Optimal PIF in tree networks.”, The 2nd International Meeting on Distributed Data and Structures 2 (WDAS), pages 1-16, 1999. 8, 47
[28] Alain Cournier, Swan Dubois, Anissa Lamani, Franck Petit, and Vincent Villain., “The snap-stabilizing message forwarding algorithm on tree topologies.”, Theoretical Computer Science, 496:89–112, 2013
[29] Bertrand Ducourthial and Sébastien Tixeuil., “ Self-stabilization with r-operators.” ,Distributed Computing, 14(3):147-162, 2001
[30] Jorge A. Cobb and Mohamed G. Gouda., “ Stabilization of routing in directed networks.”,The 5th International Workshop on Self-Stabilizing Systems (WSS), pages 51–66, Springer LNCS 2194, Springer Berlin Heidelberg, 2001
[31] Ajoy K. Datta, Shivashankar Gurumurthy, Franck Petit, and Vincent Villain., “Self-stabilizing network orientation algorithms in arbitrary rooted networks.” ,Studia Informatica Universalis, 1(1):1-22, 2001
[32] Shing-Tsaan Huang and Nian-Shing Chen., “ Self-stabilizing depth-first token circulation on networks.” , Distributed Computing, 7(1):61-66, 1993
[33] Shing-Tsaan Huang, Tzong-Jye Liu, and Su-Shen Hung., “ Asynchronous phase synchronization in uniform unidirectional rings.”, IEEE Transactions on Parallel and Distributed Systems, 15(4):378–384, 2004
[34] Shing-Tsaan Huang and Nian-Shing Chen., “ Self-stabilizing depth-first token circulation on networks.” , Distributed Computing, 7(1):61–66, 1993
[35] Carole Delporte-Gallet, Stéphane Devismes, and Hugues Fauconnier., “Stabilizing leader election in partial synchronous systems with crash failures.”, Journal of Paralla! and Distributed Computing, 70(1):45–58, 2010
[36] Toshimitsu Masuzawa and Hirotsugu Kakugawa., “ Self-stabilization in spite of frequent changes of networks: Case study of mutual exclusion on dynamic rings.” ,In Ted Herman and Sébastien Tixeuil, Eds., Self-Stabilizing Systems, 7th International Symposium, (SSS), Proceedings, volume 3764 of Lecture Notes in Computer Science, pages 183–197, Springer, Barcelona, Spain, October 26–27, 2005
[37] Lélia Blin and Sébastien Tixeuil., “ Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative.”, Distributed Computing, 31(2):139-166, 2018
[38] Pranay Chaudhuri and Hussein Thompson., “ Improved self-stabilizing algorithms for 1(2, 1)-labeling tree net urks.”, Mathematics in Computer Science, 5(1):27–39, 2011
[39] Volker Turau and Sven Köhler., “ A distributed algorithm for minimum distance-k domination in trees.” , Journal of Graph Algorithms and Applications, 19(1):223–242
[40] Ajoy K. Datta, Stéphane Devismes, Lawrence L. Larmore, and Vincent Villain., “ Self-stabilizing weak leader election in anonymous trees using constant memory per edge.”, Parallel Processing Letters, 27(2):1-18, 2017
[41] Sukumar Ghosh and Mehmet Hakan Karaata., “ A self-stabilizing algorithm for coloring planar graphs.”, Distributed Computing, 7(1):55-59, 1993
[42] Ji-Cherng Lin and Ming-Yi Chiu., “ A fault-containing self-stabilizing algorithm for 6-coloring planar graphs.”, Journal of Information Science and Engineering, 26(1):163-181, 2010
[43] Ajoy K. Datta, Colette Johnen, Franck Petit, and Vincent Villain., “ Self-stabilizing depth-first token circulation in arbitrary rooted networks.”,Distributed Computing, 13(4):207–218, 2000
[44] Stéphane Devismes, Swan Dubois, and Franck Petit., “ Introduction to Distributed Self-Stabilizing Algorithms.”, Karine Altisen,Copyright © 2019 by Morgan & Claypool
Report EWD 391, University of Texas, 1973. Published in 1982 as Selected Writings on Computing: A Personal Perspective, Springer-Verlag, OPT.
[2] Gerard Tel, “Introduction to Distributed Algorithms” , 2nd ed., Cambridge University
Press, 2001.
[3] Shlomi Dolev, “Self-Stabilization” , MIT Press, 2000.
[4] Sébastien Tixeuil, “Toward Self-Stabilizing Large-Scale Systems”, Habilitation à
diriger des recherches, Université Paris Sud - Paris XI, 2006. 4
[5] Chi-Hung Tzeng, Jehn-Ruey Jiang, and Shing-Tsaan Huang, ”Size-independent self-stabilizing asynchronous phase synchronization in general graphs”, Journal of Information Science and Engineering, 26(4):1307–1322, 2010
[6] Binh-Minh Bui-Xuan, Afonso Ferreira, and Aubin Jarry, “Computing shortest, fastest, and foremost journeys in dynamic networks”, International Journal of Foundations of Computer Science, 14(2):267–285, 2003
[7] Jeffrey O. Kephart and David M. Chess, “The vision of autonomic computing” ,Computer, 36(1):41-50, 2003
(8] Markus C. Huebscher and Julie A. McCann. “A survey of autonomic computing:Degrees, models, and applications.” , ACM Computing Surveys, 40(3):1–28, 2008.
[9] Ted Richard Herman, “ Adaptivity through distributed convergence” , Ph.D. thesis,University of Texas at Austin, 1992.
[10] Ajoy K. Datta, Eugene Outley, Visalakshi Thiagarajan, and Mitchell Flatebo,” Stabilization of the x.25 connection management protocol” , International Conference on Computing and Information (ICCI), pages 1637-1654, 1994
[11] Yu Chen, Ajoy K. Datta, and Sébastien Tixeuil, “Stabilizing inter-domain routing in the internet”, Journal of High Speed Networks, 14(1):21-37, 2005
[12] Shlomi Dolev, Mohamed G. Gouda, and Marco Schneider., “Memory requirements for silent stabilization.”, Acta Informatica, 36(6):447--462, 1999
[13] Sukumar Ghosh., “Distributed Systems: An Algorithmic Approach.”, 2nd ed., Chapman& Hall/CRC, 2014
[14] Shlomi Dolev, Amos Israeli, and Shlomo Moran., “Self-stabilization of dynamic systems assuming only Read/Write atomicity.”, Distributed Computing, 7(1):3–16, 1993
[15] Alain Cournier, Ajoy K. Datta, Franck Petit, and Vincent Villain., “Snap stabilizing PIF algorithm in arbitrary networks. “, Proc. of the 22nd International Conference on Distributed Computing Systems (ICDCS), pages 199–206, 2002.
[16] Alain Bui, Ajoy K. Datta, Franck Petit, and Vincent Villain., “ State-optimal snap-stabilizing PIF in tree networks.”, Anish Arora, Ed., Workshop on Self-stabilizing Systems, pages 78–85, IEEE Computer Society, 1999
[17] Ted Richard Herman., “ Adaptivity through distributed convergence.” , Ph.D. thesis, University of Texas at Austin, 1992.
[18] Colette Johnen., “ Memory efficient, self-stabilizing algorithm to construct BFS spanning trees.” , James E. Burns and Hagit Attiya, Eds., Proc. of the 16th Annual ACM Symposium on Principles of Distributed Computing, page 288, 1997
[19] Mohamed G. Gouda and Nicholas J. Multari., “ Stabilizing communica tion protocols.”, IEEE Transactions on Computers, 40(4):448-458, 1991
[20] Yehuda Afek and Anat Bremler-Barr., “ Self-stabilizing unidirectional network algorithms by power supply.”, Chicago Journal of Theoretical Computer Science, 1998.
[21] Edsger W. Dijkstra., “ Self-stabilizing systems in spite of distributed control.”, Communications of the ACM, 17(11):643–644, 1974.
[22] Mohamed G. Gouda and Ted Herman., “ Stabilizing unison.”, Information Processing Letters, 35(4):171-175, 1990
[23] Alain Cournier, Ajoy K. Datta, Stéphane Devismes, Franck Petit, and Vincent Villain., “ The expressive power of snap-stabilization.”, Theoretical Computer Science, 626:40–66, 2016
[24] Shmuel Katz and Kenneth J. Perry., “ Self-stabilizing extensions for message-passing systems.”, Distributed Computing, 7(1):17–26, 1993
[25] Lélia Blin, Maria Potop-Butucaru, Stéphane Rovedakis, and Sébastien Tixeuil., “Loop-free super-stabilizing spanning tree construction.” ,In Proc. of the 12th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 50–64, Springer LNCS 6366, 2010
[26] Shing-Tsaan Huang and Nian-Shing Chen., “ Self-stabilizing depth-first token circulation on networks.”, Distributed Computing, 7(1):61-66, 1993
[27] Alain Bui, Ajoy K. Datta, Franck Petit, and Vincent Villain., “ Optimal PIF in tree networks.”, The 2nd International Meeting on Distributed Data and Structures 2 (WDAS), pages 1-16, 1999. 8, 47
[28] Alain Cournier, Swan Dubois, Anissa Lamani, Franck Petit, and Vincent Villain., “The snap-stabilizing message forwarding algorithm on tree topologies.”, Theoretical Computer Science, 496:89–112, 2013
[29] Bertrand Ducourthial and Sébastien Tixeuil., “ Self-stabilization with r-operators.” ,Distributed Computing, 14(3):147-162, 2001
[30] Jorge A. Cobb and Mohamed G. Gouda., “ Stabilization of routing in directed networks.”,The 5th International Workshop on Self-Stabilizing Systems (WSS), pages 51–66, Springer LNCS 2194, Springer Berlin Heidelberg, 2001
[31] Ajoy K. Datta, Shivashankar Gurumurthy, Franck Petit, and Vincent Villain., “Self-stabilizing network orientation algorithms in arbitrary rooted networks.” ,Studia Informatica Universalis, 1(1):1-22, 2001
[32] Shing-Tsaan Huang and Nian-Shing Chen., “ Self-stabilizing depth-first token circulation on networks.” , Distributed Computing, 7(1):61-66, 1993
[33] Shing-Tsaan Huang, Tzong-Jye Liu, and Su-Shen Hung., “ Asynchronous phase synchronization in uniform unidirectional rings.”, IEEE Transactions on Parallel and Distributed Systems, 15(4):378–384, 2004
[34] Shing-Tsaan Huang and Nian-Shing Chen., “ Self-stabilizing depth-first token circulation on networks.” , Distributed Computing, 7(1):61–66, 1993
[35] Carole Delporte-Gallet, Stéphane Devismes, and Hugues Fauconnier., “Stabilizing leader election in partial synchronous systems with crash failures.”, Journal of Paralla! and Distributed Computing, 70(1):45–58, 2010
[36] Toshimitsu Masuzawa and Hirotsugu Kakugawa., “ Self-stabilization in spite of frequent changes of networks: Case study of mutual exclusion on dynamic rings.” ,In Ted Herman and Sébastien Tixeuil, Eds., Self-Stabilizing Systems, 7th International Symposium, (SSS), Proceedings, volume 3764 of Lecture Notes in Computer Science, pages 183–197, Springer, Barcelona, Spain, October 26–27, 2005
[37] Lélia Blin and Sébastien Tixeuil., “ Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative.”, Distributed Computing, 31(2):139-166, 2018
[38] Pranay Chaudhuri and Hussein Thompson., “ Improved self-stabilizing algorithms for 1(2, 1)-labeling tree net urks.”, Mathematics in Computer Science, 5(1):27–39, 2011
[39] Volker Turau and Sven Köhler., “ A distributed algorithm for minimum distance-k domination in trees.” , Journal of Graph Algorithms and Applications, 19(1):223–242
[40] Ajoy K. Datta, Stéphane Devismes, Lawrence L. Larmore, and Vincent Villain., “ Self-stabilizing weak leader election in anonymous trees using constant memory per edge.”, Parallel Processing Letters, 27(2):1-18, 2017
[41] Sukumar Ghosh and Mehmet Hakan Karaata., “ A self-stabilizing algorithm for coloring planar graphs.”, Distributed Computing, 7(1):55-59, 1993
[42] Ji-Cherng Lin and Ming-Yi Chiu., “ A fault-containing self-stabilizing algorithm for 6-coloring planar graphs.”, Journal of Information Science and Engineering, 26(1):163-181, 2010
[43] Ajoy K. Datta, Colette Johnen, Franck Petit, and Vincent Villain., “ Self-stabilizing depth-first token circulation in arbitrary rooted networks.”,Distributed Computing, 13(4):207–218, 2000
[44] Stéphane Devismes, Swan Dubois, and Franck Petit., “ Introduction to Distributed Self-Stabilizing Algorithms.”, Karine Altisen,Copyright © 2019 by Morgan & Claypool
Published
2022-03-01
How to Cite
Heidari, Z., Gorginpour, H., & Shahparasti, M. (2022). A Comprehensive Review of Self-stabilization Algorithm and Its Applications in Wireless Networks. Majlesi Journal of Mechatronic Systems, 11(1), 19-30. Retrieved from https://ms.majlesi.info/index.php/ms/article/view/512
Section
Articles
