Information Transfer in Distributed Computing with Applications to VLSI

Abstract

Simple general lower bound techniques are developed for measuring the amount of inter- processor commumcatlon required in distributed computing. Optimal bounds are shown for many problems, such as integer multiplication, integer division, matrix squaring, matrix inversion, solving a linear system of equations, and computing square roots. Using these techniques, one can unify and strengthen the area-time trade-off results known in the literature. Many new trade-off results are also shown in several of the existing models