Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Finding Almost-Invariants in Distributed Systems
EPFL.ORCID iD: 0000-0002-1256-1070
2011 (English)In: Proceedings of the 30th IEEE Symposium on Reliable Distributed Systems (SRDS), IEEE conference proceedings, 2011, -182 p.Conference paper, Published paper (Refereed)
Abstract [en]

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.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2011. -182 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-147103DOI: 10.1109/SRDS.2011.29ISI: 000298004600020Scopus ID: 2-s2.0-81055157855ISBN: 978-1-4577-1349-1 (print)OAI: oai:DiVA.org:kth-147103DiVA: diva2:727671
Conference
The 30th IEEE Symposium on Reliable Distributed Systems (SRDS)4-7 Oct. 2011 Madrid
Note

QC 20140704

Available from: 2014-06-23 Created: 2014-06-23 Last updated: 2014-07-04Bibliographically approved

Open Access in DiVA

fulltext(198 kB)45 downloads
File information
File name FULLTEXT01.pdfFile size 198 kBChecksum SHA-512
86527be59ca8cdb2f5b879749eabc9244364715b5821734dde9003c89688fe5f134d43934015bfc0165b2e22bc56ce0aa4b1f271f12a63db10d0d1a1e4a590c1
Type fulltextMimetype application/pdf

Other links

Publisher's full textScopusIEEEXplore

Authority records BETA

Kostic, Dejan

Search in DiVA

By author/editor
Kostic, Dejan
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 45 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 51 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf