Switched PIOA: Parallel composition via distributed scheduling

This paper presents the framework of switched probabilistic input/output automata (or switched PIOA), augmenting the original PIOA framework with an explicit control exchange mechanism. Using this mechanism, we model a network of processes passing a single token among them, so that the location of this token determines which process is scheduled to make the next move. This token structure therefore implements a distributed scheduling scheme: scheduling decisions are always made by the (unique) active component. Distributed scheduling allows us to draw a clear line between local and global nondeterministic choices. We then require that local nondeterministic choices are resolved using strictly local information. This eliminates unrealistic schedules that arise under the more common centralized scheduling scheme. As a result, we are able to prove that our trace-style semantics is compositional.

Authors

• Ling Cheung
• Nancy Lynch Massachusetts Institute of Technology
• Roberto Segala
• Frits Vaandrager

Keywords

• Switched probabilistic input/output automata
• Trace-style semantics
• Parallel composition
• Distributed scheduling
• Compositionality