Survey on Algorithms for Self-stabilizing Overlay Networks

被引:10
作者
Feldmann, Michael [1 ]
Scheideler, Christian [1 ]
Schmid, Stefan [2 ]
机构
[1] Paderborn Univ, Paderborn, Germany
[2] Univ Vienna, Fac Comp Sci, Vienna, Austria
关键词
Self-stabilization; overlay networks; topological self-stabilization; distributed algorithms; resilience; dependability; RESILIENT; GRAPHS; CHORD;
D O I
10.1145/3397190
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The maintenance of efficient and robust overlay networks is one of the most fundamental and reoccurring themes in networking. This article presents a survey of state-of-the-art algorithms to design and repair overlay networks in a distributed manner. In particular, we discuss basic algorithmic primitives to preserve connectivity, review algorithms for the fundamental problem of graph linearization, and then survey self-stabilizing algorithms for metric and scalable topologies. We also identify open problems and avenues for future research.
引用
收藏
页数:24
相关论文
共 50 条
[31]   Token-based self-stabilizing uniform algorithms [J].
Beauquier, J ;
Gradinariu, M ;
Johnen, C ;
Durand-Lose, J .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2002, 62 (05) :899-921
[32]   Self-stabilizing Synchronous Unison in Directed Networks [J].
Altisen, Karine ;
Cournier, Alain ;
Defalque, Geoffrey ;
Devismes, Stephane .
PROCEEDINGS OF THE 24TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING AND NETWORKING, ICDCN 2023, 2023, :115-124
[33]   Self-stabilizing token circulation in uniform networks [J].
Huang, ST ;
Wuu, LC .
DISTRIBUTED COMPUTING, 1997, 10 (04) :181-187
[34]   Self-stabilizing Algorithms for Connected Vertex Cover and Clique Decomposition Problems [J].
Delbot, Francois ;
Laforest, Christian ;
Rovedakis, Stephane .
PRINCIPLES OF DISTRIBUTED SYSTEMS, OPODIS 2014, 2014, 8878 :307-322
[35]   Self-stabilizing Leader Election in Dynamic Networks [J].
Datta, Ajoy K. ;
Larmore, Lawrence L. ;
Piniganti, Hema .
STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, 2010, 6366 :35-49
[36]   Self-stabilizing group communication in directed networks [J].
Shlomi Dolev ;
Elad Schiller .
Acta Informatica, 2004, 40 :609-636
[37]   Self-stabilizing synchronous unison in directed networks [J].
Altisen, Karine ;
Cournier, Alain ;
Defalque, Geoffrey ;
Devismes, Stephane .
THEORETICAL COMPUTER SCIENCE, 2024, 1001
[38]   Self-stabilizing agent traversal on tree networks [J].
Nakaminami, Y ;
Masuzawa, T ;
Herman, T .
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2004, E87D (12) :2773-2780
[39]   Self-stabilizing token circulation in uniform networks [J].
Shing-Tsaan Huang ;
Lih-Chyau Wuu .
Distributed Computing, 1997, 10 :181-187
[40]   Self-stabilizing group communication in directed networks [J].
Dolev, S ;
Schiller, E .
ACTA INFORMATICA, 2004, 40 (09) :609-636