𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Distributed Computing on Anonymous Hypercube Networks

✍ Scribed by Evangelos Kranakis; Danny Krizanc

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
245 KB
Volume
23
Category
Article
ISSN
0196-6774

No coin nor oath required. For personal study only.

✦ Synopsis

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 Ε½ 4 . algorithm for computing all such functions with bit complexity O N ΠΈ log N . For the case of symmetric boolean functions we give an algorithm with bit complexity Ε½ 2 . O N ΠΈ log N .

πŸ“œ SIMILAR VOLUMES

Computing on anonymous networks with sen
Computing on anonymous networks with sense of direction
✍ Paola Flocchini; Alessandro Roncato; Nicola Santoro πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 358 KB

Sense of direction refers to a set of global consistency constraints of the local labeling of the edges of a network. Sense of direction has a large impact on the communication complexity of many distributed problems. In this paper, we study the impact that sense of direction has on computability an

Computing biconnected components on a hy
Computing biconnected components on a hypercube
✍ Jinwoon Woo; Sartaj Sahni πŸ“‚ Article πŸ“… 1991 πŸ› Springer US 🌐 English βš– 712 KB

We describe two hypercube algorithms to find the biconnected components of a dense connected undirected graph. One is a modified version of the Tarjan-Vishkin algorithm and the other is an adaptation of Read's sequential algorithm. The two hypercube algorithms were experimentally evaluated on an NCU

Computing Hough transforms on hypercube
Computing Hough transforms on hypercube multicomputers
✍ Sanjay Ranka; Sartaj Sahni πŸ“‚ Article πŸ“… 1990 πŸ› Springer US 🌐 English βš– 843 KB

Efficient algorithms to compute the Hough transform on M1MD and SIMD hypercube multicomputers are developed. Our algorithms can compute p angles of the Hough transform of an N x N image, p < N, in 0(p + log N) time on both MIMD and SIMD hypercubes. These algorithms require 0(N ~) processors. We also