  A causal set is a partially ordered set on a countably infinite ground-set
such that each element is above finitely many others. A natural extension of a
causal set is an enumeration of its elements which respects the order. We bring
together two different classes of random processes. In one class, we are given
a fixed causal set, and we consider random natural extensions of this causal
set: we think of the random enumeration as being generated one point at a time.
In the other class of processes, we generate a random causal set, working from
the bottom up, adding one new maximal element at each stage. Processes of both
types can exhibit a property called order-invariance: if we stop the process
after some fixed number of steps, then, conditioned on the structure of the
causal set, every possible order of generation of its elements is equally
likely. We develop a framework for the study of order-invariance which includes
both types of example: order-invariance is then a property of probability
measures on a certain space. Our main result is a description of the extremal
order-invariant measures.
