Self-stabilizing asynchronous phase synchronization in general graphs

Chi Hung Tzeng, Jehn Ruey Jiang, Shing Tsaan Huang

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


The phase synchronization problem requires each node to infinitely transfer from one phase to the next one under the restriction that at most two consecutive phases can appear among all nodes. In this paper, we propose a self-stabilizing algorithm under the parallel execution model to solve this problem for semi-uniform systems of general graph topologies. The proposed algorithm is memory-efficient; its space complexity per node is O(log Δ + log K) bits, where Δ is the maximum degree of the system and K > 1 is the number of phases.

Original languageEnglish
Title of host publicationStabilization, Safety, and Security of Distributed Systems - 8th International Symposium, SSS 2006. Proceedings
PublisherSpringer Verlag
Number of pages15
ISBN (Print)3540490183, 9783540490180
StatePublished - 2006
Event8th International Symposium on Self-Stabilizing Systems, SSS 2006 - Dallas, TX, United States
Duration: 17 Nov 200619 Nov 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4280 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th International Symposium on Self-Stabilizing Systems, SSS 2006
Country/TerritoryUnited States
CityDallas, TX


  • Distributed system
  • Fault tolerance
  • Phase synchronization
  • Self-stabilization
  • Spanning tree


Dive into the research topics of 'Self-stabilizing asynchronous phase synchronization in general graphs'. Together they form a unique fingerprint.

Cite this