AN ALGEBRAIC MODEL OF COMPUTATION FOR SYSTEMS WITH DYNAMIC STRUCTURE

We introduce the Structure Model- a formalism for modelling and controlling networked systems with dynamic structure. The pervasiveness of networked computing devices is raising attention on models of computation which entail the network structure as a first-class concept. Modelling how the network evolves and how entities interact is now paramount for a correct understanding of the overall system and for the design and synthesis of effective controllers. We address this problem by introducing a formalism for modelling and controlling systems with dynamic structures. The Structure Model (SM) consists of a set of entities, and a set of unary relations and a binary relation over the set of entities. The unary relations are used to model state properties of the entities while the binary relation is used to model interaction between entities such as communication. The SM can be manipulated using a set of algebraic operators. The dynamics of the structure are modelled using a transition system. The SM is designed to compose with an underlying model that describes the entities behaviour. We present how the structure can be abstracted from an underlying model and how the changes at the structure level can be propagated back to the system. This provides means controlling the system from a structure perspective. The structure model aims at being agnostic to the underlying model of computation. In this work we compose the structure model with Nancy Lynch’s Synchronous Network Model and present a case study using a version of the “agree and pursue ” communication and control law