Browse Prior Art Database

Original Publication Date: 1977-Jan-31
Included in the Prior Art Database: 2007-Mar-30
Document File: 66 page(s) / 3M

Publishing Venue

Software Patent Institute

Related People

Friedman, Daniel P.: AUTHOR [+3]



This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 5% of the total text.

Page 1 of 66


Daniel P. Friedman
David S. Wise

Co~puter Science Department
Indiana University

Bloomington, Indiana 47401

*Research reported herein was supported (in part) by the National Science Foundation under grants numbered DCR~~-06678 and MCS75-08145.

[This page contains 1 picture or other non-text object]

Page 2 of 66

[This page contains 1 picture or other non-text object]

Page 3 of 66


    If we trace the design of modern computers back t o its sources, the unifying theme of synchronous deterministic operation appears. Turing machines, for example, are formalized so that the computation -- the behavior -- of the machine is preordained when it is started, and all of the (admittedly simple) operations are performed i n lock-step. Even i n the earliest operational computers the themeof determinism--'the unique path of the computation--and of synchronous behavior may be observed. This latter property, by itself, was no t r i v i a l requirement for designers but various parts of the machine had t o be co-ordinated lest the first prloperty be lost.

    A s computer applications matured and moved from the straight- forward computational applications, i n which both algorithm and data could be preordained before the machine was started, into real-time applications (interactive computing for instance),
where neither may be preordained, one of these assumptions had t o be abandoned. The sequence of events i n the real world occurs continuously, even when measured by the nano-second clocks which drive modern computers. In order t o respond t o events occurring in realtime, one of these fundamental precepts had t o be abandoned.

[This page contains 1 picture or other non-text object]

Page 4 of 66

    What fell was the "perceived1' determinism. It is not hard
to see that a discrete computer design, with an internal clock
dividing time into discrete intervals for the operation of the
entire machine, would not adapt well to events occurring at
distinct times along a continuum. As far as the discrete machine
was concerned, any non-simultaneous events which occurred in the
same clock interval would appear to have occurred simultaneously.
Of course, the "ticks" of a computerts internal clock are not
at all synchronized with the occurrence of continuous events, so
the occurrence of two very close events in the -- same

                                                               -- versus adjacent
time intervals is completely arbitrary. Thus, external everts a m
viewed as happening at unpredictable intervals; we say that this
unforeseeable timing of events violates the "perceived" determinfsm
of early machines, where events in the "next" clock tick depend
only on the state of the machine in the previous one.

    This perceived nondeterminism differs from "nondeterminism"
as used commonly in the literature. We do not mean that the
computation reaches a point where it chooses a successful...