A Distributed Logic for Networked Cyber-Physical Systems


Kim, M., Stehr, M.-O., & Talcott, C. (2013). A distributed logic for Networked Cyber-Physical Systems. Science of Computer Programming, 78(12), 2453-2467.


We describe a distributed logical framework designed to serve as a declarative semantic foundation for Networked Cyber-Physical Systems. The framework provides notions of facts and goals that include interactions with the environment via external goal requests, observations that generate facts, and actions that achieve goals. Reasoning rules are built on a partially ordered knowledge-sharing model for loosely coupled distributed computing. The logic supports reasoning in the context of dynamically changing facts and system goals. It can be used both to program systems and to reason about possible scenarios and emerging properties.

The underlying reasoning framework is specified in terms of constraints that must be satisfied, making it very general and flexible. Inference rules for an instantiation to a specific local logic (Horn clause logic) are given as a concrete example. The key novel features are illustrated with snippets from an existing application—a theory for self-organizing robots performing a distributed surveillance task. Traditional properties of logical inference and computation are reformulated in this novel context, and related to features of system design and execution. Proofs are outlined for key properties corresponding to soundness, completeness, and termination. Finally, the framework is compared to other formal systems addressing concurrent/distributed computation.

Read more from SRI