Data-stream-based global event monitoring using pairwise interactions

The problem of global state observation is fundamental to distributed systems and to the analysis of data streams. Many interactions in distributed systems can be analyzed in terms of the building block formed by the pairwise interactions of intervals at two processes. Considering causality-based pairwise interactions by which two processes may interact with each other, there are 40 orthogonal interaction types. For each pair of processes (Pi,Pj)(Pi,Pj), let interaction type ri,jri,j be of interest. This paper examines the problem: “If a global state of interest to an application is specified in terms of such pairwise interaction types, one per pair of processes, how can such a global state be detected?” A solution identifies a global state in which the interaction type specified for each process pair is satisfied. This paper formulates the specific conditions on the communication structures to determine which of the intervals being examined at any time may never satisfy the stipulated interaction type for that pair of processes, and therefore that interval(s) need no longer be considered as forming a part of any solution. Based on this theory, the paper proposes two on-line distributed algorithms to solve the problem.