期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：1996
卷号：1996
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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.
