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_9: In distributed systems, local controllers often need to impose global guarantees. A solution that will not impose additional synchronization may not be feasible due to the lack of ability of one process to know the current situation at another. On the other hand, a completely centralized solution will eliminate all concurrency. A good solution is usually a compromise between these extremes, where synchronization is allowed for in principle, but avoided whenever possible. In a quest for practicable solutions to the distributed control problem, one can constrain the executions of a system based on the pre-calculation of knowledge properties and allow for temporary interprocess synchronization in order to combine the knowledge needed to control the system. This type of control, however, may incur a heavy communication overhead. We introduce the use of simple supervisor processes that accumulate information about processes until sufficient knowledge is collected to allow for safe progression. We combine the knowledge approach with a game theoretic search that prevents progressing to states from which there is no way to guarantee the imposed constraints.
@cite_11: Distributed control for enforcing a global invariant can be achieved based on calculating the knowledge of processes. When the local knowledge of individual processes is insufficient, processes can temporarily join their knowledge by means of synchronization. While synchronization can be used to guarantee progress, it is computationally expensive and should be used sparsely. In this paper, we introduce several solutions for minimizing the synchronization overhead. One possibility is to calculate the knowledge of a process of whether or not the system can progress without it. This knowledge can be used by the process to avoid unnecessary synchronization. Because of the distributed nature of the system, mutual passing of responsibility, based on such knowledge may result in deadlocks. We discuss three independent solutions to this problem. Our first solution breaks the symmetry between processes in order to avoid such situations, while our second solution is based on chance (coin tossing). Finally, we use automatically constructed stable properties to increase the joint knowledge of processes in order to minimize the number of processes that need to interact.
Starting with an arbitrary controller Katz, Peled and Schewe @cite_9 @cite_11 propose a knowledge-based approach for obtaining a decentralized controller by reducing the number of required communication between components. This approach assumes a fully connected communication structure, and the approach fails if the starting controller is inherently non-deployable.