Self-stabilizing Asynchronous Phase Synchronization in General Graphs

摘要

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.