Lower Bounds on Information Transfer in Distributed Computations
We derive a lower bound on the interprocessor information transfer required for computing a function in a distributed network. The bound is expressed in terms of the function's derivatives, and we use it to exhibit functions whose computation requires a great deal of interprocess communication....
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148930 |
| _version_ | 1826215009305231360 |
|---|---|
| author | Abelson, Harold |
| author_facet | Abelson, Harold |
| author_sort | Abelson, Harold |
| collection | MIT |
| description | We derive a lower bound on the interprocessor information transfer required for computing a function in a distributed network. The bound is expressed in terms of the function's derivatives, and we use it to exhibit functions whose computation requires a great deal of interprocess communication. As a sample application, we give lower bounds on information transfer in the distributed computation of some typical matrix operations. |
| first_indexed | 2024-09-23T16:15:04Z |
| id | mit-1721.1/148930 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T16:15:04Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1489302023-03-30T03:06:32Z Lower Bounds on Information Transfer in Distributed Computations Abelson, Harold We derive a lower bound on the interprocessor information transfer required for computing a function in a distributed network. The bound is expressed in terms of the function's derivatives, and we use it to exhibit functions whose computation requires a great deal of interprocess communication. As a sample application, we give lower bounds on information transfer in the distributed computation of some typical matrix operations. 2023-03-29T14:10:32Z 2023-03-29T14:10:32Z 1978-04 https://hdl.handle.net/1721.1/148930 4622478 MIT-LCS-TM-102 application/pdf |
| spellingShingle | Abelson, Harold Lower Bounds on Information Transfer in Distributed Computations |
| title | Lower Bounds on Information Transfer in Distributed Computations |
| title_full | Lower Bounds on Information Transfer in Distributed Computations |
| title_fullStr | Lower Bounds on Information Transfer in Distributed Computations |
| title_full_unstemmed | Lower Bounds on Information Transfer in Distributed Computations |
| title_short | Lower Bounds on Information Transfer in Distributed Computations |
| title_sort | lower bounds on information transfer in distributed computations |
| url | https://hdl.handle.net/1721.1/148930 |
| work_keys_str_mv | AT abelsonharold lowerboundsoninformationtransferindistributedcomputations |