Fault-Tolerant Decentralized Runtime Monitoring

Abstract:

 

Runtime verification  is aiming at extracting information from a running system, and using it to detect and possibly react to  behaviors violating a given correctness property. Decentralized runtime verification involves a set of monitors observing the behavior of  the underlying system. In this talk, the investigation of decentralized runtime verification in which not only the elements of the observed system, but also the monitors themselves are subject to failures will be presented. In this context, it is unavoidable that the unreliable monitors may have different views of the underlying system, and therefore may have different valuations of the correctness property. We characterize the number of valuations required for monitoring a given correctness property in a decentralized manner. Our lower bound is independent of the logic used for specifying the correctness property, as well as of the way the set of valuations returned by the monitors is globally interpreted. Moreover, our lower bound is tight in the sense that we design a distributed protocol enabling any given set of monitors to verify any given correctness property using as many different valuations as the one given by this lower bound.

Joint work with: Sergio Rajsbaum (UNAM, Mexico) and Corentin Travers (LaBRI, Bordeaux)

 

Date: Mar 16, 2016 at 14:30 h
Venue: Beauchef 851, Torre Norte, Sala de Seminarios John Von Neumann CMM., Piso 7
Speaker: Pierre Fraigniaud
Affiliation: Institut de Recherche en Informatique Fondamentale, CNRS
Coordinator: Prof. Iván Rapaport.
Abstract:
PDF

Posted on Mar 14, 2016 in Discrete Mathematics, Seminars