Speed of parallel processing for random task graphs

Marco Isopi, Charles M. Newman

Research output: Contribution to journalArticlepeer-review


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 T1,…, Tn, the task processing times, and p = pn, the probability for a given i < j that task i must be completed before task j is started. The total processing time is Rn, the maximum sum of Ti's along directed paths of the graph. We study the large n behavior of Rn when npn grows sublinearly but superlogarithmically, the regime where the longest directed path contains about enpn tasks. For an exponential (mean one) F, we prove that Rn is about 4npn. The “discrepancy” between 4 and e is a large deviation effect. Related results are obtained when npn 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 languageEnglish (US)
Pages (from-to)361-376
Number of pages16
JournalCommunications on Pure and Applied Mathematics
Issue number3
StatePublished - Mar 1994

ASJC Scopus subject areas

  • General Mathematics
  • Applied Mathematics


Dive into the research topics of 'Speed of parallel processing for random task graphs'. Together they form a unique fingerprint.

Cite this