Minimizing message complexity of partially replicated data on hypercubes
✍ Scribed by Humenik, Keith; Matthews, Peter; Stephens, A. B.; Yesha, Yelena
- Publisher
- John Wiley and Sons
- Year
- 1996
- Tongue
- English
- Weight
- 663 KB
- Volume
- 28
- Category
- Article
- ISSN
- 0028-3045
No coin nor oath required. For personal study only.
✦ Synopsis
Within the framework of distributed and parallel computing, we consider partially replicated data on a hypercube. We address the problem of placing copies on the hypercube in order to minimize message complexity. With realistic restrictions on the read/write ratio and the number of copies, we find the unique optimal configuration of copies. We compute the communication cost of this configuration. The optimal configuration is a linear array satisfying certain properties. 0 7996 John Wiley 8 Sons, Inc.
I I / &
Let X denote the randomly chosen processor. The expected cost ( I ) which we denote E( T,,) is Let Z, be the sum of the first n digits of the binary representation of X . Then.