Distributed computing on Cayley networks

The authors study the bit-complexity (i.e. total number of bits transmitted) of computing Boolean functions on anonymous Cayley networks. They present a simple group-theoretic characterization of the Boolean functions computable on a given Cayley network and also give an efficient algorithm for computing all such functions. For many networks of interest, the algorithm is the most efficient known. The complexity bounds derived from the present results are the best known for several networks of interest, including rings, tori, hypercubes, and star-, pancake- and bubble-sort networks. >