What Can We Monitor Over Unreliable Channels?

TitleWhat Can We Monitor Over Unreliable Channels?
Publication TypeJournal Article
Year of Publication2021
AuthorsKauffman, S., K. Havelund, and S. Fischmeister
JournalInternational Journal on Software Tools for Technology Transfer
Volume23
Issue4
Pagination579--600
ISSN1433-2779
Abstract

This article addresses the question of what properties can be monitored over an unreliable communication channel.  We model unreliable communications as mutations to finite traces and define what it means for a property to be immune to such a mutation.  We also introduce the idea of a trustworthy verdict, which is a verdict guaranteed to be correct in the presence of a trace mutation.  We show that the trustworthiness of a verdict or immunity of a property for a single mutation is equivalent to the trustworthiness or immunity for any number of mutations.  We classify trustworthy verdicts on $\omega$-regular properties by updating a recently proposed monitorability-focused refinement of the safety-liveness taxonomy.  The article also includes a fixed-parameter tractable algorithm to test an $\omega$-regular property for immunity to a trace mutation.  Our results show that many of the most common properties can be monitored over unreliable channels.

DOI10.1007/s10009-021-00625-z
Refereed DesignationRefereed
Related files: 

Opportunities

Looking for motivated students (undergrads and grads) interested in working on embedded software and systems research. Mail Sebastian Fischmeister for further information.