The Synchronous Blog

A blog about reactive programming languages.

About Determinism

with 2 comments

Current approaches for concurrent systems, such as multi-threading and message-passing are inherently non-deterministic, leading to unpredicted execution.

In multi-threaded systems, wherein memory is shared among threads, even if critical sections of code are protected, one is still subject to bugs due to non-determinism.

Suppose one writes the following code:

thread1 {
    ...     // do some processing
    lock {
        a = a + 2
    }
}
thread2 {
    ...     // do some processing
    lock {
        a = a * 2
    }
}

a = 1
start(thread1)
start(thread2)
wait(thread1, thread2)
print(a)

Depending on which thread assigns to `a` first, the value printed might be 6 or 4.
Moreover, each time the program is executed, the other result may be printed, as thread scheduling isn’t deterministic.

By using message-passing concurrency, non-determinism is also an issue.
In the code below, the value 6 or 4 might also be printed.

myChannel = new Channel()
cspA {
    ...     // do some processing
    send(myChannel, 4)
}
cspB {
    ...     // do some processing
    send(myChannel, 6)
}
cspC {
    ...     // do long processing
    a = receive(myChannel)
    a = receive(myChannel)
    print(a)
}

The characteristic that makes such systems non-deterministic is that each command in the language takes an unbounded time to execute.
As each thread or process run in asynchrony with each other, we (or the compiler) can’t predict where each thread will be at anytime, being impossible to detect simultaneous accesses to system resources.


Synchronous Concurrency, in the other hand, is deterministic.
Each command is conceptually instantaneous or takes exactly the time it says so.

For instance, in LuaGravity all commands but AWAIT are instantaneous:

_a = _a + 2           -- instantaneous
SPAWN(reactor)        -- instantaneous
AWAIT(reactor)        -- waits for `reactor` to finish
AWAIT(2)              -- waits 2 seconds

In the code below, we can predict simultaneous access to _a that would lead to non-deterministic behavior, and raise an error.

SPAWN(function()
    _a = _a + 2       -- line 2: simultaneous access to `_a` with line 8
end)
SPAWN(function()
    AWAIT(keyboard.press)
    _a = 10           -- deterministic access to `_a`
end)
_a = _a * 2           -- line 8: simultaneous access to `_a` with line 2

The execution of this program yields an error when the second simultaneous access to _a happens.
The prediction of simultaneous access could be even static (if LuGravity had a compiling phase), raising a compile-time error.

Advertisements

Written by francisco

January 6, 2009 at 5:04 pm

2 Responses

Subscribe to comments with RSS.

  1. Please note that although you’ve tagged this post with “CSP”, and have used “csp” as a prefix in the process names of your message-passing example, what you’ve shown isn’t representative of CSP. It looks more like the Actors model, where processes (actors) send messages asynchronously to other named processes. In CSP-style programming (as represented by occam, Alef, Limbo, etc.), processes send messages via channels that require rendezvous for message delivery. Those channels are typically only owned by a single channel at each end. Rendezvous (synchronization) on channel send/receive enforces an ordering on operations that enables deterministic designs to be produced. Thus your example should look like

    # cspC {
    # … // do long processing
    # a = ChanAtoC.receive()
    # a = ChanBtoC.receive()
    # print(a)
    # }

    which will have a deterministic result (the value of a will be 6). That’s not to say that nondeterminism can’t crop up in CSP-style message-passing systems. It just doesnt arise in the way you’re trying to claim it does.

    You could probably create a similar design in an asynchronous messaging system like Erlang by blocking on the reception of messages from certain sources. Again, that won’t give you the same kind of deterministic guarantees that a synchronous-reactive system gives you, but it does make it possible to create deterministic designs if you want to.

    Allan

    June 2, 2009 at 10:40 pm

    • Hi Allan,
      Thanks for your feedback.

      I’m not quite familiar with the CSP jargon, and based this post on Hoare’s original paper, which does not mention channels — altough I now checked a further work that does.

      Your example uses different channels for communicating with C.
      By using a shared channel between the processes, your example would be equivalent to mine in respect to non-determinism:

      cspC {
          … // do long processing
          a = sharedChannel.receive()
          a = sharedChannel.receive()
          print(a)
      }
      

      I agree that one can write deterministic programs with CSP or any other asynchronous model (even with threads and locks).
      However, these models do not guarantee determinism in the same way synchronous languages do.

      — Francisco

      luagravity

      June 3, 2009 at 1:44 am


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: