DISTRIBUTED COMPUTING ON CAYLEY NETWORKS (Extended Abstract)
Evangelos Kranakis, Danny Kriz̧anc · 1992
We study the bit-complexity (i.e. total number of bits transmitted) of computing boolean functions on anonymous Cayley networks. We show that if G is a set of generators for a group Q then i3 boolean function f is computable on the naturallly labeled Cayley network NG[~G] if and only if f is invariant under all automorphisms of the network:. We also give efficient algorithms for computing boolean functions on all such networks. We give an algorithm that shows that for any group Q and any set G of generators of 6 the bit complexity of computing all boolean functions which are computable 011 A/’c[&] is O(lGl. log2 e6’ . CgEG lgl’), where 6 is the diameter of the network, and (91 the order of g in G. In addition for any group 6 there is a set G of generators of G such that the above bit-complexity is O((G( . log4 IQ1 . CgEG lgl’). The complexity bounds derived from our results are the best known for several networks of interest, including rings, tori, hypercubes, star-, pancake- and bubble-sort networks.