Lower Bounds on Information Transfer in Distributed Computations
- 1 April 1980
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 27 (2) , 384-392
- https://doi.org/10.1145/322186.322200
Abstract
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.Keywords
This publication has 3 references indexed in Scilit:
- Some complexity questions related to distributive computing(Preliminary Report)Published by Association for Computing Machinery (ACM) ,1979
- Towards a theory of local and global in computationTheoretical Computer Science, 1978
- Some Complexity Results for Matrix Computations on Parallel ProcessorsJournal of the ACM, 1978