Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18]


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

Full Text () 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 (SSS03) and ISCA 17th International Conference on Parallel and Distributed Computing Systems (PDCS-2004).