SPEED OF PARALLEL-PROCESSING FOR RANDOM TASK GRAPHS

The random graph model of parallel computation introduced by Gelenbe e t al. depends on three parameters: n, the number of tasks (vertices); F, the common distribution of T1,...,T(n), the task processing times, and p = p(n), the probability for a given i < j that task i must be co mpleted before task j is started. The total processing time is R(n), t he maximum sum of T(i)'s along directed paths of the graph. We study t he large n behavior of R(n) when np(n) grows sublinearly but superloga rithmically, 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 logarit hmically and when F is not exponential, but has a tail which decays (a t least) exponentially fast. (C) 1994 John Wiley & Sons, Inc.