XML CO631 Anonymous Questions and Answers Keyword Index

This page provides a keyword index to questions and answers. Clicking on a keyword will take you to a page containing all questions and answers for that keyword, grouped by year.

To submit a question, use the anonymous questions page. You may find the keyword index and/or top-level index useful for locating past questions and answers.

Keyword reference for non-determinism

Question 122 (2003):

What is actually meant by non-determinism ? Is it the fact the you cannot predict the values of variables and program position ? Due to program flow is un-predictable ?

Answer 122:

Almost.. What you describe is really an artifact of non-determinism. Non-determinism is the inability to predict what event will happen next, even when you do know what events are being offered. A classic example is the difference between `ALT' and `PRI ALT'. For example:

    ALT                          PRI ALT
      c ? x                        c ? x
        P ()                         P ()
      d ? y                        d ? y
        Q ()                         Q ()

In the first (`ALT') example, if we know that the channels `c' and `d' are ready for communication, we cannot tell which guard will be selected by the `ALT'. Hence, that choice is non-deterministic. In the other (`PRI ALT') example, if both channels are ready, we do know what will happen -- it will pick the `c' channel.

`PRI ALT' isn't always determinstic, however. For example:

    PRI ALT
      tim ? AFTER t
        Q ()
      c ? x
        P ()

This too is non-determinstic, since it relies on timing -- the outcome depends on when the code is run. Another way of thinking about a timeout is a parallel-process that waits for a bit then communicates. The above, for example, is equivalent to:

    CHAN BOOL d:
    PAR
      SEQ
        tim ? AFTER t
        c ! TRUE

      PRI ALT
        BOOL any:
        d ? any
          Q ()
        c ? x
          P ()

Unlike the earlier example, where we assumed we knew about the `ready' states of the `c' and `d' channels, we cannot call this example determinstic. The `ready-ness' of `c' depends on timing.

Keywords: non-determinism