Optimal Partitioning of Random Programs Across Two Processors

Recent work by Indurkhya et al., discusses the optimal partitioning of random distributed programs. They conclude that the optimal partitioning of a homogeneous random program over a homogeneous distributed system either assigns all modules to a single processor, or distributes the modules as evenly as possible among all processors. Their analysis rests heavily on the approximation that equates the expected maximum of a set of independent random variables with the set's maximum expectation. In this paper we strengthen their results by providing an approximation-free proof of this result for two processors under general conditions on the module execution time distribution. However, we show that additional rigor leads to a different characterization of the optimality points. We also show that under a rigorous analysis one is led to different conclusions in the general p-processor case than those reached using Indurkhya et al.'s approximation.