Distributed computing on anonymou hypercube networks
1997
We consider the bit-complexity (i.e.a, total number of bits transmitted) of computing boolean functions on an anonymous canonically labeled n-dimensional hypercube network and give a characterization of the boolean functions computable on such a network as exactly those boolean functions which are invariant under all bit-complement automorphisms of the hyercube. We provide an efficient algorithm for computing all such functions with bit complexity O(N log 4 N). For the case of symmetric boolean functions we give an algorithm with bit complexity O(N log 2 N).
Keywords:
- Correction
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI