TR96-052 Authors: Martin Dietzfelbinger

Publication: 7th October 1996 08:01

Downloads: 1969

Keywords:

The fundamental assumption in the classical theory of

dissemination of information in interconnection networks

(gossiping and broadcasting) is that atomic pieces of information

are communicated. We show that, under suitable assumptions about

the way processors may communicate, computing an n-ary function

that has a "critical input" (e.g., the OR of n bits) and

distributing the result to all processors on an n-processor

network takes exactly as long as performing gossiping in the

graph that defines the network structure. A similar relation

exists between the problem of computing functions with the output

appearing at only one processor and the complexity of

broadcasting in the corresponding graph.

We further characterize the complexity of broadcasting one bit in

a synchronous network with the only restriction that in one step

a processor can send only one message. These results also

apply to EREW PRAMs and distributed memory machines (DMMs)

with the COLLISION or the ARBITRARY conflict resolution rule.