Christmas Tree: A Versatile 1-Fault-Tolerant Design for Token Rings^*

Chun-Nan Hung and Lih-Hsing Hsu^*
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.

Ting-Yi Sung
Institute of Information Science
Academia Sinica
Taipei, Taiwan 115, R.O.C.

Abstract:

The token ring topology is required in token passing approach used in distributed operating systems. Fault tolerance is also required in the designs of distributed systems. Note that 1-fault-tolerant design for token rings is equivalent to design of 1-hamiltonian graphs. This paper introduces a new family of graphs called Christmas tree, denoted by CT(s). The graph CT(s) is a 3-regular, planar, 1-hamiltonian, and hamiltonian-connected graph. The number of nodes in CT(s) is $3 \cdot 2^s - 2$. Its diameter is at most 2s. In other words, the diameter of CT(s) is no more than $2 \log_2 n - O(1)$, where n is the number of nodes.

Keywords: hamiltonian, 1-hamiltonian, hamiltonian-connected, fault-tolerant, token rings.