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 Ti,. . . , T,, the task processing times, and p = p,, the probability for a given i < j that task i must be completed before task j is started. The total processing time is R,,, the maximum sum of T,’s along directed paths of the graph. We study the large n behavior of Rn when np,, grows sublinearly but superlogarithmically, the regime where the longest directed path contains about enp,, tasks. For an exponential (mean one) F, we prove that R,, is about 4np,. The “discrepancy” between 4 and e is a large deviation effect. Related results are obtained when np,, grows exactly logarithmically and when F is not exponential, but has a tail which decays (at least) exponentially fast.