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

来源：

ACM COMPUTING SURVEYS | 2020年 / 53卷 / 04期

关键词：

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 条

[41] Evaluating Fault Tolerance Properties of Self-stabilizing Matching Algorithms in Wireless Sensor Networks [J].

Ileri, Can Umut ;

Dagdeviren, Orhan .

2018 IEEE INTERNATIONAL BLACK SEA CONFERENCE ON COMMUNICATIONS AND NETWORKING (BLACKSEACOM), 2018, :11-15

[42] Self-stabilizing algorithms for finding centers and medians of trees [J].

Bruell, SC ;

Ghosh, S ;

Karaata, MH ;

Pemmaraju, SV .

SIAM JOURNAL ON COMPUTING, 1999, 29 (02) :600-614

[43] Self-Stabilizing Leader Election in Dynamic Networks [J].

Ajoy K. Datta ;

Lawrence L. Larmore .

Theory of Computing Systems, 2018, 62 :977-1047

[44] Self-Stabilizing Leader Election in Dynamic Networks [J].

Datta, Ajoy K. ;

Larmore, Lawrence L. .

THEORY OF COMPUTING SYSTEMS, 2018, 62 (05) :977-1047

[45] Performance Evaluation of Distributed Self-Stabilizing Dominating Set Algorithms in Wireless Sensor Networks [J].

Evcimen, Huseyin Tolga ;

Akram, Vahid Khalilpour ;

Dagdeviren, Orhan .

2018 5TH INTERNATIONAL CONFERENCE ON ELECTRICAL AND ELECTRONIC ENGINEERING (ICEEE), 2018, :428-432

[46] Brief Announcement: Self-Stabilizing Counting in Mobile Sensor Networks [J].

Beauquier, Joffroy ;

Clement, Julien ;

Messika, Stephane ;

Rosaz, Laurent ;

Rozoy, Brigitte .

PODC'07: PROCEEDINGS OF THE 26TH ANNUAL ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2007, :396-397

[47] Self-stabilizing space optimal synchronization algorithms on trees [J].

Bein, Doina ;

Datta, Ajoy K. ;

Larmore, Lawrence L. .

STRUCTURAL INFORMATION AND COMMUNICATION COMPLEXITY, PROCEEDINGS, 2006, 4056 :334-348

[48] Convergence Time Analysis of Self-stabilizing Algorithms in Wireless Sensor Networks with Unreliable Links [J].

Kakugawa, Hirotsugu ;

Masuzawa, Toshimitsu .

STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, 10TH INTERNATIONAL SYMPOSIUM, SSS 2008, 2008, 5340 :173-187

[49] Probabilistic Self-stabilizing Vertex Coloring in Unidirectional Anonymous Networks [J].

Bernard, Samuel ;

Devismes, Stephane ;

Paroux, Katy ;

Potop-Butucaru, Maria ;

Tixeuil, Sebastien .

DISTRIBUTED COMPUTING AND NETWORKING, PROCEEDINGS, 2010, 5935 :167-+

[50] Luby's MIS algorithms made self-stabilizing [J].

Giakkoupis, George ;

Turau, Volker ;

Ziccardi, Isabella .

INFORMATION PROCESSING LETTERS, 2025, 188

← 1 2 3 4 5 →