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.

Considers a distributed database with partial replication of data objects located on a ring network. Certain placements of replicated objects are shown to optimize the probability of read-only success and the probability of write-only success. We also obtain optimal placements for k-terminal reliability and expected minimal path length for read-only and write-only operations.>

A percolation process on $n \times n$ 0-1matrices is defined. This process is defined so that a zero entry becomes one if two or more of its neighbors have the value one. Entries that have the value one never change. The process halts when no more entries can change. The initial matrices are taken to be all the $n \times n$ permutation matrices. It is shown that the number of matrices that eventually become all ones is given by the Schröder numbers. Asymptotically, the proportion of such matrices approaches zero. Next, matrices that exhibit no growth at all are considered. The number of such matrices is given in terms of a generating function, and the proportion of such matrices approaches $e^{ - 2} $ as n goes to infinity. The methods used involve bracketing, trees, and generating functions.