Title: Synthesis of Optimal Resilient Control Strategies,
Abstract: Repair mechanisms are important within resilient systems to maintain the
system in an operational state after an error occurred. Usually, constraints on
the repair mechanisms are imposed, e.g., concerning the time or resources
required (such as energy consumption or other kinds of costs). For systems
modeled by Markov decision processes (MDPs), we introduce the concept of
resilient schedulers, which represent control strategies guaranteeing that
these constraints are always met within some given probability. Assigning
rewards to the operational states of the system, we then aim towards resilient
schedulers which maximize the long-run average reward, i.e., the expected mean
payoff. We present a pseudo-polynomial algorithm that decides whether a
resilient scheduler exists and if so, yields an optimal resilient scheduler. We
show also that already the decision problem asking whether there exists a
resilient scheduler is PSPACE-hard.