|
Comparing models of computation
Abstract:
We give a denotational framework (a "meta model") within which certain
properties of models of computation can be understood and compared. It
describes concurrent processes as sets of possible behaviors. Compositions of
processes are given as intersections of their behaviors. The interaction
between processes is through signals, which are collections of events. Each
event is a value-tag pair, where the tags can come from a partially ordered or
totally ordered set. Timed models are where the set of tags is totally
ordered. Synchronous events share the same tag and synchronous signals contain
events with the same set of tags. Synchronous systems contain synchronous
signals. Strict causality (in timed systems) and continuity (in untimed
systems) ensure determinacy under certain technical conditions. The framework
is used to compare certain essential features of various models of computation,
including Kahn process networks, dataflow, sequential processes, concurrent
sequential processes with rendezvous, Petri nets, and discrete-event systems.
UCB Design Technology Warehouse Homepage
|