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 is known that every Boolean function of n ... 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., the OR of ... more >>>