Tight Bounds for Maximal Identifiability of Failure Nodes in Boolean Network Tomography

We study maximal identifiability, a measure recently introduced in Boolean Network Tomography to characterize networks' capability to localize failure nodes in end-to-end path measurements. Under standard assumptions on topologies and on monitors placement, we prove tight upper and lower bounds on the maximal identifiability of failure nodes for specific classes of network topologies, such as trees, bounded-degree graphs, d-dimensional grids, in both directed and undirected cases. Among other results we prove that directed d-dimensional grids with support n have maximal identifiability d using nd monitors; and in the undirected case we show that 2d monitors suffice to get identifiability of d-1. We then study identifiability under embeddings: we establish relations between maximal identifiability, embeddability and dimension when network topologies are modelled as DAGs. Through our analysis we also refine and generalize results on limits of maximal identifiability recently obtained in [12] and [1]. Our results suggest the design of networks over N nodes with maximal identifiability Ω(√log N) using 2√log N monitors and heuristics to place monitors and edges in a network to boost maximal identifiability.