Synchronization of concurrent processes without globality assumptions
P. E. Lauer · ACM SIGPLAN Notices · 1981
I nt roduct i onThe advent of LSI and VLSI technology and microprogramming %echniques has greatly increased the number of choices a digital system designer has for decomposing a system into ultimate subsysfems which grow considerably more powerful and complex in function as technology progresses.Furthermore, designers have been learning how to combine such subsystems in new ways giving rise to systems which perform the same general functions as earlier systems but with a much greater degree of parallelism and distribution.We will be concerned with the general problem of the definition and analysis of sjnchronization in concu~Tent systems without the assumption of a global nature for such entities as the system clock, the system state, the control, the observer, eteoSystems without such g]obality assumptions will be called distributed.If a combination of subsystems is to cooperate coherently %o perform a particular system function synchronization is necessary to ensure proper joint behaviours of subsystems with respect %o any parts of the system they share.If the resulting system is distributed and capable of parallel behaviours in subsystems, then the required synchronization must be specified without recourse %o either a central clock, central control or global state.Many of the conventional formal tools the system designer has at his disposal, such as Automata Theory, are only suitable for adequately expressing sequential systems and they do this ~nder the assumption of a global system state.Hence, designers have had to support such formalisms with additional formal and informal notions when applying them to the specification and analysis of concurrent and distributed systems.