Concurrency always is non-deterministic?

Concurrency always is non-deterministic?

[Long Hoàng Đình]

The author of this post said so. If Ada were non-deterministic at concurrency, I guess it couldn't be real-time, right?

http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/

Please let me know your opinions about that post.

Re: Concurrency always is non-deterministic?

[Dmitry A. Kazakov]

On Mon, 13 Feb 2012 09:41:31 -0800 (PST), Long Hoïżœng ïżœïżœnh wrote:

> The author of this post said so. If Ada were non-deterministic at concurrency, I guess it couldn't be real-time, right?
> 
> http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/
> 
> Please let me know your opinions about that post.

Concurrent and parallel were used as synonyms in the literature I read. The
author seems to think that concurrent = time sharing. It is not.

In any case the issue is unrelated to determinism and real-time.

Determinism is when the state of a program is determinable from its
previous state. A program that reads from the keyboard and then uses the
value in some if statement, is non-deterministic. A program that uses a
hardware random generator, a real-time clock is non-deterministic.

Note also that unpredictable /= non-deterministic. A program can be very
complex to predict (especially when you are looking for a bug to reproduce
(:-)) but still deterministic.

Real-time is a property of being related to the external real time source.
No more, no less.

In a narrower sense, RT is when the quality of a value (e.g. of a response)
depends on the real time. For example, when that value degrades as the time
passes. Hard real-time is when the value reaches 0 in bounded time. A
program is said to be real time, when it processes certain values before
their quality degrades below specified (usually by the application domain)
level.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Concurrency always is non-deterministic?

[Georg Bauhaus]

On 13.02.12 18:41, Long Hoàng Đình wrote:
> The author of this post said so. If Ada were non-deterministic at concurrency, I guess it couldn't be real-time, right?
> 
> http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/
> 
> Please let me know your opinions about that post.

As an exercise in journalism, it's great. It excels at lifting
definitions into the realm of vagueness, phrasing as if it didn't.
Not saying that this is the author's intention, though.

Once vague enough, the article has the effect of spurring a discussion
that cannot bear fruit until readers have spent time consulting
precise sources---from doing which the article keeps them away,
quite effectively.

Enough said ;-)

Re: Concurrency always is non-deterministic?

[Niklas Holsti]

On 12-02-13 19:41 , Long Hoàng Đình wrote:
> The author of this post said so. If Ada were non-deterministic at concurrency, I guess it couldn't be real-time, right?
>
> http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/
>
> Please let me know your opinions about that post.

It is a nice and clear position statement, with its own definitions of 
the terms.

The author's main point is that when a program is multi-threaded (or 
multi-tasked, in Ada terms), with tasks that can have side effects on 
shared data, then the results computed can depend on the order in which 
the tasks are scheduled and executed (on one or several cores). This is 
what the author calls "non-deterministic" concurrent execution. As the 
author says, to write such a program, the programmer must usually make 
careful use of task synchronization and control access to shared data. 
Ada has nice high-level features for that.

On the other hand, if all computations use only private data (and do not 
include non-deterministic data such as inputs or clock readings in their 
computations) then the end result does not depend on the order or timing 
of the computations (whether divided into tasks or not), even if they 
are executed in parallel on many cores. This is what the author calls 
deterministic parallel execution. In other words, the programmer does 
not have to consider task scheduling or synchronization; that is handled 
by the compiler and run-time system.

However, for most real-time programs "non-determinism" in the author's 
sense is desirable, because the results of the computation are 
*required* to depend on timing, inputs, and clock-readings. Moreover, in 
real-time programs, tasks must be executed at certain times, as 
specified in the program -- whether or not the tasks share data.

The right conclusion is therefore the opposite: using the author's 
terms, "deterministic parallelism" is unusable for real-time systems, 
because real-time systems must be "non-deterministic".

Note that the author's term "non-deterministic" does not imply 
"unreliable" or "unpredictable".

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .

Re: Concurrency always is non-deterministic?

[Simon Wright]

"Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:

> In a narrower sense, RT is when the quality of a value (e.g. of a
> response) depends on the real time. For example, when that value
> degrades as the time passes. Hard real-time is when the value reaches
> 0 in bounded time. A program is said to be real time, when it
> processes certain values before their quality degrades below specified
> (usually by the application domain) level.

A somewhat different statement from the one I'm used to, which is pretty
much as in http://en.wikipedia.org/wiki/Real-time_computing

