Run-time predicate monitoring for distributed systems.

摘要

The problem of global state detection and predicate monitoring is fundamental to distributed systems. All interactions in distributed systems can be analyzed in terms of the building block formed by pairwise interactions of intervals between two processes. Considering causality-based pairwise interactions by which two processes may interact with each other, there exists a rich class of orthogonal interactions. This work examines the problem: "If a global state of interest to an application is specified in terms of the pairwise interactions types between each pair of processes, how can such a global state be detected?" A solution identifies a global state in which the relation specified for each process pair is satisfied. Devising an efficient algorithm is a challenge because of the overhead of having to track the intervals at different processes. This work formulates the specific conditions on the exact communication structures to determine which of the intervals being examined at any time may never satisfy the stipulated relation for that pair of processes, and therefore that interval(s) must be deleted. One centralized and two distributed on-line algorithms are presented to solve the above problem.; In this work, for conjunctive predicates, we also show how to use these algorithms to detect the traditional Possibly and Definitely modalities along with the added information of the exact interaction type between each pair of intervals (one interval at each process). The polynomial time, space, and message complexities of the proposed on-line detection algorithms to detect Possibly and Definitely in terms of the rich class of interaction types per pair of processes, are the same as those of the earlier on-line algorithms that can detect only whether the Possibly and Definitely modalities hold. This work provides the theoretical background for the problem of temporal interactions in a distributed system and has potential applications in fields such as temporal data mining, synchronization and coordination, distributed debugging, sensor networks, and industrial process control.