Lower Bounds on Information Transfer in Distributed Computations
Harold H. Abelson · Journal of the ACM · 1980
Lower bounds on the interprocessor communication required for computing a differentiable real-valued function in a distributed network are derived. These bounds are independent of the network interconnection configuration, and they impose no assumptions other than differentiability constraints on the computations performed by individual processors. As a sample application, lower bounds on information transfer in the distributed computation of some-typical matrix operations are exhibited.