Non-adaptive End-to-End Diagnosis for Complex Networks.

摘要

The major goals of this project include three components: First, we want to characterize the optimal number of measurements that are needed to identify any problematic component of a connected complex system. Second, we aim to provide constructive methods to generate those measurements. Finally, we would like to test these theoretical results by numerical simulations. All three goals have been essentially met. More concretely, for goal number 1, we have shown the lower bound of number of measurements for any given graph. In particular, for several special graphs, we were able to find the exact optimal number of measurements. Furthermore, for general networks, we were able to provide order optimal estimation of the number of measurements needed. For goal number 2, all above estimation comes with explicit measurement construction. In particular, for general networks, we have a construction which only uses polynomial time algorithms. Finally, for goal number 3, all above results are extensively tested numerically.