The token ring topology is required in the token passing approach used in distributed operating systems. Fault tolerance is also required in the design of distributed systems. We consider the 1-fault-tolerant design for token rings, which can tolerate 1-processor fault- or 1-link fault. Note that the 1-fault-tolerant design for token rings is equivalent to the design of 1-Hamiltonian graphs. The paper introduces a new family of interconnection networks called Christmas tree. The under graph of the Christmas tree, denoted by CT(s), is a 3-regular, planar, 1-Hamiltonian, and Hamiltonian-connected graph. The number of nodes and the diameter of CT(s) are 3/spl times/2/sup s/-2 and 2s, respectively. In other words, the diameter of CT(s) is 2 log/sub 2/ n-O(1), where n is the number of nodes.
展开▼
机译：在分布式操作系统中使用的令牌传递方法中需要令牌环形拓扑。在分布式系统的设计中也需要容错。我们考虑了令牌环的1个容错设计，可容忍1处理器故障或1连杆故障。请注意，令牌环的1个容错设计相当于1-Hamiltonian图形的设计。本文介绍了一个名为圣诞树的新系列互连网络。由CT（S）表示的圣诞树的下图是一个3常规，平面，1-Hamiltonian和Hamiltonian连接的图表。节点的数量和CT的直径分别是3 / SPL时间/ 2 / sup S / -2和2s。换句话说，CT的直径是2个log / sub 2 / n-o（1），其中n是节点的数量。
展开▼
