Knowledge for achieving distributed control

Susanne Graf


How to obtain distributed implementations from global specifications has been studied in the past from the perspectives of different application domains, under different assumptions and for different constraints. We reconsider here this topic from a knowledge perspective: when does an individual process have sufficient knowledge to start a some action which is supposed to be either the local part of a larger action involving several processes or a local action potentially in conflict with some other action?

Without restriction of generality, we represent here global specifications by Petri Nets with priorities and a distributed implementation by particular Petri Nets augmented with attributes representing knowledge. At the semantic level, we consider event structures. Without aiming at exhaustivity, we then propose a set of implementation relations consisting of a safety and a progress condition in order to define possible correctness criteria.

We consider a set of elementary properties which are typically used in such distributed controllers. We then discuss different means for guaranteeing knowledge of such properties. This allows us then to either derive from global specification distributed solutions that are optimal with respect to some QoS criteria or to prove the correctness of a given distributed controller at a relatively abstract level.

Presentation Slides