Performance considerations on a random graph model for parallel processing. (English) Zbl 0778.68017

Summary: Consider a random directed acyclic graph (dag) with nodes \(1,2,...,n\), and an edge from node \(i\) to node \(j\) (only if \(i>j\)) with fixed probability \(p\). Such a graph can be thought of as the task graph associated with a job and thus it serves as a parallel processing model; the vertices correspond to tasks and the edges correspond to precedence constraints between tasks. In this case, the length of the graph corresponds to the parallel processing time of the job (an infinite number of available processors is assumed) and the width of the graph corresponds to the parallelism of the job. We estimate here the average length of the random dag (that is, the average processing time of the job) as a function of the probability \(p\) and the number of tasks \(n\) by establishing tight lower and upper bounds. The lower (resp. upper) bound is determined as being equal to the average length of a random dag considerably simpler to manipulate than the original one. Furthermore, the asymptotic behaviour of the average length is studied and the results obtained improve previously published results. Finally, asymptotic results are obtained concerning the average width of the task graph; it is shown that the average width tends to \(1/p\) as \(n\to \infty\).


68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI EuDML


[1] 1. M. H. ALBERT and A. M. FRIEZE, Random Graph Orders, Order, Vol. 6, 1989, pp. 19-30. Zbl0697.06004 MR1020453 · Zbl 0697.06004
[2] 2. P. FRANASZEK and J. T. ROBINSON, Limitations of Concurrency in Transaction Processing, ACM Transactions on Database Systems, 10, 1, 1985, pp. 1-28. Zbl0561.68020 · Zbl 0561.68020
[3] 3. E. GELENBE, R. D. NELSON, T. K. PHILIPS and A. TANTAWI, An Approximation of the Processing Time for a Random Graph Model of Parallel Computation, in: Proceedings, 1986 Fall Joint Computer Conference, Dallas, Texas, ACM/IEEE Computer Society, 1986, pp. 691-697.
[4] 4. C. H. PAPADIMITRIOU, The Theory of Database Concurrency Control, Computer Science Press, 1986. Zbl0609.68073 MR1102897 · Zbl 0609.68073
[5] 5. J. N . TSITSIKLIS, C. H. PAPADIMITRIOU and P. HUMBLET, The Performance of a Precedence-Based Queueing Discipline, Journal of the ACM 33, 3, 1986, pp, 593-602. MR849031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.