Paper Info
Title
Synchronisationsgraphen
Abstract
There is an increasing demand for a new type of mathematical systems theory which would include treatment of non-trivial synchronization problems and thus could serve as a tool for design and implementation of information systems. Such systems can be characterized as dynamical systems consisting of many concurrently working information processing elements, e.g. computers and/or human beings.As a basis for studying these information systems a better understanding of the fundamental characteristics of information flow is required. One such characteristic is the simple synchronization of the flow of messages. A mathematical model for this synchronization is a directed graph along the paths of which tokens (objects with no properties) can move. Transition of tokens across a vertex of a path is effected by elementary events. An event may occur at a vertex whenever there is at least one token on each incoming edge of this vertex. With each occurrence of an event the number of tokens on each incoming edge is decreased by one, an on each outgoing edge is increased by one. These graphs shall be called synchronization graphs.The mathematical properties of synchronization graphs are studied in this paper. The discussion centers on necessary and sufficient conditions for liveness (exclusion of deadlocks) and safety (observance of capacity limits). The relationship between synchronization graphs and Linear Algebra is demonstrated and used both to obtain theoretical results and to offer practical methods for systems analysis.
Year
DOI
Venue
1973
10.1007/BF00264027
Acta Inf.
DocType
Volume
Issue
Journal
2
2
Citations 
PageRank 
References 
3
0.96
5
Authors
2
Name
Order
Citations
PageRank
Hartmann J. Genrich1339162.18
Kurt Lautenbach2250130.15