Given a set of interacting components with non-deterministic variable update and given safety requirements, the goal of priority synthesis is to restrict, by means of priorities, the set of possible interactions in such a way as to guarantee the given safety conditions for all possible runs. In distributed priority synthesis we are interested in obtaining local sets of priorities, which are deployed in terms of local component controllers sharing intended next moves between components in local neighborhoods only. These possible communication paths between local controllers are specified by means of a communication architecture. We formally define the problem of distributed priority synthesis in terms of a multi-player safety game between players for (angelically) selecting the next transition of the components and an environment for (demonically) updating uncontrollable variables; this problem is NP-complete. We propose several optimizations including a solution-space exploration based on a diagnosis method using a nested extension of the usual attractor computation in games together with a reduction to corresponding SAT problems. When diagnosis fails, the method proposes potential candidates to guide the exploration. These optimized algorithms for solving distributed priority synthesis problems have been integrated into our VissBIP framework. An experimental validation of this implementation is performed using a range of case studies including scheduling in multicore processors and modular robotics.
@cite_10: We present the tool Sycraft (SYmboliC synthesizeR and Adder of Fault-Tolerance). In Sycraft , a distributed fault-intolerant program is specified in terms of a set of processes and an invariant. Each process is specified as a set of actions in a guarded command language, a set of variables that the process can read, and a set of variables that the process can write. Given a set of fault actions and a specification, the tool transforms the input distributed fault-intolerant program into a distributed fault-tolerant program via a symbolic implementation of respective algorithms.
@cite_7: In this paper, we concentrate on automated synthesis of fault recovery mechanism for fault-intolerant component-based models that encompass a cyber-physical system. We define the notion of fault recovery for cyber-physical component-based models. We also present synthesis constraints that preserve the correctness and cyber-physical nature of a given fault-intolerant model under which recovery can be added. We show that the corresponding synthesis problem is NP-complete and consequently introduce symbolic heuristics to tackle the exponential complexity. Our experimental results validate effectiveness of our heuristics for relatively large models.
Bonakdarpour, Kulkarni and Lin @cite_7 propose methods for adding for fault-recoveries for BIP components. The algorithms in @cite_10 @cite_7 are orthogonal in that they add additional behavior, for example new transitions, for individual components instead of determinizing possible interactions among components as in distributed priority synthesis @. However, distributed synthesis as described by @cite_10 on distributed synthesis is restricted to local processes without joint interactions between components @.