Subgraph Reliability of Alternating Group Graph With Uniform and Nonuniform Vertex Fault-Free Probabilities. (5th August 2020)
- Record Type:
- Journal Article
- Title:
- Subgraph Reliability of Alternating Group Graph With Uniform and Nonuniform Vertex Fault-Free Probabilities. (5th August 2020)
- Main Title:
- Subgraph Reliability of Alternating Group Graph With Uniform and Nonuniform Vertex Fault-Free Probabilities
- Authors:
- Huang, Yanze
Lin, Limei
Xu, Li - Abstract:
- Abstract: As the size of a multiprocessor system grows, the probability that faults occur in this system increases. One measure of the reliability of a multiprocessor system is the probability that a fault-free subsystem of a certain size still exists with the presence of individual faults. In this paper, we use the probabilistic fault model to establish the subgraph reliability for $AG_n$, the $n$ -dimensional alternating group graph. More precisely, we first analyze the probability $R_n^{n-1}(p)$ that at least one subgraph with dimension $n-1$ is fault-free in $AG_n$, when given a uniform probability of a single vertex being fault-free. Since subgraphs of $AG_n$ intersect in rather complicated manners, we resort to the principle of inclusion–exclusion by considering intersections of up to five subgraphs and obtain an upper bound of the probability. Then we consider the probabilistic fault model when the probability of a single vertex being fault-free is nonuniform, and we show that the upper bound under these two models is very close to the lower bound obtained in a previous result, and it is better than the upper bound deduced from that of the arrangement graph, which means that the upper bound we obtained is very tight.
- Is Part Of:
- Computer journal. Volume 65:Number 3(2022)
- Journal:
- Computer journal
- Issue:
- Volume 65:Number 3(2022)
- Issue Display:
- Volume 65, Issue 3 (2022)
- Year:
- 2022
- Volume:
- 65
- Issue:
- 3
- Issue Sort Value:
- 2022-0065-0003-0000
- Page Start:
- 589
- Page End:
- 605
- Publication Date:
- 2020-08-05
- Subjects:
- subgraph reliability -- probabilistic fault model -- intersection pattern -- principle of inclusion–exclusion
Computers -- Periodicals
005.1 - Journal URLs:
- http://comjnl.oxfordjournals.org/ ↗
http://ukcatalogue.oup.com/ ↗ - DOI:
- 10.1093/comjnl/bxaa088 ↗
- Languages:
- English
- ISSNs:
- 0010-4620
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 3394.060000
British Library DSC - BLDSS-3PM
British Library HMNTS - ELD Digital store - Ingest File:
- 21558.xml