Diagnosing missing events in distributed systems with negative provenance
Authors:
Open Access
- 17 August 2014
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 383-394
Abstract
When debugging a distributed system, it is sometimes necessary to explain the absence of an event - for instance, why a certain route is not available, or why a certain packet did not arrive. Existing debuggers offer some support for explaining the presence of events, usually by providing the equivalent of a backtrace in conventional debuggers, but they are not very good at answering 'Why not?' questions: there is simply no starting point for a possible backtrace. In this paper, we show that the concept of negative provenance can be used to explain the absence of events in distributed systems. Negative provenance relies on counterfactual reasoning to identify the conditions under which the missing event could have occurred. We define a formal model of negative provenance for distributed systems, and we present the design of a system called Y! that tracks both positive and negative provenance and can use them to answer diagnostic queries. We describe how we have used Y! to debug several realistic problems in two application domains: software-defined networks and BGP interdomain routing. Results from our experimental evaluation show that the overhead of Y! is moderate.Keywords
Funding Information
- Defense Advanced Research Projects Agency (FA8650-11-C-7189)
- Division of Computer and Network Systems (CNS-1054229, CNS-1040672, CNS-1065130, CNS-0845552)
This publication has 19 references indexed in Scilit:
- Answering why-not queries in software-defined networks with negative provenance2013
- The beacon openflow controller2013
- Automatic test packet generation2012
- Where is the debugger for my software-defined network?2012
- Secure network provenance2011
- Debugging the data plane with anteater2011
- Declarative networkingCommunications of the ACM, 2009
- On the provenance of non-answers to queries over extracted dataProceedings of the VLDB Endowment, 2008
- ORCHESTRA2007
- R-trees1984