Gestalt: fast, unified fault localization for networked systems
Radhika Niranjan Mysore, Ratul Mahajan, Amin M. Vahdat, George Varghese · 2014
Abstract — We show that the performance of existing fault localization algorithms differs markedly for differ-ent networks; and no algorithm simultaneously provides high localization accuracy and low computational over-head. We develop a framework to explain these behav-iors by anatomizing the algorithms with respect to six important characteristics of real networks, such as uncer-tain dependencies, noise, and covering relationships. We use this analysis to develop Gestalt, a new algorithm that combines the best elements of existing ones and includes a new technique to explore the space of fault hypotheses. We run experiments on three real, diverse networks. For each, Gestalt has either significantly higher localization accuracy or an order of magnitude lower running time. For example, when applied to the Lync messaging sys-tem that is used widely within corporations, Gestalt lo-calizes faults with the same accuracy as Sherlock, while reducing fault localization time from days to 23 seconds. 1.