Information Transfer in Distributed Computing with Applications to VLSI

Abstract

Simple general lower bound techniques are developed for measuring the amount of interprocessor 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 Categories and SubJect Descriptors: B.7. l