License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2016.16
URN: urn:nbn:de:0030-drops-61856
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6185/
Go to the corresponding LIPIcs Volume Portal

Bonakdarpour, Borzoo ; Fraigniaud, Pierre ; Rajsbaum, Sergio ; Rosenblueth, David A. ; Travers, Corentin

Decentralized Asynchronous Crash-Resilient Runtime Verification

pdf-format:
LIPIcs-CONCUR-2016-16.pdf (0.7 MB)

Abstract

Runtime Verification (RV) is a lightweight method for monitoring the formal specification of a system during its execution. It has recently been shown that a given state predicate can be monitored consistently by a set of crash-prone asynchronous distributed monitors, only if sufficiently many different verdicts can be emitted by each monitor. We revisit this impossibility result in the context of LTL semantics for RV. We show that employing the four-valued logic Rv-LTL will result in inconsistent distributed monitoring for some formulas. Our first main contribution is a family of logics, called Ltl2k+4, that refines Rv-Ltl incorporating 2k + 4 truth values, for each k >= 0. The truth values of Ltl2k+4 can be effectively used by each monitor to reach a consistent global set of verdicts for each given formula, provided k is sufficiently large. Our second main contribution is an algorithm for monitor construction enabling fault-tolerant distributed monitoring based on the aggregation of the individual verdicts by each monitor.

BibTeX - Entry

@InProceedings{bonakdarpour_et_al:LIPIcs:2016:6185,
  author =	{Borzoo Bonakdarpour and Pierre Fraigniaud and Sergio Rajsbaum and David A. Rosenblueth and Corentin Travers},
  title =	{{Decentralized Asynchronous Crash-Resilient Runtime Verification}},
  booktitle =	{27th International Conference on Concurrency Theory (CONCUR 2016)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-017-0},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{59},
  editor =	{Jos{\'e}e Desharnais and Radha Jagadeesan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6185},
  URN =		{urn:nbn:de:0030-drops-61856},
  doi =		{10.4230/LIPIcs.CONCUR.2016.16},
  annote =	{Keywords: Runtime monitoring, Distributed algorithms, Fault-tolerance}
}

Keywords: Runtime monitoring, Distributed algorithms, Fault-tolerance
Collection: 27th International Conference on Concurrency Theory (CONCUR 2016)
Issue Date: 2016
Date of publication: 24.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI