A Distributed Computing Model for Dataflow, Controlflow, and Workflow in Fractionated Cyber-Physical Systems

Abstract

With the ongoing trend to parallelize computations for scalability, better performance, and reliability, distributed dataflow models are attracting interest at all design levels, ranging from processorarchitectures to local- and wide-area computing clusters in the cloud. Data-driven computation has also been an important paradigm in sensor networks and embedded systems, which have evolved into a larger research effort on networked cyber-physical systems (NCPS), that can sense and affect their environment. Fractionated cyber-physical systems (FCPS) are an interesting subclass of NCPS where the redundancy and diversity of many unreliable and potentially heterogeneous networked components is exploited to improve scalability, reliability, and verifiability of the overall system. In this paper we present the theory of a new distributed computing model for such systems as a first step toward a model-based design methodology for FCPS. To uniformly capture dataflow, controlflow, and workflow, we use a subclass of Petri nets as an intuitive high-level model, which is translated into a weaker model — namely, a new variant of Petri nets that does not make any atomicity assumptions but instead uses a partial order to ensure eventual consistency. In the full version of this paper, we briefly discuss an application to unmanned aerial vehicle (UAV) swarms, which has been implemented on top of a prototype of our theory for both simulation models and real world deployments.