A Policy Description Language

AAAI 1999

TL;DR

This paper introduces PDL, a novel language for formally describing policies as functions mapping event sequences to actions. PDL offers a declarative, implementation-independent semantics, drawing inspiration from action languages and active databases, to simplify policy specification and enable efficient implementation in systems like soft switches.

What Problem Does This Paper Address?

In system management, policies are crucial for defining strategies to achieve goals, ranging from high-level organizational principles to technical configurations like network traffic management. While policies can be expressed in natural language or low-level production rules, there's a need for an intermediate, computationally effective approach. Existing definitions of policies often map states to actions, but this paper argues for a more dynamic model: policies as functions that react to sequences of events and trigger actions. This is particularly relevant for managing complex, dynamic systems where continuous monitoring and reactive behavior are essential. The paper aims to bridge the gap between informal policy descriptions and their precise, executable implementation.

Methods

The core contribution is the Policy Description Language (PDL). PDL defines a policy as a function that maps a series of events to a set of actions. The language is built around the event-condition-action (ECA) paradigm, common in active databases.

Key aspects of PDL include:

  • Event Semantics: PDL handles various event types, including primitive system-defined events, user-defined primitive events, and complex events constructed from sequences, repetitions, and combinations of other events. It introduces the concept of "policy-defined primitive events" to provide a limited form of memory within policies.
  • Policy Rules: Policies are expressed as propositions of the form "event causes action if condition." This allows for reactive behavior triggered by specific event occurrences under certain conditions.
  • Formal Semantics: The paper defines a formal, implementation-independent semantics based on event histories and transition functions, drawing from automata theory and logic programming. This rigorous foundation is crucial for predictable policy behavior.
  • Implementation: The paper discusses the implementation of a "policy server" that interprets PDL specifications and executes policies in real-world systems, such as soft switches in telecommunication networks.

Datasets

Not discussed in the paper. The paper focuses on the language design and its formal semantics, using illustrative examples rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Events as Triggers, Not Just States: Shifting from state-based policies to event-driven policies (event sequences mapping to actions) provides a more natural and powerful way to model dynamic system behavior.
  • Policy-Defined Primitive Events: The introduction of policy-defined primitive events is a clever mechanism to imbue policies with a limited, controllable memory, allowing them to react to past events in a structured way without requiring a full state representation.
  • Declarative and Implementation-Independent Semantics: The formal semantics based on event histories and transition functions is a significant contribution, ensuring that policy behavior is predictable and not tied to specific implementation details. This is crucial for debugging and verifying complex policies.
  • Bridging the Gap: PDL effectively bridges the gap between informal, high-level policy descriptions and their precise, executable implementations, making policy management more accessible and reliable.

Key Results

The paper presents a formal language (PDL) and its semantics, along with a discussion of its implementation in a policy server. While specific quantitative results are not the primary focus, the paper establishes:

  • A formal framework for describing policies as functions from event histories to actions.
  • A language (PDL) with syntax and semantics for specifying these policies.
  • A discussion of complexity: The paper notes that even restricted versions of policy evaluation are NP-Hard, highlighting the inherent complexity of temporal reasoning in policies.
  • An implemented policy server used in a soft switch for telecommunication networks, demonstrating the practical applicability of PDL.

Limitations and Future Work

  • Complexity: The authors acknowledge that policy evaluation can be computationally expensive, with even restricted cases being NP-Hard. This suggests that efficient algorithms are crucial for practical deployment.
  • Expressiveness vs. Tractability: While PDL aims for expressiveness, there's a trade-off with computational tractability. The paper hints at designing efficient algorithms for practical policy scenarios where description sizes are bounded.
  • Consistency and Interaction: Future work is suggested in reasoning about policies, specifically checking for conflicting actions between rules and understanding inter-policy interactions. The authors plan to address consistency issues in a future paper.
  • Language Evolution: The authors view PDL as an initial proposal and expect the language to evolve based on practical experience and further research.

Summary updated

BibTeX
@inproceedings{1999policy,
  title = {{A Policy Description Language}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1999},
}
Figure