Re: Concurrency always is non-deterministic?

[Bill Findlay]

On 13/02/2012 19:38, in article m28vk634mr.fsf@pushface.org, "Simon Wright"
<simon@pushface.org> wrote:

> "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de> writes:
> 
>> In a narrower sense, RT is when the quality of a value (e.g. of a
>> response) depends on the real time. For example, when that value
>> degrades as the time passes. Hard real-time is when the value reaches
>> 0 in bounded time. A program is said to be real time, when it
>> processes certain values before their quality degrades below specified
>> (usually by the application domain) level.
> 
> A somewhat different statement from the one I'm used to, which is pretty
> much as in http://en.wikipedia.org/wiki/Real-time_computing

"The needs of real-time software requires the use of one or more synchronous
programming languages" ??

Methinks someone is grinding a proprietary axe.

-- 
Bill Findlay
with blueyonder.co.uk;
use  surname & forename;

Re: Concurrency always is non-deterministic?

[Brian Drummond]

On Mon, 13 Feb 2012 09:41:31 -0800, Long Hoàng Đình wrote:

> The author of this post said so. If Ada were non-deterministic at
> concurrency, I guess it couldn't be real-time, right?
> 
> http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/
> 
> Please let me know your opinions about that post.

As a counterexample, the VHDL language's model of concurrency is 
deterministic. 

(In the terms of the article, it is a side-effecty language, but there is 
a two-stage execution model where the side effects happen as "postponed 
assignments" which are scheduled after all the concurrent processes have 
suspended. It follows that the processes have to have well defined 
suspend intervals; these are guaranteed in hardware by static timing 
analysis. After the assignments, the next scheduling event restarts some 
or all processes)

So I can't entirely agree with the article.

- Brian

Re: Concurrency always is non-deterministic?

[Simon Wright]

Bill Findlay <yaldnif.w@blueyonder.co.uk> writes:

> On 13/02/2012 19:38, in article m28vk634mr.fsf@pushface.org, "Simon Wright"
> <simon@pushface.org> wrote:

>> A somewhat different statement from the one I'm used to, which is pretty
>> much as in http://en.wikipedia.org/wiki/Real-time_computing
>
> "The needs of real-time software requires the use of one or more synchronous
> programming languages" ??
>
> Methinks someone is grinding a proprietary axe.

Hmm. I've added a query to the Disputed section of the Talk page.

Re: Concurrency always is non-deterministic?

[Phil Clayton]

On Feb 13, 5:41 pm, Long Hoàng Đình <long....@gmail.com> wrote:
> The author of this post said so.

The author's point is that non-determinism introduced by concurrency
requires synchronization to make the overall program deterministic but
this synchronization is difficult to get right (so why not use the
Glasgow Haskell Compiler that takes care of all that for you...)


> If Ada were non-deterministic at concurrency, I guess it couldn't be real-time, right?

If you wrote a concurrent program but left out the synchronization
required to ensure deterministic behaviour, in general, the result
would be so unpredictable that it doesn't make sense to ask whether it
is still real-time.

Synchronization support exists for many languages, e.g. via the
pthreads library.  In Ada, tasking (and its synchronization support)
is actually part of the language which has numerous advantages.


> http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/
>
> Please let me know your opinions about that post.

I am a big proponent of functional programming and it does have
advantages for parallelism.  I find the discussion on parallelism vs
concurrency nonsensical.  I'm sure GHC will have some great new
parallelism features though.  The post should be seen in a certain
software context: functional programming is unsuitable for systems
that are any of: real-time, embedded or critical (I will happily
expand on that claim) so any claims made by the author only extend so
far.

Phil

Re: Concurrency always is non-deterministic?

[Phil Clayton]

On Feb 13, 6:04 pm, "Dmitry A. Kazakov" <mail...@dmitry-kazakov.de>
wrote:
> The author seems to think that concurrent = time sharing.

That's how I read it too.


> It is not.

I agree.  I take the view that concurrency can be either time-slicing
or running in parallel (using multiple processing cores).  Either way,
it's still non-deterministic so the author's point about needing
synchronization still stands.

Phil

Re: Concurrency always is non-deterministic?

[Erich]

On Feb 14, 2:18 am, Phil Clayton <phil.clay...@lineone.net> wrote:

> functional programming is unsuitable for systems
> that are any of: real-time, embedded or critical

