Speed of parallel processing for random task graphs

The random graph model of parallel computation introduced by Gelenbe et al. depends on three parameters: n, the number of tasks (vertices); F, the common distribution of T₁,…, T_n, the task processing times, and p = p_n, the probability for a given i < j that task i must be completed before task j is started. The total processing time is R_n, the maximum sum of T_i's along directed paths of the graph. We study the large n behavior of R_n when np_n grows sublinearly but superlogarithmically, the regime where the longest directed path contains about enp_n tasks. For an exponential (mean one) F, we prove that R_n is about 4np_n. The “discrepancy” between 4 and e is a large deviation effect. Related results are obtained when np_n grows exactly logarithmically and when F is not exponential, but has a tail which decays (at least) exponentially fast. © 1994 John Wiley L Sons, Inc.