Connectedness and synchronization (Q1179707)

This aper is a presentation of another mathematical model to describe semantics of systems of concurrent processes. The processes are assumed to be defined by events to which they can respond, or in which they can engage. The presentation starts from a list of four models that have already been defined in the literature. The four models describe compositions of: linear (sequential) processes (e.g. \(CSP)\), pomset (partially ordered multiset) processes (e.g. Petri nets), automaton (defined by transition diagrams) processes (e.g. \(CCS\)), and event or behaviour structures (nets in general). The authors extend this list by so-called connected relations. The purpose of the new, fifth model is to capture algebraically concurrent systems that have so far eluded rigorous mathematical treatment as too complicated in any of the four models mentioned above. The connected relations model is promised to cope with systems such as \(P/T\) nets (the more sophisticated Petri nets) and data flow networks. Connected relations can be defined for a variety of domains which may satisfy different finiteness conditions (generally, \(F\)-domains). For the domain of natural numbers, connected relations have been known under the name of multitrees. As in the four previous models, in connected relations there are basic process structurig operations: synchronization (combining processes to act concurrently), union (choice between processes), and hiding (elimination of events from the given combination of processes). Unlike in the four previous models, here processes may have values defined as connected relations in the corresponding \(F\)-domain. If some relations in the \(F\)-domain is a value of a process, the process is said to implement the relation. The paper contains 2 examples how the connected relations model can be applied to data flow systems. Both are concerned with the problem of message passing in such systems. One is a description of data flow stream processing, and the other --- processing of streams with ``holes''.