Survey on Algorithms for Self-stabilizing Overlay Networks

被引:9
|
作者
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 条
  • [1] Self-Stabilizing Prefix Tree Based Overlay Networks
    Caron, Eddy
    Datta, Ajoy K.
    Petit, Franck
    Tedeschi, Cedric
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2016, 27 (05) : 607 - 630
  • [2] Building self-stabilizing overlay networks with the transitive closure framework
    Berns, Andrew
    Ghosh, Sukumar
    Pemmaraju, Sriram V.
    THEORETICAL COMPUTER SCIENCE, 2013, 512 : 2 - 14
  • [3] On Underlay-Aware Self-Stabilizing Overlay Networks
    Goette, Thorsten
    Scheideler, Christian
    Setzer, Alexander
    STABILIZATION, SAFETY, AND SECURITY OF DISTRIBUTED SYSTEMS, SSS 2018, 2018, 11201 : 50 - 64
  • [4] Brief Announcement: A Framework for Building Self-Stabilizing Overlay Networks
    Berns, Andrew
    Ghosh, Sukumar
    Pemmaraju, Sriram V.
    PODC 2010: PROCEEDINGS OF THE 2010 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING, 2010, : 398 - 399
  • [5] Simulation of self-stabilizing algorithms
    Datta, AK
    Flatebo, M
    Thiagarajan, V
    COMPUTER SYSTEMS SCIENCE AND ENGINEERING, 1997, 12 (05): : 295 - 306
  • [6] Symbolic model checking for self-stabilizing algorithms
    Tsuchiya, T
    Nagano, S
    Paidi, RB
    Kikuno, T
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2001, 12 (01) : 81 - 95
  • [7] Self-stabilizing c-wave algorithms for arbitrary networks
    Mehmet Hakan Karaata
    Ebrahim Alrashed
    Mohammad Allaho
    Computing, 2023, 105 : 53 - 88
  • [8] MULTISKIPGRAPH: A Self-stabilizing Overlay Network that Maintains Monotonic Searchability
    Luo, Linghui
    Scheideler, Christian
    Strothmann, Thim
    2019 IEEE 33RD INTERNATIONAL PARALLEL AND DISTRIBUTED PROCESSING SYMPOSIUM (IPDPS 2019), 2019, : 845 - 854
  • [9] Re-Chord: A Self-stabilizing Chord Overlay Network
    Kniesburges, Sebastian
    Koutsopoulos, Andreas
    Scheideler, Christian
    THEORY OF COMPUTING SYSTEMS, 2014, 55 (03) : 591 - 612
  • [10] Re-Chord: A Self-stabilizing Chord Overlay Network
    Sebastian Kniesburges
    Andreas Koutsopoulos
    Christian Scheideler
    Theory of Computing Systems, 2014, 55 : 591 - 612