Tiwari (1987) considered the following scenario: k+1 processors P_0,...,P_k,
connected by k links to form a linear array, compute a function f(x,y), for
inputs (x,y) from a finite domain X x Y, where x is only known to P_0 and
y is only known to P_k; the intermediate ... more >>>

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., ... more >>>

It was shown some years ago that the computation time for many important
Boolean functions of n arguments on concurrent-read exclusive-write
parallel random-access machines
(CREW PRAMs) of unlimited size is at least f(n) = 0.72 log n.
On the other hand, it ... more >>>