Eventually perfect predicate detection in crash-affected finite average response time systems

摘要

Monitoring and predicate detection is a fundamental challenge of evaluating whether or not a predicate has held on the state of a distributed system in an execution. We solve eventually perfect predicate detection in a failure-prone system assuming that only the average response time is finite. The solution is based on an eventually accurate failure detection sequencer (◇Σ) which we propose and implement in the finite average response time system. We prove that ◇Σ can solve eventually perfect detection of predicates involving process operational status. This research contributes to identifying realistic detection semantics in a weak partially synchronous model. Our approach has a layered model with which applications have the flexibility to choose appropriate predicate detection algorithms with the possibility to solve different predicate modalities.