ALGORITHMS TO REALIZE AN ARBITRARY BPC PERMUTATION IN CHORDAL RING NETWORKS WITH FAILURES

A family of regular graphs of degree 3, called chordal rings is presented as a possible candidate for the implementation of a distributed system and for fault-tolerant architectures. The symmetry of graphs makes it possible to determine message routing by using a simple distributed algorithm. Arbitrary data permutations are generally accomplished by sorting. For certain classes of permutations, however, there exist algorithms that are more efficient than the best sorting algorithm. One such class is the Bit Permute Complement (BPC) class of permutations. In this paper, we first develop algorithms requiring two token storage registers in each node to realize an arbitrary BPC permutation. We next evaluate its ability to realize BPC permutations in networks of arbitrary size by estimating the number of required routing steps when a single fault is present and when not.