Monitoring Event Frequencies

Thomas Ferrère, Thomas A. Henzinger, Bernhard Kragl

TL;DR

Exact real-time tracking of frequency statistics (such as the most frequent event or the median) over large alphabets requires an impractical number of counters—one for each possible event. This paper introduces limit monitoring, showing that under stochastic assumptions (modeled as connected Markov chains), we can monitor the mode, median, or composite linear frequency properties almost surely using just four counters, completely independent of alphabet size.

What Problem Does This Paper Address?

In runtime verification, a monitor observes an executing system to flag anomalies or compute performance metrics (e.g., identifying the most active IP address hitting a web server). Computing statistics like the mode (the most frequent event) or the median requires knowing event counts.

However, if your system uses IPv4 addresses (~4.3 billion possible events) or Unicode codepoints (~1.1 million), maintaining a separate counter for every single event is memory-prohibitive. The authors formally prove that exact, real-time monitoring of such statistics fundamentally requires $\Omega(|\Sigma|)$ counters, where $|\Sigma|$ is the alphabet size.

The paper asks: What if we don't need exact answers at every single step, but instead want an estimate that is guaranteed to converge to the true value over time?

Methods

The authors reframe the monitoring task from real-time evaluation to limit monitoring, where the monitor's output must almost surely converge to the true asymptotic limit of the statistic over an infinite random trace.

  1. Subword Chunking & Candidate Tournaments: Instead of tracking all events continuously across prefixes, the monitor splits the stream into subwords (chunks) of increasing length ($1, 2, 3, \dots$).

  2. For the mode monitor, it maintains two event registers: a current champion $x$ and a contender $y$ (sampled from the stream).

  3. Over a chunk, it counts occurrences of only $x$ and $y$. If $y$ appears at least as often as $x$, $y$ replaces $x$ as the new champion; otherwise, $x$ remains, and a new candidate $y$ is picked for the next round.
  4. Four integer counters suffice: two to count occurrences of $x$ and $y$ within the chunk, and two to track the current chunk length and position.
  5. Median & General Frequency Logic:
  6. A similar strategy tracks median candidates using four counters to evaluate whether candidates fall above or below the distribution split.
  7. The authors define a logic of frequency formulas (Boolean combinations of linear inequalities over event frequencies) and demonstrate that any such property can be limit-monitored with 4 counters by evaluating subformulas across alternating subwords.
  8. Ergodic Theory over Infixes: Classical ergodic theory guarantees that state frequencies converge over growing prefixes ($w_{1..n}$). Because this algorithm samples disjoint infixes (subwords), the authors formulate and prove a generalized ergodic theorem for connected Markov chains using rowwise-independent triangular random arrays.

Datasets

Not discussed in the paper. The work is purely theoretical and does not evaluate on empirical datasets or benchmarks.

Key Insights and Ideas

  • Limit Monitoring vs. Real-Time Monitoring: Relaxing the requirement from exact prefix-by-prefix reporting to asymptotic almost-sure convergence slashes the state-space requirement from linear in the alphabet size ($\Omega(|\Sigma|)$) down to a constant ($O(1)$).
  • The Infix Ergodic Theorem: Letter frequencies in a connected Markov chain do not just stabilize across entire histories; they stabilize across any sequence of arbitrarily placed infixes, provided the infix lengths grow fast enough (e.g., linearly).
  • Resource Independence: Whether tracking 3 events or 4 billion events, four counters are sufficient to discover and permanently settle on the true mode or median.

Key Results

  • Hardness Lower Bound: Any exact real-time counter monitor for $\Sigma$-counting statistics (which includes both mode and median) requires at least $\Omega(|\Sigma|)$ counters (Theorem 16).
  • Constant Memory Upper Bound:
  • An exact limit monitor for the mode requires only 4 counters (Theorem 22).
  • An exact limit monitor for the median requires only 4 counters (Theorem 23).
  • An exact limit monitor for any Boolean combination of linear frequency inequalities requires only 4 counters (Theorem 27).

Limitations and Future Work

  • Stochastic Requirement: The proofs assume the event generator is a finite, connected Markov chain. The algorithms do not directly transfer to adversarial or non-deterministic environments (such as Markov Decision Processes), where an adversary could strategically emit events only when the monitor is not inspecting them.
  • Convergence Rates (Time-Efficiency): While the algorithm is exceptionally memory-efficient, the paper does not provide general analytical bounds on time-efficiency (how many events must be observed to reach a target confidence interval), noting that expressions become intractable for alphabets with three or more letters.
  • Richer Specifications: Future extensions include investigating limit monitoring for properties featuring temporal modalities (like always or eventually) and studying convergence in probability alongside almost-sure convergence.

Summary updated

Abstract

The monitoring of event frequencies can be used to recognize behavioral anomalies, to identify trends, and to deduce or discard hypotheses about the underlying system. For example, the performance of a web server may be monitored based on the ratio of the total count of requests from the least and most active clients. Exact frequency monitoring, however, can be prohibitively expensive; in the above example it would require as many counters as there are clients. In this paper, we propose the efficient probabilistic monitoring of common frequency properties, including the mode (i.e., the most common event) and the median of an event sequence. We define a logic to express composite frequency properties as a combination of atomic frequency properties. Our main contribution is an algorithm that, under suitable probabilistic assumptions, can be used to monitor these important frequency properties with four counters, independent of the number of different events. Our algorithm samples longer and longer subwords of an infinite event sequence. We prove the almost-sure convergence of our algorithm by generalizing ergodic theory from increasing-length prefixes to increasing-length subwords of an infinite sequence. A similar algorithm could be used to learn a connected Markov chain of a given structure from observing its outputs, to arbitrary precision, for a given confidence.
BibTeX
@inproceedings{ferrere2020monitoring,
  author = {Thomas Ferrère and Thomas A. Henzinger and Bernhard Kragl},
  title = {{Monitoring Event Frequencies}},
  booktitle = {CSL},
  year = {2020},
  url = {https://openreview.net/forum?id=SLbF36JNZq},
}

Loading related content...

Figure