A Distributed Approach to LARS Stream Reasoning (System paper)

Thomas Eiter, Paul Ogris, Konstantin Schekotihin

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.

Introduction

Stream reasoning serves as the analytical core for real-time systems in the Internet of Things (IoT) and Cyber-Physical Systems. These environments require making complex, declarative decisions based on infinite, high-velocity data streams. Currently, the Logic-based framework for Analytic Reasoning over Streams (LARS) is the state-of-the-art language for such tasks. However, existing LARS solvers, such as Ticker or Laser, are typically monolithic.

These stand-alone solvers run on single machines and often encounter a "scalability gap" as data rates increase or logic becomes more intricate. A primary bottleneck is "tick-overload," where the reasoner re-evaluates the entire state at every discrete time point (tick), even when the underlying data hasn't changed. This paper addresses these limitations by proposing a distributed architecture that leverages cloud resources and introduces a more efficient communication paradigm.

Methodology: Distributed Architecture and Interval Semantics

The proposed system moves away from monolithic processing through two primary innovations: stream stratification and interval-based semantics.

Interval-based Semantics

Traditional LARS solvers communicate the state of an atom at every single tick. For instance, if a sensor reports a "High" state from $t=1$ to $t=10$, a traditional solver processes ten individual data points. The authors introduce an interval-based semantics where this is represented as a single interval $[1, 10]$. This shift drastically reduces the volume of data transmitted between distributed components.

Comparison of standard LARS streams and the proposed interval-based semantics.

As shown in the figure above, the interval stream provides a compressed representation of the LARS stream, allowing for "lazy evaluation." Downstream nodes only activate when an upstream node signals a change in an interval, rather than reacting to every clock tick.

Stream Stratification and Component Graphs

To distribute the workload, the system analyzes the LARS program to identify dependencies. It constructs a Dependency Graph to determine which logical components can be computed independently or must be processed sequentially. This leads to a Component Graph, which a Master Node uses to deploy individual reasoner nodes across a network. Each node utilizes Answer Set Programming (ASP) solvers (specifically clingo) to handle its specific layer of the reasoning process, querying a custom in-memory interval database to maintain state.

Experimental Evaluation

The system's performance was validated using two distinct benchmarks designed to test real-world utility and synthetic complexity.

Content Caching Scenario

This benchmark involves Content Centric Networks (CCN), where routers must autonomously decide which data "chunks" to cache based on shifting consumer demand. This requires the system to handle dynamic data and make localized decisions that affect global network efficiency.

The Content Caching Scenario used for system evaluation.

Chained n-Queens Completion

To test high-complexity logic, the authors adapted the n-Queens combinatorial problem into a streaming format. In this synthetic benchmark, the solution of one step depends on the previous one, creating complex constraints and "odd loops." This specifically tested the system's ability to handle non-monotonicity and integrity constraints that often break simpler incremental solvers.

Key Results and Discussion

The distributed approach demonstrated significant advantages over traditional stand-alone solvers:

  • Throughput Gains: In the n-Queens benchmark, the distributed system achieved a 500% increase in throughput compared to a single-node configuration. While single-node solvers became saturated as complexity grew, the distributed pipeline maintained low latency.
  • Logical Robustness: The system successfully resolved complex integrity constraints and "odd loops" that the incremental Justification-based Truth Maintenance Systems (JTMS) used in other solvers could not process.
  • Efficiency: The combination of interval-based communication and lazy evaluation significantly reduced CPU overhead by eliminating redundant computations at every tick.

Conclusion and Future Work

This research demonstrates that distributing LARS reasoning is not only viable but essential for high-speed, complex stream processing. By shifting to interval-based semantics, the system overcomes the communication bottlenecks typical of distributed logic systems.

Future work will focus on expanding the framework to support tuple-based windows (e.g., "the last 10 items") and incorporating aggregates like sums or averages as first-class citizens. Additionally, the team plans to explore "on-the-fly" grounding and techniques to handle non-stratified programs, further increasing the expressive power of distributed stream reasoning.

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. Under consideration for acceptance in Theory and Practice of Logic Programming.
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},
}
Figure