¡@
Journal of Information Science and Engineering, Vol. 24 No.
6, pp. 1859-1872 (November 2008)
The Self-Stabilizing Edge-Token and Its Applications*
Su-Shen Hung and Shing-Tsaan Huang+
Department of Computer Science
National Tsing Hua University
Hsinchu, 300 Taiwan
+Department of Computer Science and Information Engineering
National Central University
Taoyuan, 320 Taiwan
Consider a connected graph with nodes (or processes) and edges (or communication
links). An edge token associated with an edge is a token maintained by the two nodes
connected by the edge; one and only one of the two nodes holds the token. An edge token
can be passed from one node to the other if so desired. This paper first presents a
randomized self-stabilizing algorithm to implement the edge token, in which each process
maintains two three-state variables for an edge; the scheme works under the distributed
scheduler with the read/write atomicity. Then, the edge token algorithm is used as a
building block in two other self-stabilizing algorithms: one is for ring orientation problem
and the other for token circulation problem on trees. All the proposed algorithms are
uniform.
Keywords:
edge token, leader election, mutual exclusion, orientation, self-stabilization
Retrieve PDF document (200811_15.pdf)
Received January 20, 2006; revised October 26, 2007; accepted May 29, 2008.
Communicated by Tsan-sheng Hsu.
* This research was supported in part by the National Science Council of Taiwan, R.O.C. under contracts No.
NSC 91-2213-E008-011 and 92-2213-E008-029. The preliminary parts of the paper have been presented at
the 6th Symposium on Self-Stabilizing Systems (SSS¡¦03) and ISCA 17th International Conference on Parallel
and Distributed Computing Systems (PDCS-2004).