1997-04-01
Distributed Computing on Anonymous Hypercube Networks
Publication
Publication
Journal of Algorithms , Volume 23 - Issue 1 p. 32- 50
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 · log4 N). For the case of symmetric boolean functions we give an algorithm with bit complexity O(N · log2 N).
Additional Metadata | |
---|---|
Journal of Algorithms | |
Organisation | School of Computer Science |
Kranakis, E, & Krizanc, D. (Danny). (1997). Distributed Computing on Anonymous Hypercube Networks. Journal of Algorithms, 23(1), 32–50.
|