
doi: 10.1109/32.21740
Recent works by \textit{B. Indurkhya}, \textit{H. S. Stone} and \textit{X.-Ch. Lu} [ibid. SE-12, 483-495 (1986; Zbl 0587.68025)], 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. 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, \textit{H. S. Stone} and \textit{X.-Ch. Lu} [ibid. SE-12, 483-495 (1986; Zbl 0587.68025)] approximation.
random distributed programs, partitioning, multiprocessors, random graphs, Theory of operating systems
random distributed programs, partitioning, multiprocessors, random graphs, Theory of operating systems
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 19 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
