Narrow Results

The 2-dimensional torus networks, denoted by $T(m,n)$, is a special case of the famous $n$-dimensional torus network. The extra connectivity, structure connectivity and sub-structure connectivity are generalized connectivity to measure the fault-tolerance of the networks. In this paper, we show the 1-extra connectivity of $T(m,n)$ for $m\ge 3$ and $n\ge 4$ and 2-extra connectivity of $T(3,n)$ for $n\ge 4$. We also determine the $H$-structure connectivity and $H$-substructure connectivity of 2-dimensional torus network $T(m,n)$ ($m\ge 3$ and $n\ge 4$) when the structure subgraph $H\in \{K_{1,r},P_k\}$, where $2\le r\le 4$ and $4\le k\le 8$. These results are sharp since the connectivity of $T(m,n)$ ($m\ge 3,n\ge 3$) is 4.

This paper analyses how the symmetry of a processor network influences the existence of a solution for the network orientation problem. The orientation of hypercubes and tori is the problem of assigning labels to each link of each processor, in such a way that a sense of direction is given to the network. In this paper the problem of network orientation for these two topologies is studied under the assumption that the network contains a single leader, under the assumption that the processors possess unique identities, and under the assumption that the network is anonymous. The distinction between these three models is considered fundamental in distributed computing.

It is shown that orientations can be computed by deterministic algorithms only when either a leader or unique identities are available. Orientations can be computed for anonymous networks by randomized algorithms, but only when the number of processors is known. When the number of processors is not known, even randomized algorithms cannot compute orientations for anonymous processor networks.

Lower bounds on the message complexity of orientation and algorithms achieving these bounds are given.