Narrow Results

In this paper we study the problem of fault-tolerant parallel routing in the star network, i.e., we assume that all processors send packets according to the prescribed protocol but some packets may fail to reach (on time) their destination. Using the Information Dispersal Algorithm (IDA) we obtain a fault-tolerant randomised routing algorithm whose probability of success is 1 - N^-Θ(n), where N = n! is the number of nodes of the star graph S_n.

The surviving route graph R(G, ρ)/F for a graph G, a routing ρ and a set of failures F is a graph consisting of all non-faulty vertices of G and with an edge between two vertices if there are no failures in the routing between the two vertices. Numerous papers have studied the diameter of R(G, ρ)/F as a measure of the fault-tolerance of G and ρ, assuming that the cardinality of F is strictly smaller than the connectivity of G. In this paper we study the diameter of R(G, ρ)/F, when G is either the n-star graph or the n-dimensional hypercube and ρ is any minimal length routing, under the assumption that F is any set of failures not containing all the neighbours of any vertex and |F| is at most twice the connectivity of G minus 3.

In this paper, we propose a Star cellular neural network (Star CNN) for associative and dynamic memories. A Star CNN consists of local oscillators and a central system. All oscillators are connected to a central system in the shape of a Star, and communicate with each other through a central system. A Star CNN can store and retrieve given patterns in the form of synchronized chaotic states with appropriate phase relations between the oscillators (associative memories). Furthermore, the output pattern can occasionally travel around the stored patterns, their reverse patterns, and new relevant patterns which are called spurious patterns (dynamic memories).