Back to search

Michigan State University

Achieving reliable distributed systems : through efficient run-time monitoring and predicate detection

Abstract

dc:description

Runtime monitoring of distributed systems to perform predicate detection is critical as well as a challenging task. It is critical because it ensures the reliability of the system by detecting all possible violations of system requirements. It is challenging because to guarantee lack of violations one has to analyze every possible ordering of system events and this is an expensive task. In this report, wefocus on ordering events in a system run using HLC (Hybrid Logical Clocks) timestamps, which are O(1) sized timestamps, and present some efficient algorithms to perform predicate detection using HLC. Since, with HLC, the runtime monitor cannot find all possible orderings of systems events, we present a new type of clock called Biased Hybrid Logical Clocks (BHLC), that are capable of finding more possible orderings than HLC. Thus we show that BHLC based predicate detection can find more violations than HLC based predicate detection. Since predicate detection based on both HLC and BHLC do not guarantee detection of all possible violations in a system run, we present an SMT (Satisfiability Modulo Theories) solver based predicate detection approach, that guarantees the detection of all possible violations in a system run. While a runtime monitor that performs predicate detection using SMT solvers is accurate, the time taken by the solver to detect the presence or absence of a violation can be high. To reduce the time taken by the runtime monitor, we propose the use of an efficient two-layered monitoring approach, where the first layer of the monitor is efficient but less accurate and the second layer is accurate but less efficient. Together they reduce the overall time taken to perform predicate detection drastically and also guarantee detection of all possible violations.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tekken Valapil, Vidhya
Contributors dc:contributor
  • Kulkarni, Sandeep
  • Torng, Eric
  • McKinley, Philip
  • Kulkarni, Rajesh

Subjects

dc:subject × 1

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-ShareAlike 4.0 International
Language dc:language
English

Identifiers

dc:identifier.*
Identifier
etd:48663
isbn:9798662422421
oclc:1201189993
umi:28023451
local:TekkenValapil_grad.msu_0128D_17687

Chain of custody

source
Harvested from
Michigan State University
Base URL
d.lib.msu.edu/oai
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
related terms
citation

Tekken Valapil, Vidhya. Achieving reliable distributed systems : through efficient run-time monitoring and predicate detection. 2020. https://doi.org/doi:10.25335/dbsf-d560