Information Technology Reference
In-Depth Information
In this work, we consider the situation where monitored hosts in a distributed system
wish to compress data to decrease the load on the network. One of the most e
ff
ective
ways to compress an event trace is to aggregate all occurring events in a data structure
that captures the events' types and frequencies but discards their order. In our example,
the host could retain the number of times thatloginandlogoutevents were observed.
The monitor would then face the challenge that, on receiving a compressed batch of two
events, the next state would be uncertain (
A
2
or
B
2
). Importantly, though, receiving a
subsequent logout event would confirm that the automaton must be in state
B
3
,and
would cause the automaton to converge onto a single state.
Anaıve approach to processing such “compressed traces” with incomplete informa-
tion about ordering constraints would be to define a special transition procedure over an
unmodified finite-state property automaton. In such a model, on receiving an aggregated
batch of events, one would be able to determine the possible next states by traversing
the automaton with each legal permutation of events that satisfies the aggregated input,
be it through brute-force generation of traces, or by using the automaton as a genera-
tor. Using the example illustrated in Figure 1, consider the case where the monitor has
observed the following compressed batch of events:
{
logout
,
2
,
login
,
1
}
This signifies the arrival of two logout events and one login event, without any in-
formation on the order in which they were received. In a di
erent scenario, one might
consider aggregate traces that only record
N
, that is, the number of events that occurred,
without even recording their type. For such a model, any state reachable within
N
steps
of the current state is a potential next state. Preserving the type restricts the possible
next state set to a subset of these states. In general, the larger the window and number
of aggregated events, the greater the uncertainty of the end state, as the automaton will
have potentially progressed to a greater depth.
The problem with determining the next state set via naıve traversal is that the run-
ning time will grow exponentially with the number of observed events. Thus, this work
proposes an ahead-of-time automaton transformation of finite-state property automata
into a data structure which, on being presented with a current state and an input of ag-
gregated events, computes the set of possible and valid next states
e
ff
ciently
, within a
time bounded by the size of the structure rather than that of the input.
3
Constraint Automata
The following section introduces the notions of
constraints
and
constraint automata
,
defining their structure, evaluation and traversal.
3.1
Overview
The transitions in a finite-state automaton determine the number, type and order of input
elements required to move between states. In the scenario we consider, compressed in-
puts are
unordered
, containing information only pertaining to each element's frequency.
