Size-Independent Self-Stabilizing Asynchronous Phase Synchronization in General Graphs

被引：0

作者：

Tzeng, Chi-Hung ^{[1
]}

Jiang, Jehn-Ruey ^{[2
]}

Huang, Shing-Tsaan ^{[2
]}

机构：

[1] Natl Tsing Hua Univ, Dept Comp Sci, Hsinchu 300, Taiwan

[2] Natl Cent Univ, Dept Comp Sci & Informat Engn, Chungli 320, Taiwan

来源：

JOURNAL OF INFORMATION SCIENCE AND ENGINEERING | 2010年 / 26卷 / 04期

关键词：

general connected graph; fault tolerance; phase synchronization; self-stabilization; spanning tree; UNIDIRECTIONAL RINGS; DISTRIBUTED CONTROL; ODD SIZE; SYSTEMS; SPITE;

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

In this paper, we design a self-stabilizing phase synchronizer for distributed systems. The synchronizer enables a node to transfer from one phase to the next one, subject to the condition that at most two consecutive phases appear among all nodes. It does not rely on any system parameter like the number of nodes, and thus fits for dynamic systems where nodes can freely join or leave. Each node just maintains a few variables that are related to its neighborhood; all operations are decided based on local information rather than global information. The memory usage of the proposed algorithm is low; each node has only O(Delta K) states, where Delta is the maximum degree of nodes and K > 1 is the number of phases. To the best of our knowledge, there are no other such size-independent self-stabilizing algorithms for systems of general graph topologies.

引用

页码：1307 / 1322

页数：16

共 50 条

[31] Universal self-stabilizing phase clock protocol with bounded memory.
Nolot, F
Villain, V
CONFERENCE PROCEEDINGS OF THE 2001 IEEE INTERNATIONAL PERFORMANCE, COMPUTING, AND COMMUNICATIONS CONFERENCE, 2001, : 228 - 235
[32] Self-stabilizing depth-first token circulation in asynchronous message-passing systems
Petit, F
Villain, V
COMPUTERS AND ARTIFICIAL INTELLIGENCE, 2000, 19 (05): : 391 - 415
[33] Self-stabilizing 2m-clock for unidirectional rings of odd size
Huang, ST
Liu, TJ
DISTRIBUTED COMPUTING, 1999, 12 (01) : 41 - 46
[34] Self-Stabilizing Computation of Perfect Neighborhood Set in Large Network Graphs
Ding, Yihua
Wang, James Z.
Srimani, Pradip K.
2016 IEEE/WIC/ACM INTERNATIONAL CONFERENCE ON WEB INTELLIGENCE (WI 2016), 2016, : 435 - 438
[35] A self-stabilizing (Δ+1)- edge-coloring algorithm of arbitrary graphs
Drira, Kaouther
Dekar, Lyes
Kheddouci, Hamamache
2009 INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED COMPUTING, APPLICATIONS AND TECHNOLOGIES (PDCAT 2009), 2009, : 312 - 317
[36] Fast, silent self-stabilizing distance-k independent dominating set construction
Johnen, Colette
INFORMATION PROCESSING LETTERS, 2014, 114 (10) : 551 - 555
[37] ANALYSIS OF SELF-STABILIZING CLOCK SYNCHRONIZATION BY MEANS OF STOCHASTIC PETRI NETS - COMMENTS
CIARDO, G
LINDEMANN, C
IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (12) : 1453 - 1456
[38] A Thin Self-Stabilizing Asynchronous Unison Algorithm with Applications to Fault Tolerant Biological Networks
Emek, Yuval
Keren, Eyal
PROCEEDINGS OF THE 2021 ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC '21), 2021, : 93 - 102
[39] Self-Stabilizing Master-Slave Token Circulation in Unoriented Cactus Graphs
Ding, Yihua
Wang, James Z.
Srimani, Pradip K.
2018 IEEE/WIC/ACM INTERNATIONAL CONFERENCE ON WEB INTELLIGENCE (WI 2018), 2018, : 41 - 48
[40] An O(n2) Self-Stabilizing Algorithm for Minimal Total Dominating Set in Arbitrary Graphs
Ding, Yihua
Wang, James Z.
Srimani, Pradip K.
2020 IEEE/WIC/ACM INTERNATIONAL JOINT CONFERENCE ON WEB INTELLIGENCE AND INTELLIGENT AGENT TECHNOLOGY (WI-IAT 2020), 2020, : 49 - 54

← 1 2 3 4 5 →