Synthesizing Dominant Strategies for Liveness

Bernd Finkbeiner, Noemi Passing

TL;DR

This paper introduces "delay-dominance," a new concept for synthesizing strategies in complex systems, particularly distributed ones. It allows strategies to deviate from a specification in certain situations if no other strategy could have succeeded, making it compositional for liveness properties, unlike previous dominance notions. This enables a more robust approach to automatically generating strategies for distributed systems.

What Problem Does This Paper Address?

Reactive synthesis aims to automatically generate strategies (like control programs) that ensure a system meets a formal specification. However, requiring a strategy to always satisfy the specification (a "winning strategy") is often too strict, especially in distributed systems where multiple components must cooperate. Individual components might not have winning strategies on their own because their behavior is intertwined with others.

Previous work introduced "remorsefree dominance," a weaker notion where a strategy is allowed to fail if no other strategy could have succeeded. This is useful for compositional synthesis (breaking down the problem for individual components). However, remorsefree dominance only guarantees compositionality for "safety" properties (preventing bad things from happening), not "liveness" properties (ensuring good things eventually happen). This limits its applicability to more expressive specifications. "Bounded dominance" was an attempt to fix this but required choosing an arbitrary bound on "non-progress" steps, which was problematic.

This paper addresses the need for a compositional synthesis approach that works for both safety and liveness properties, overcoming the limitations of existing dominance notions.

Methods

The core contribution is the introduction of delay-dominance. This new winning condition for strategies is defined using a game-theoretic approach, specifically a "delay-dominance game." This game is played between a "Duplicator" (representing the strategy being tested) and a "Spoiler" (representing an alternative strategy).

Key aspects of the method include:

  • Automaton-based definition: Delay-dominance is defined with respect to an alternating co-Büchi automaton (ACA) representing the LTL specification. This allows for measuring progress beyond just satisfying the specification.
  • Game-theoretic definition: The delay-dominance game formalizes the condition. Intuitively, a strategy s delay-dominates another strategy t if, whenever s makes a "non-progress" step (visiting a rejecting state in the ACA), t also eventually makes a non-progress step. The Duplicator wins if every rejecting state visited by the "dominant" strategy is eventually matched by a rejecting state visited by the "alternative" strategy.
  • Compositionality for Liveness: The authors prove that delay-dominance is compositional for many liveness properties, a significant improvement over remorsefree dominance. This is achieved by introducing a "bad prefixes" criterion for ACAs.
  • Automaton Construction: They present a construction for an automaton that recognizes delay-dominant strategies. This automaton is a universal co-Büchi automaton (UCA) and can be used with existing synthesis tools.
  • Complexity Analysis: The resulting automaton is shown to be single-exponential in the squared length of the specification, and synthesizing delay-dominant strategies is in 2EXPTIME, matching the complexity of winning strategy synthesis.

Datasets

Not discussed in the paper. The paper focuses on theoretical foundations and algorithmic constructions rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Bridging the Gap for Liveness: The most significant insight is the development of delay-dominance, which successfully extends compositional synthesis to liveness properties. This is achieved by moving beyond simple specification satisfaction to analyzing the progress made by strategies relative to an automaton.
  • Game-Theoretic Nuance: The delay-dominance game elegantly captures the "as good as any alternative" intuition. The roles of Duplicator and Spoiler, and the order of their moves, are crucial for correctly defining the condition.
  • Automata as Progress Meters: Using ACAs and their rejecting states as a measure of progress (or lack thereof) is a powerful technique. It allows distinguishing between strategies that simply fail and those that fail in a way that is "better" or "no worse" than any other option.
  • Compositionality is Achievable: The paper demonstrates that compositionality for liveness properties is possible with the right notion of dominance, provided the underlying automaton has certain properties (the "bad prefixes" criterion).

Key Results

  • Delay-Dominance: A new winning condition for strategies that is compositional for many safety and liveness properties.
  • Compositionality Guarantee: A criterion for ACAs that ensures the compositionality of delay-dominant strategies.
  • Remorsefree Dominance Implication: Every delay-dominant strategy is also remorsefree dominant.
  • Winning Strategy Guarantee: For realizable specifications, if a delay-dominant strategy exists and the compositionality criterion is met, the composed strategy is winning for the whole system.
  • Automaton Construction: A sound and complete UCA for recognizing delay-dominant strategies, with a size single-exponential in the squared length of the LTL specification.
  • Complexity: Synthesis of delay-dominant strategies is in 2EXPTIME, matching existing bounds for winning strategies.

Limitations and Future Work

  • "Punishing" Automata: The authors acknowledge that for certain ACAs (even those derived from standard LTL-to-automaton translations), delay-dominance might not exist. This can happen if the ACA has "unnecessary" rejecting states that don't affect language acceptance but can "punish" strategies, preventing them from being delay-dominant.
  • Bad Prefixes Criterion: The compositionality guarantee relies on the ACA satisfying the "bad prefixes" criterion. While the authors suggest standard LTL-to-ACA constructions often satisfy this, it's not universally guaranteed. Future work could explore how to ensure this criterion or handle cases where it's not met.
  • Practical Applicability: While the theoretical framework is strong, further work could focus on the practical implementation and performance of the proposed synthesis algorithm, especially for large-scale distributed systems.
  • Optimization of ACAs: The paper mentions that simple optimizations to ACAs (like removing non-cyclic rejecting states) can improve the existence of delay-dominant strategies and ensure the bad prefixes property. Further research into optimal ACA construction for delay-dominance synthesis would be valuable.

Summary updated

Abstract

Reactive synthesis automatically derives a strategy that satisfies a given specification. However, requiring a strategy to meet the specification in every situation is, in many cases, too hard of a requirement. Particularly in compositional synthesis of distributed systems, individual winning strategies for the processes often do not exist. Remorsefree dominance, a weaker notion than winning, accounts for such situations: dominant strategies are only required to be as good as any alternative strategy, i.e. , they are allowed to violate the specification if no other strategy would have satisfied it in the same situation. The composition of dominant strategies is only guaranteed to be dominant for safety properties, though; preventing the use of dominance in compositional synthesis for liveness specifications. Yet, safety properties are often not expressive enough. In this paper, we thus introduce a new winning condition for strategies, called delay-dominance, that overcomes this weakness of remorsefree dominance: we show that it is compositional for many safety and liveness specifications, enabling a compositional synthesis algorithm based on delay-dominance for general specifications. Furthermore, we introduce an automaton construction for recognizing delay-dominant strategies and prove its soundness and completeness. The resulting automaton is of single-exponential size in the squared length of the specification and can immediately be used for safraless synthesis procedures. Thus, synthesis of delay-dominant strategies is, as synthesis of winning strategies, in 2EXPTIME.
BibTeX
@inproceedings{finkbeiner2022synthesizing,
  author = {Bernd Finkbeiner and Noemi Passing},
  title = {{Synthesizing Dominant Strategies for Liveness}},
  booktitle = {FSTTCS},
  year = {2022},
  doi = {10.4230/lipics.fsttcs.2022.37},
}

Loading related content...

Figure