Event structures were introduced in order to abstract away from the precise ‘places’ and times at which events occur in distributed systems. The structure focuses on the events and the causal ordering between them.
An event structure, , consists of a poset of events, where the partial order relation expresses causal dependency, together with a symmetric irreflexive relation , called incompatibility . This data is to satisfy
Let be an event structure. Define its set of configurations, , to consist of those subsets , which are
A morphism of event structures consists of a partial function such that
This second condition says that if both and are defined and either or , then either , or .
Winskel and Neilsen explain the definition as follows:
A morphism between event structures expresses how behaviour in determines behaviour in . The partial function, , expresses how the occurrence of an event in implies the simultaneous occurrence of an event in ; the fact that can be understood as expressing that the event is a ”component” of the event and, in this sense, that the occurrence of implies the simultaneous occurrence of . If two distinct events in have the same image in under then they cannot belong to the same configuration.
(There is more discussion of the notion of morphism of event structures in the notes referred to below.)
With this definition of morphism, we get the category, of event structures.
In some sources, rather than stress the inconsistency relation, the complementary consistency relation. This leads to the definition of a family, , of finite subsets of , which satisfy
for all ;
G. Winskel, Events, causality, and symmetry, (an earlier version appeared in the BCS conference ‘Visions in Computer Science.’ September 2008. The final version appears in a special issue of The Computer Journal 2009; doi: 10.1093/comjnl/bxp052; see also an online version).