Finding almost-invariants in distributed systems

Maysam Yabandeh*, Abhishek Anand, Marco Canini, Dejan Kostić

*Corresponding author for this work

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

4 Scopus citations

Abstract

It is notoriously hard to develop dependable distributed systems. This is partly due to the difficulties in foreseeing various corner cases and failure scenarios while implementing a system that will be deployed over an asynchronous network. In contrast, reasoning about the desired distributed system behavior and the corresponding invariants is easier than reasoning about the code itself. Further, the invariants can be used for testing, theorem proving, and runtime enforcement. In this paper, we propose an approach to observe the system behavior and automatically infer invariants which reveal implementation bugs. Using our tool, Avenger, we automatically generate a large number of potentially relevant properties, check them within the time and spatial domains using traces of system executions, and filter out all but a few properties before reporting them to the developer. Our key insight in filtering is that a good candidate for an invariant is the one that holds in all but a few cases, i.e., an "almost-invariant". Our experimental results with the XORP BGP implementation demonstrate Avenger's ability to identify the almost-invariants that lead the developer to programming errors.

Original languageEnglish (US)
Title of host publicationProceedings - 2011 30th IEEE International Symposium on Reliable Distributed Systems, SRDS 2011
Pages177-182
Number of pages6
DOIs
StatePublished - Dec 14 2011
Event2011 30th IEEE International Symposium on Reliable Distributed Systems, SRDS 2011 - Madrid, Spain
Duration: Oct 4 2011Oct 7 2011

Publication series

NameProceedings of the IEEE Symposium on Reliable Distributed Systems
ISSN (Print)1060-9857

Other

Other2011 30th IEEE International Symposium on Reliable Distributed Systems, SRDS 2011
CountrySpain
CityMadrid
Period10/4/1110/7/11

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications

Fingerprint Dive into the research topics of 'Finding almost-invariants in distributed systems'. Together they form a unique fingerprint.

Cite this