determinism

  • Thread starter Anthony Kerstens
  • Start date
A

Thread Starter

Anthony Kerstens

Knowing some of the past discussions, and having had some recent discussions of my own, I clipped the following from WWW.webster.com.
~~~~~~~~~~~~~~~~~~~
Main Entry: determinism
Function: noun
Date: 1846
1 a : a theory or doctrine that acts of the will, occurrences in nature, or social or psychological phenomena are causally determined by preceding events or natural laws b : a belief in predestination
2 : the quality or state of being determined
deterministic / adjective
~~~~~~~~~~~~~~~~~~~

I think meaning 1 is what was intended. So, when we call a network deterministic, we are saying what? Determinism has nothing to do with response time, but rather that every communication is
guaranteed to get a response?

For example, AB RIO is deterministic, but AB DH+ is not???

Also, anyone have a story on how this word became a technical term?


Anthony Kerstens P.Eng.
 
I think we use the term in the context of networks, not philosophy For example, from RFC1193:

A simple and popular form of performance requirement is that
involving a bound. A deterministic bound can be specified as

(var <= bound) = TRUE, or var <= bound,

where variable var is server-controlled, while bound is client-
specified. The bounds in these expressions are upper bounds; if <
is replaced by > , they become lower bounds.

Or,

From FOLDOC (free on line dictionary of computing)
http://foldoc.doc.ic.ac.uk/foldoc/index.html

deterministic
1. Describes a system whose time evolution can be predicted exactly.
Contrast probabilistic.

I have no idea where FOLDOC obtained its definition but, FWIW, its in agreement with
my understanding of the term. I think that is the meaning when used in the CompSci literature.

Bill Code
MPM Engineering Ltd.
4-6240 202nd St., Langley, B.C., Canada, V2Y-1N2
Phone: 1-604-534-6605 Fax: 1-604-534-6693
E-Mail: [email protected] WWW: http://WWW.MPM-ENG.COM/
 
G

Greg Goodman

My introduction to determinism came from comp sci,
in the context of state machines, specifically
finite deterministic automata.

"deterministic" used in this sense is a technical
term meaning absolute predictability. a finite
deterministic automaton has a finite number of
states and only one transition from any given
state for any given input event; therefore an
automaton in a known state and given any finite
sequence of events will have an absolutely
predictable final state.

applying "absolute predictability" to other
frames of reference:

- a hard realtime system is deterministic because
the time at which a specific piece of processing
will occur is absolutely predictable.

- a protocol is deterministic if the state of
the communication is absolutely predictable for
any sequence of messages.
 
D

Darold Woodward

Nothing is truly determinisitic in the real world using the strict form of the definition. Even if the system is hard-wired, there are variances in responses from subtle factors (cosmic rays, variations in the Earth's magnetic field, changes in the utility operating voltage that day). There is also the random chance that a component will fail.

For example, a protocol may be deterministic, but once you apply it with an actual communication channel, there is a possibility that bit errors on the channel will corrupt a message. So, even if you don't have random collisions to worry about, you will have random corrupt messages.

In the example of the control software, the program may be deterministic, but once you apply it in the real world there is still a chance that the computer it runs on will fail. Once you apply the "deterministic" solution in the real world, the truly stochastic behavior of the universe starts to creep in around the edges.

I prefer to take a more engineering (rather than pure science) approach to the whole discussion. Is the system sufficiently deterministic for your application (including any regulations or other
considerations that might apply)? If you truly understand your application, then you will only pay for determinism, speed, redundancy, etc. to the point that it is necessary.

Darold Woodward PE
SEL Inc.
[email protected]
 
R

Ralph Mackiewicz

> Main Entry: determinism
> Function: noun
> Date: 1846
> 1 a : a theory or doctrine that acts of the will, occurrences in
> nature, or social or psychological phenomena are causally determined
> by preceding events or natural laws b : a belief in predestination 2 :
> the quality or state of being determined deterministic / adjective
> ~~~~~~~~~~~~~~~~~~~
>
> I think meaning 1 is what was intended. So, when we call a network
> deterministic, we are saying what?

I think that determinism (as it relates to communications) is usually used as a qualitative measure of the ease at which the worst case
network access time can be predicted. For instance, a token passing network is considered deterministic because it is easy to calculate
the worst case network access time by considering, the number of nodes, the token hold time, token slot time and a few other parameters. Ethernet is not considered deterministic because the equations required to accurately predict worst case network access time are probabilistic and are much more difficult.

The dictionary definition of determinism describes both token passing and Ethernet. The only difference is that the natural laws of token
passing require simple algebra. The natural laws of Ethernet involve probabilities.

I still think determinism by itself is a red herring for most applications. You simply can't "guarantee" everything regardless of how the data link is structured. At some point the bit error rates of the medium you are using will enter into the equations. At that point ALL network systems are probabilistic. If the probability of a non-
deterministic data link (i.e. Ethernet) failing to resolve network access is EXTREMELY low (~ bit error rate), then the determinism of the data link is mostly irrelevant. Systems have to be designed to accommodate these non-deterministic events anyway.

> Determinism has nothing to do with response time, but rather that
> every communication is guaranteed to get a response?

Determinism has nothing to do with guaranteed response. Determinism relates to predictability. The issue of guaranteeing a response (or more accurately from a comm point of view: guaranteeing reception) is related to the reliability of the data transfer protocols and is
typically handled at the data link, transport, and/or application layers of the protocol stack used. This issue is more accurately described as "reliable message transfer" not determinism.

> Also, anyone have a story on how this word became a technical term?

The person who invented token passing had to come up with a feature that made his system sound better? ;-)

