×

Connection reliabilities in stochastic acyclic networks. (English) Zbl 0812.90054

Let \({\mathcal F}_{n,p}\) be the subset of a simply generated family \(\mathcal F\) containing all trees \(T\) and \(p\) leaves and \(n\) nodes in total. Assuming that the trees are planar so that leaf numbers are identifiable, the paper deals with the following reliability model: (i) \(T\) is selected randomly from \({\mathcal F}_{n,p}\); (ii) Each edge of \(T\) has the same probability \(q\) of failing; (iii) Failures of edges occur independently.
The reliability variable \(Z_ i\) is defined as \(Z_ i= 1\) if the path connecting the root of \(T\) to the \(i\)th leaf does not contain a failed edge, 0 otherwise. In this article the stochastic process \(\{Z_ 1,\dots, Z_ p\}\) is studied. Asymptotic results when \(n\) and the path indices \(i\), \(j\) etc. tend to \(\infty\) are also obtained. The following auxiliary results are further derived: (i) Rotational invariance of leaf distance distribution in arbitrary simply generated families; (ii) The asymptotic height distribution of the \(i\)th leaf and the asymptotic joint height distribution of the \(i\)th and \(j\)th leaves in a random \(t\)-ary tree.

MSC:

90B25 Reliability, availability, maintenance, inspection in operations research
90B18 Communication networks in operations research
60K10 Applications of renewal theory (reliability, demand theory, etc.)
Full Text: DOI

References:

[1] Aldous, Proc. Durham Symp. Stochastic Analysis 90 pp 23– (1991) · doi:10.1017/CBO9780511662980.003
[2] Downs, IEEE Trans. Software Eng. SE-11 pp 375– (1985)
[3] Downs, IEEE Trans. Software Eng. SE-12 pp 978– (1986) · doi:10.1109/TSE.1986.6313052
[4] , and , On weighted heights of randome trees, Tech. Rep., Cornel University, Ithaca, NY (1989).
[5] Flajoitet, J. Comput. Syst. Sci. 25 pp 171– (1982)
[6] Random tree models in the analysis of algorithms, in and (Eds.), Performance ’87, Elsevier, New York, 1988, pp. 171–187.
[7] Flajolet, SIAM J. Discrete Math. 3 pp 216– (1990)
[8] A combinatorial model for software testing and reliability, Tech. Rep., University of Vienna, 1989.
[9] Gutjahr, Österr. Zeitschr. f. Statistik u. Informatik 21 pp 57– (1991)
[10] Gutjahr, Graphs and Combinatorics 8 pp 243– (1992)
[11] Gutjahr, Theor. Inf. Appl. 26 pp 1– (1992)
[12] Gutjahr, Stochastic Proc. Appl. 41 pp 69– (1992)
[13] , and , Mathematical Models for the Study of the Reliability of Systems, Academic, New York, 1977.
[14] Kemp, J. Copmbinat. Theory B 34 pp 191– (1983)
[15] Fundamentals of the Average Case Analysis of Particular Algorithms, Wiley-Teubner, New York, 1984. · Zbl 0638.68026 · doi:10.1007/978-3-663-12191-6
[16] Kirschenhofer, J. Graph Theory 7 pp 311– (1983)
[17] Kirschenhofer, Ann. Discrete Math. 33 pp 157– (1987)
[18] McLeod, J. Parallel Distr. Comput. 8 pp 376– (1990)
[19] Meir, Can. J. Math. 30 pp 997– (1978) · Zbl 0394.05015 · doi:10.4153/CJM-1978-085-0
[20] Meir, Eur. J. Combinat. 11 pp 581– (1990) · Zbl 0735.05008 · doi:10.1016/S0195-6698(13)80043-1
[21] Moon, SIAM J. Alg. Discrete Math. 4 pp 8– (1983)
[22] Parther, IEEE Trans. Software Eng. SE-13 pp 761– (1987)
[23] Ramamoorthy, IEEE Trans. Software Eng. SE-8 pp 354– (1982)
[24] Ramesh, Ann. Discrete Math. 33 pp 261– (1987)
[25] Algebraic aspects of computing network reliability, Applications of Discrete Mathematics, SIAM, Philadelphia, PA. 1988, pp. 135–147.
[26] On network structure function computations, Tech. Rep., Oregon State Univerisity, Corvallis, OR. · Zbl 0850.60015
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.