The first two points, yes, but what about the third. Haven't
functional programming languages like Haskell been used for critical
(high-integrity) applications as a substitute for Ada/Spark, because
they make formal verification very easy?

I'm not claiming it, just believe I've read about it and ask as a
layman out of curiosity.

Re: Concurrency always is non-deterministic?

[John B. Matthews]

In article <m24nuu2p4k.fsf@pushface.org>,
 Simon Wright <simon@pushface.org> wrote:

> Bill Findlay <yaldnif.w@blueyonder.co.uk> writes:
> 
> > On 13/02/2012 19:38, in article m28vk634mr.fsf@pushface.org, "Simon Wright"
> > <simon@pushface.org> wrote:
> 
> >> A somewhat different statement from the one I'm used to, which is 
> >> pretty much as in http://en.wikipedia.org/wiki/Real-time_computing
> >
> > "The needs of real-time software requires the use of one or more 
> > synchronous programming languages" ??
> >
> > Methinks someone is grinding a proprietary axe.
> 
> Hmm. I've added a query to the Disputed section of the Talk page.

I've submitted clarified wording.

-- 
John B. Matthews
trashgod at gmail dot com
<http://sites.google.com/site/drjohnbmatthews>

Re: Concurrency always is non-deterministic?

[Phil Clayton]

On Feb 14, 10:05 am, Erich <j...@peppermind.com> wrote:
> On Feb 14, 2:18 am, Phil Clayton <phil.clay...@lineone.net> wrote:
>
> > functional programming is unsuitable for systems
> > that are any of: real-time, embedded or critical
>
> The first two points, yes, but what about the third. Haven't
> functional programming languages like Haskell been used for critical
> (high-integrity) applications as a substitute for Ada/Spark, because
> they make formal verification very easy?
>
> I'm not claiming it, just believe I've read about it and ask as a
> layman out of curiosity.

Yes, this is worth clarifying.  I am talking about using the output of
a functional language compiler directly in a critical system.  The
main issue (for me) is that the included run-time system is just too
complicated to be trusted.  I'm not sure that it would even be
possible to perform the various verification activities required of a
typical critical system.

Where I've heard about FP used for critical application software, it
is generating code, e.g. C [1].  The risks here are totally different:
we are concerned with the likelihood that an error in the functional
language compiler results in a legal program that is incorrect in a
way that is sufficiently subtle that it is not detected by any
verification activities.  This risk is very small and can be reduced
further by re-running with a different compiler.  This is dwarfed by
the risk due to an error in implementation of the code generation
algorithms.  Functional programming really will help avoid this sort
of algorithmic error: it is especially suitable for data structure
transformation algorithms.  So I believe FP is actually a good choice
for code generators (and verification tools) used in the development
of critical systems.

As for formal verification being very easy.. unless your language is
incredibly simple, it's never easy!  If you know what you are doing,
what slows your formal verification down is usually bad tool support,
rather than the language.  It is usually easier to reason about the
algorithmic behaviour of (purely) functional programs than imperative
programs but it isn't just the programming paradigm that makes a
difference.  For example, justifying algorithmic optimizations often
requires knowledge about ranges of variables, for which Ada types are
incredibly useful because tools can assume values are in their type
range.  Without this, adding/managing such global constraints must be
done manually, which is very laborious.

Phil


[1] Also, I think the languages may be constrained in some way.  (If
your language doesn't have functions as ordinary values, is it still a
functional programming language?)

Re: Concurrency always is non-deterministic?

[Jeffrey Carter]

On 02/14/2012 03:05 AM, Erich wrote:
> On Feb 14, 2:18 am, Phil Clayton<phil.clay...@lineone.net>  wrote:
>
>> functional programming is unsuitable for systems
>> that are any of: real-time, embedded or critical
>
> The first two points, yes, but what about the third. Haven't
> functional programming languages like Haskell been used for critical
> (high-integrity) applications as a substitute for Ada/Spark, because
> they make formal verification very easy?
>
> I'm not claiming it, just believe I've read about it and ask as a
> layman out of curiosity.

Erlang was created for implementing soft real-time systems, specifically 
telephony systems.

-- 
Jeff Carter
"If you think you got a nasty taunting this time,
you ain't heard nothing yet!"
Monty Python and the Holy Grail
23

--- Posted via news://freenews.netfront.net/ - Complaints to news@netfront.net ---