Time Models for Complex Distributed Discrete Systems

Abstract

The impetus for writing this article was the thesis about the inadequacy of using linearly-ordered time models in describing processes in complex discrete systems characterized by the presence of components with independent behavior between the moments of their interaction, with recursively defined, hierarchically organized, varying (dynamic) structure unlimited in complexity, and with non-deterministic behavior. The cause-and-effect relationships between possible events in a distributed multicomponent system leading to changes in its state determine, among other things, the minimally necessary partial order in the set of time instants corresponding to possible events in the system. The time universe is understood to mean the class of isomorphic finite partially-strictly ordered sets as a necessary basic formalism. The above-mentioned concept differs from other well-known formalizations (such as acyclic digraphs, Hasse diagrams, etc.) in that it uses a strictly partial order under the assumption that the set of simultaneous events in the system can be considered as one complex event. The presence of the above-mentioned features of complex systems generates the need to analyze the sets of time universes both in view of possible non-determinism in the behavior of systems and as a consequence of changes resulting from events associated with the system structure itself and the cause-and-effect relationships acting in it. The problem of developing a constructive description—with different degrees of complexity—of time universe sets, primarily infinite ones, which is similar to specifying formal languages as sets of words in a certain alphabet. The authors have solved a similar problem in the theory of directed relationships - the basic formalism for constructing declarative programming languages using the network representation of directed relationships. The key point of such solution is to correctly define the operation of substituting a network into another network instead of some element thereof, which plays the role of entering the network variable into the network structure and has the same specifications as the substituted network. The T-network and T-network language notions introduced in the article, i.e., sets of T-networks, are used to constructively specify the sets of time universes in modeling parallel processes in systems. The main syntactic difference between T-networks and networks of directed relationships is the requirement that T-networks shall not contain cycles, which is ensured by fulfilling certain proposed restrictions posed to network components. The correctness of the substitution operation with respect to these restrictions is proven. The substitution operation can be used both for hierarchically constructing T-networks and for multivariate and recursive assignment of T-network sets. Application of the substitution operation for defining a representative class of context-free T-network languages using context-free T-network grammars is described. A simple grammar example describing the time model for parallel recursive calculation of a definite integral is given, and further research lines are pointed out.