Carleton University
Technical Report TR-215
November 1992
Labeled Versus Unlabeled Distributed Cayley Networks
Evangelos Kranakis & Danny Krizanc
Abstract
We consider labelings (i.e. assignments of labels to the links that give the network a globally consistent orientation) on anonymous Cayley networks Na constructed from a set G of generators of a group Q. Such networks can be endowed with a natural labeling .Ca to. form the oriented . Cayley network, denoted by Na[.Ca]. We show that in general oriented Cayley networks are more powerful than unoriented Cayley networks, in the sense that the former can compute more Boolean functions than the latter. We also give a characterization of those abelian groups Q which have a canonical set of generators G such that the network Na computes more Boolean functions than the network Na[.Ca].