Fundamental limits of failure identifiability by boolean network tomography

N. Bartolini, T. He, H. Khamfroush

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

20 Scopus citations


Boolean network tomography is a powerful tool to infer the state (working/failed) of individual nodes from path-level measurements obtained by egde-nodes. We consider the problem of optimizing the capability of identifying network failures through the design of monitoring schemes. Finding an optimal solution is NP-hard and a large body of work has been devoted to heuristic approaches providing lower bounds. Unlike previous works, we provide upper bounds on the maximum number of identifiable nodes, given the number of monitoring paths and different constraints on the network topology, the routing scheme, and the maximum path length. The proposed upper bounds represent a fundamental limit on the identifiability of failures via Boolean network tomography. This analysis provides insights on how to design topologies and related monitoring schemes to achieve the maximum identifiability under various network settings. Through analysis and experiments we demonstrate the tightness of the bounds and efficacy of the design insights for engineered as well as real networks.

Original languageEnglish
Title of host publicationINFOCOM 2017 - IEEE Conference on Computer Communications
ISBN (Electronic)9781509053360
StatePublished - Oct 2 2017
Event2017 IEEE Conference on Computer Communications, INFOCOM 2017 - Atlanta, United States
Duration: May 1 2017May 4 2017

Publication series

NameProceedings - IEEE INFOCOM
ISSN (Print)0743-166X


Conference2017 IEEE Conference on Computer Communications, INFOCOM 2017
Country/TerritoryUnited States

Bibliographical note

Publisher Copyright:
© 2017 IEEE.

ASJC Scopus subject areas

  • General Computer Science
  • Electrical and Electronic Engineering


Dive into the research topics of 'Fundamental limits of failure identifiability by boolean network tomography'. Together they form a unique fingerprint.

Cite this