Premium
Minimizing message complexity of partially replicated data on hypercubes
Author(s) -
Humenik Keith,
Matthews Peter,
Stephens A. B.,
Yesha Yelena
Publication year - 1996
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199609)28:2<87::aid-net2>3.0.co;2-8
Subject(s) - hypercube , computer science , parallel computing , communication complexity , computational complexity theory , message passing , theoretical computer science , distributed computing , algorithm
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. © 1996 John Wiley & Sons, Inc.