Depending on the context in which it is used, non-determinism can mean different things. One definition is having multiple possible traces through the state space of a system. Another definition is having multiple possible transitions for a certain event, for a certain state. Different communities also use different definitions, and some communities only use one of the definitions, and use a different name to refer to the other concept.
One cause of non-determinism is that multiple events are enabled, leading to multiple possible transitions. In other words, there are multiple possible traces through the state space. During the lesson on synchronizing events, we already encountered this form of non-determinism, as transitions for the
consume events could be performed in arbitrary order.
Another cause of non-determinism is the presence of multiple outgoing edges of a single location for the same event. This can lead to multiple possible transitions for a that event, for a single state. For instance, consider the following CIF specification:
automaton coin: event toss, land, pick_up; location hand: initial; edge toss goto air; location air: edge land goto ground; location ground: edge pick_up goto hand; end automaton outcome: location unknown: initial; edge coin.land goto heads; // First way to land. edge coin.land goto tails; // Second way to land. location heads: edge coin.pick_up goto unknown; location tails: edge coin.pick_up goto unknown; end
coin automaton represents a single coin. Initially, it is in the
hand of a person. That person can
toss the coin up into the
air, eventually causing it to fall and
land on the
ground. It can be picked up (event
pick_up), causing it to once again be in the
hand of a person.
outcome automaton registers the outcome of the coin toss. Initially, the outcome is
unknown. Whenever the coin is tossed, it lands (event
land from automaton
coin) on the ground with either the
tails side up. The
unknown location of the
outcome automaton has two edges for the same event. This leads to two possible transitions, one to the
heads location, and one to the
tails location. This is a non-deterministic choice, as the model does not specify which transition is chosen, or even which choice is more likely.
In both the
tails locations, the coin can be picked up again, making the outcome
unknown. The coin can be tossed again and again, repeating the behavior forever. The following figure shows the state space of this specification:
The states are labeled with the first letters of the current locations of the two automata.