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 1 ,…, 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 4 np 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.