Time

There is no time without space, without a space.

The naive, popular, pre-Einsteinian notion of time (Kantian, i.e. pre-conceptual) is this of a universal, linear (ordered) reference.

Einstein proposed a kind of extension, binding such a notion to a location (i.e. making it local), in order to keep it its nature, while better accounting for more complex phenomena.

Let's transpose this to computers (following Lamport on this way). What is the nature of a "place" for localizing time in programs?

The answer to this question is bound to our most common model of computers, based on so-called von Neumann architectures. This one has made its way up to the abstract model of the Turing Machine (as noticed by Peter Wegner). One more reason for its popularity is that it matches with a common, naive, model of mind limited to consciousness.
Let's call this conceptual "place" a "thread" (overloading on purpose this word).

The notion of time in one thread is fairly limited. One can even say that there is no proper time in one thread (my opening claim, as it appears). There is actually only a discrete monotonic sequentiality (in computers). Any meaning bound to a duration actually escapes the model by referring to a parallel world, i.e. to a second thread.

Note that this model makes no distinction between the notions of distribution and concurrency (and even of persistence!).
Note also that the notion of thread I made is abstract, and does not necessarily refer to any other stable location: a thread may "migrate" (whatever this means), yet carry its time with itself. This is a basis for powerful applications.

With this model in mind, and extending now to several threads, the notion of synchrony is restricted to the preservation of the order of events.

Now one first point I want to make is that synchrony is not preserved by RPC, contrarily to a naive assumption, possibly embodied in CORBA. The reason is that remote procedure calls are only synchronous with respect to the thread from which they are initiated, but are subject to collisions from other threads, which are, they, a-priori asynchronous.

This is important: our model of time is jeopardized by distribution, despite using RPC to match function calls. Distribution transparency is an illusion!

This is crucial to the paradigm of structured programming, on top of which static typing is built. It is acknowledgeably wider though, extending as well to computing models based on stacks (see e.g. Ullman on ML).

The generalization goes: times in different threads are by construction slightly inconsistent. The synchronization is however progressive: the past stabilizes a consistent state, as soon as the views of the various threads "commit". This happens eventually, but in an a-priori unpredictable way.

This is even more general, which shows the intimacy of time. One may have objected to my boldness in redefining the concepts of space or of location. Well, this is unescapable: the meaning of words are not stabilized yet either. They are constantly slightly inconsistent, synchronizing only in time.


Diverse ToC
Marc Girod
Last modified: Wed Apr 21 16:55:39 EETDST 1999