## Abstract

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 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.

Original language | English (US) |
---|---|

Pages (from-to) | 361-376 |

Number of pages | 16 |

Journal | Communications on Pure and Applied Mathematics |

Volume | 47 |

Issue number | 3 |

DOIs | |

State | Published - Mar 1994 |

## ASJC Scopus subject areas

- Mathematics(all)
- Applied Mathematics