The g g -good-neighbor diagnosability of product networks under the PMC model
Zhao Wang, Yaping Mao, Sun-Yuan Hsieh, Ralf Klasing · 2025
Read The g g -good-neighbor diagnosability of product networks under the PMC model by Zhao Wang, Yaping Mao, Sun-Yuan Hsieh, Ralf Klasing (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-19463.txt.
Description
Zhao Wang and co-authors study in 2025 how many faulty nodes a network can contain while its failures can still be located, under a classic testing model. The measure grows from a notion of good neighbors: a diagnosis counts only if each healthy node keeps enough healthy neighbors. That twist fits failures that spread through neighborhoods, like cascading faults.
The team gives two conditions that settle exactly when such diagnosis is possible. They define a new count of cut components tied to the measure, and prove sharp bounds for it on general graphs. Those bounds yield a formula for the diagnosability of any graph, including product networks built from smaller ones. Data centers rely on such formulas to size their fault tolerance.
Catalog record
| CREATOR | Zhao Wang, Yaping Mao, Sun-Yuan Hsieh, Ralf Klasing |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-19463