Signature Algorithms for Cayley Graphs

Michael D. Rice
Lewis C. Robertson

Department of Mathematics & Computer Science
Wesleyan University

Assume that an interconnection network is defined by a Cayley graph (G, S), where G is a group and S is a generating set for G. In certain cases, after executing an algorithm on the network, the same data value will be found in each processor. For example, this is the case when computing the sum of all data values or broadcasting a data value from a given processor.

Our notion of a signature algorithm is based on this property. Formally, we define the following property:

Definition 1: A Cayley graph (G, S) has the A-redundancy property with respect to an algorithm A if for every initial distribution of data {gx | x in G}, there exists a constant C such that A(g)x = C for each x in G.

The redundancy property guarantees that regardless of the initial distribution of data, executing the algorithm will result in the same final value C being computed in each processor. (Of course, this value depends on the initial data {gx}.)

Definition 2: An algorithm A is a signature for an interconnection network if every Cayley graph which has the A-redundancy property is graph-isomorphic to the network.

Definition 3: A generating set S is Cayley-minimal if each s in S does not belong to the subgroup <S\{s, s-1}>.

Assuming that S is Cayley-minimal, we show that several simple algorithms are signatures for the complete graph and ring networks.

We also show that the well known algorithm H that sums the data values in the nodes of the hypercube (for a fixed ordering of the dimensions) is a signature for the hypercube if S is Cayley-minimal and G is abelian.

Furthermore, we show that if S is Cayley-minimal and (G, S) satisfies the H-redundancy property with respect to every ordering of S, then G is group isomorphic to the product of | S | copies of Z2.

Our work only scratches the surface of identifying signature algorithms for familiar interconnection networks. However, it does illustrate some possibly interesting connections between the behavior of algorithms on Cayley graphs and the structure of the underlying group.