Regards,
Ralph Mackiewicz
SISCO, Inc.
 
E

E. Douglas Jensen

Your FSM usage of "deterministic" is correct but your statement "- a hard realtime system is deterministic because the time at which a specific piece of processing will occur is absolutely predictable." is incorrect. The real-time theory literature is unanimous on this: a "hard" real-time system is one which always
meets all its hard deadlines -- so what is deterministic is the property that all hard deadlines will always be met (given the premises hold, which may not be easily accomplished). The
property of the task completion times being deterministic is a very much stronger one, and is both unusual to seek and exceptionally difficult to achieve.

The real-time practitioner (user, vendor) community commonly uses "deterministic" in contradictory and vague ways. Sometimes they
incorrectly use it to mean "predictable" (of course, determinism is one end-point on the continuum of predictability); sometimes they
use it to mean there is a (least) upper bound. In the latter case, note that they refer to interrupt response/context switch times (that
is, starting a task), rather than deadlines (completing a task). They often pick some arbitrary time like 10 or 30 uS as the upper bound
for "hard" real-time in that sense. Obviously, starting a task quickly, even deterministically quickly, does not mean that it will complete
on time, except in the most trivial of systems. Indeed, starting a task quickly is not in general even a necessary much less a sufficient condition for completing it on time -- that's why the field of scheduling is supposed to be used.

This is discussed in more detail on my website; for example, http://www.real-time.org/presentations/dagstuhl/dagstuhl2.pdf

Doug

--
E. Douglas Jensen (at home)
[email protected], http://www.real-time.org
Home voice 508-653-5653, home fax 508-653-3342
Cell phone: voice 508-728-0809; text
http://www.bam.com/send2.htm
Pager 888-916-9802 and http://www.skytel.com/paging (PIN
8889169802)
Office voice 781-271-2514, office Fax 781-271-4686
 
V

Vladimir E. Zyubin

Hello List,

Tuesday, September 05, 2000, 10:00:59 PM, you wrote:

LMA> ------- Forwarded message follows -------
LMA> From: "Greg Goodman" <[email protected]>
[...]
LMA> "deterministic" used in this sense is a technical term meaning
LMA> absolute predictability. a finite deterministic automaton has a finite
LMA> number of states and only one transition from any given state for
LMA> any given input event; therefore an automaton in a known state and
LMA> given any finite sequence of events will have an absolutely
LMA> predictable final state.

Just a couple of remarks:
1. the description of finite deterministic automaton(FDA) can be applied to finite
automaton as well. But finite automaton has no "final state". I will not insist but it seems to me that definition of FDA has no "final state"...
2. I have a feeling that ANY program is deterministic according to this definition due to the nature of program.


LMA> applying "absolute predictability" to other frames of reference:
LMA> - a hard realtime system is deterministic because the time at
LMA> which a specific piece of processing will occur is absolutely
LMA> predictable.

there is no such a thing as "absolutely" in our "real" world... for the case of "realtime" - surely. If we open doc for any processor we can read about inrerrupts and _floating_ value of interrupt latency because of different lengths
of the processor commands (in clocks). And there is such commands as STI and CLI (SeT Interrupt flag and CLear Interrupt flag)... they are commonly use. ;-)

LMA> - a protocol is deterministic if the state of the communication is
LMA> absolutely predictable for any sequence of messages.

??? maybe "if there is maximal _threshold_ time for any message". Again, it seems to me "predictability" in the first definition is an
attribute of computers. It is in the nature of computer.

Thanks
--
Best regards,
Vladimir mailto:[email protected]
 
Top