A Distributed Approach to LARS Stream Reasoning (System paper)

Thomas Eiter, Paul Ogris, Konstantin Schekotihin

TL;DR

This paper introduces a distributed architecture for LARS (Logic-based framework for Analytic Reasoning over Streams), moving away from the performance bottlenecks of traditional stand-alone solvers. By implementing a novel interval-based semantics and program stratification, the authors achieved up to a 500% increase in throughput, enabling complex logic-based decision-making on high-speed data streams that were previously unmanageable.

What Problem Does This Paper Address?

Stream reasoning is the "brain" behind real-time systems like the Internet of Things (IoT) and Cyber-Physical Systems. It requires making complex, declarative decisions based on infinite, fast-moving data.

The current state-of-the-art utilizes the LARS language, but existing solvers (like Ticker or Laser) are typically monolithic. They run on a single machine and often struggle as data rates climb or the logic becomes more complex. Specifically, many systems suffer from "tick-overload," where the reasoner re-evaluates the entire state at every time point, even if nothing has changed. This creates a massive scalability gap when trying to deploy these systems in cloud environments or on multi-core hardware.

Methods

The authors propose a "divide and conquer" approach through two primary innovations:

  1. Interval-based Semantics: Instead of communicating the state of an atom at every single "tick" (e.g., "Sensor A is High at $t=1, t=2, t=3$"), the system uses intervals (e.g., "Sensor A is High for $[1, 3]$"). This drastically reduces network traffic between distributed components.
  2. Stream Stratification & Component Graphs: The system analyzes the LARS program to find dependencies. It builds a Dependency Graph to identify which parts of the logic can be calculated independently or sequentially. It then produces a Component Graph, allowing a Master Node to spawn individual reasoner nodes across a network. Each node is responsible for a "layer" of the reasoning process.

The implementation uses Answer Set Programming (ASP) solvers (specifically clingo) as the underlying engine for each node, utilizing external functions to efficiently query a custom in-memory interval database.

Datasets

The system was evaluated using two primary benchmarks:

  • Content Caching Scenario: A practical use case involving Content Centric Networks (CCN). Routers must autonomously decide which data "chunks" to cache based on shifting consumer demand patterns.
  • Chained n-Queens Completion: A synthetic, high-complexity benchmark. The authors adapted the classic n-Queens combinatorial problem into a streaming format where the solution of one step depends on the previous one. This was specifically chosen to test the system's ability to handle "odd loops" and complex constraints that break simpler incremental solvers.

Key Insights and Ideas

  • Communication is the Bottleneck: In a distributed reasoning system, the cost of moving data can outweigh the benefits of parallel processing. The shift to interval-based communication is the "aha moment" that makes distribution viable for LARS.
  • Lazy Evaluation in Logic: Unlike traditional solvers that "tick" constantly, the distributed nodes in this system practice a form of lazy evaluation. A downstream node only wakes up and performs work if an upstream node produces a change in its interval stream.
  • Handling Non-Monotonicity: By including negation in their dependency analysis, the authors ensure that "choices" in the logic are resolved in the correct order across the distributed pipeline, maintaining the mathematical integrity of the Answer Set Programming paradigm.

Key Results

  • Massive Throughput Gains: In the n-Queens benchmark, the distributed approach handled 500% more throughput than a single-node configuration. As the number of pipeline stages increased, the distributed system maintained low latency while the single-node version became completely saturated.
  • Superior Logic Handling: The system successfully solved problems involving "odd loops" and complex integrity constraints that the incremental JTMS (Justification-based Truth Maintenance System) used in Ticker could not solve at all.
  • Reduced CPU Overhead: Because of the interval-based "lazy" approach, the Distributed-ASP setup performed significantly less redundant work than traditional "always-ticking" solvers.

Limitations and Future Work

While a significant step forward, the authors note a few areas for improvement:

  • Window Support: The current prototype primarily supports time-based sliding windows; support for tuple-based windows (e.g., "the last 10 items") is not yet implemented.
  • Recursion Constraints: The system currently requires programs to be "stream-stratified," meaning it cannot handle recursion that goes through window operators.
  • Future Directions: The team aims to incorporate aggregates (like sums or averages) as first-class citizens in the interval framework and explore "on-the-fly" grounding to further speed up the individual ASP nodes. They also plan to tackle non-stratified programs to allow for even more expressive distributed logic.

Summary updated

Abstract

Stream reasoning systems are designed for complex decision-making from possibly infinite, dynamic streams of data. Modern approaches to stream reasoning are usually performing their computations using stand-alone solvers, which incrementally update their internal state and return results as the new portions of data streams are pushed. However, the performance of such approaches degrades quickly as the rates of the input data and the complexity of decision problems are growing. This problem was already recognized in the area of stream processing, where systems became distributed in order to allocate vast computing resources provided by clouds. In this paper we propose a distributed approach to stream reasoning that can efficiently split computations among different solvers communicating their results over data streams. Moreover, in order to increase the throughput of the distributed system, we suggest an interval-based semantics for the LARS language, which enables significant reductions of network traffic. Performed evaluations indicate that the distributed stream reasoning significantly outperforms existing stand-alone LARS solvers when the complexity of decision problems and the rate of incoming data are increasing.
BibTeX
@inproceedings{eiter2019distributed,
  author = {Thomas Eiter and Paul Ogris and Konstantin Schekotihin},
  title = {{A Distributed Approach to LARS Stream Reasoning (System paper)}},
  booktitle = {Theory Pract. Log. Program},
  year = {2019},
  url = {https://openreview.net/forum?id=9ma4JtkEt7},
}

Loading related content...

Figure