Tuesday, March 17, 2009

Relativity of simultaneity

A problem with staying in a profession for long years is that there's less and less things that can truly excite or surprise you as the time passes. That's why I was particularly delighted to experience a moment of sudden enlightenment while listening to Rich Hickey talk about "Persistent Data Structures and Managed References" last thursday at QCon in London. The title of the talk might not sound exciting, but I have to tell you, if this were the only talk I attended, it alone would have been worth attending. I don't say this often. Slides are here, although you're missing out Rich's incredibly good verbal presenting style if you just read them, obviously.

Rich's view (with which I have to agree; in the time I knew Rich, I have yet to hear the first thing from him I'd disagree with, whether it be concurrency, memory models, or ideas for what to do in San Francisco if you only have a single day to explore it); so, Rich's view is that the idea of variables in traditional programming languages is broken, because they are based on a single thread of control at a time. This used to be true in single-threaded programs, and even to a degree for multi-threaded programs running on single-CPU systems.

He argues that we need well defined time models for state changes in our concurrent computational systems. A lack of a time model fails to capture the situation where two observers (threads, CPUs) can observe two events (changes of state) in different order.

Then it suddenly hit me! I learned this stuff in school! Relative timelines, observers... Rich is talking about relativity of simultaneity!

(Which is one of the simpler conseqeunces of Einstein's special theory of relativity.)

Wait a moment. Finding such a surprising parallel analogy between physical world surrounding us and our digital computational systems seems at first unlikely, but thinking more of it, it makes perfect sense. For event timelines to appear differently to different observers, we only need two prerequisites: truly parallel processing, and finite speed of change propagation. Both are true for the real world (quite massively parallel, and the changes propagate at at most the speed of light), and for digital computational systems (parallel already at two CPU cores, with changes occurring in CPU registers and needing time to propagate downstream the hardware memory model to be observable by other CPUs).

One of the wonderful things about Rich is that he's able to express these notions very clearly. It is all really obvious when you think about it, and I couldn't even say I wasn't aware of it for at least three years now, it's just that before hearing this talk, I always had a very slight hope that someday, someone (infinitely wiser than me) will somehow be able to, you know, solve this. Eliminate this problem. The thing I realize now is that it's inherent. You can no sooner eliminate relativity of simultaneity and the rest of consequences it brings to the table from our computational systems than you could cancel its effects in the physical world.

Rich does the only sane thing to do with a problem you can't eliminate - he embraces it. His programming language, Clojure, is an attempt at being the easiest way to write correct concurrent programs. Emphasis on all of "easy to write", "concurrent", and "correct". I learned about Clojure sometime last year when it came up at the jvm-languages mailing list. I read up the documentation on the website, and came away thoroughly impressed. Then I met Rich and saw a 30-minute Clojure presentation last year at the JVM language summit, saw the 60-minute version of the same talk now at QCon, and I'm still impressed. Clojure embraces the problem of concurrent state modifications by encapsulating the state into "references" - the only mutable data types in Clojure, which all point to immutable values. The references can change in time though to point to new values, and the big idea here is that each reference has defined concurrency semantics for how and when change occurs.

Now, there's likely a huge number of temporal semantics of how can some entity's state change. Clojure identifies several usual semantic categories though, and provides them for ease of use. We have synchronous coordinated (Clojure has a STM for that), synchronous uncoordinated, asynchronous uncoordinated, as well as isolated (thread local). I think you can build whatever you need using those.

Anyhow, during Rich's talk I had a moment of enlightenment. Not because I heard something entirely new, but because the pieces of the jigsaw puzzle finally fell into place and revealed a picture. The picture does away with a false hope I had, which is good as it is a clear and definite answer to a question, and having accepted it it is at least clear to me what's the direction forward. During the rest of the day, I was telling pretty much everyone I met and their dog about how I was shown the inherent manifestation of relativity in finite-speed concurrent systems. (Joe Armstrong was just smirking at it, probably thinking "you wet-behind-the-ears kids, this should've been obvious to you for decades", and then we proceeded making fun of all n-phase commit protocols, for any finite value of n).

On multicore systems, there's no longer absolute time. Every core runs on its own relative time and there's no definite sequencing of events. It's time we build this assumption into our code, and not use tools and methodologies that are ignorant of this fact. And as Rich would point it out, writing your code in Clojure is a good way towards the goal.

6 comments:

Thoughts said...

You might be interested in Time and conscious experience. This is based on Alex Green's original insight

Martin Dale Lyness said...

Just curious what drew you into Closure versus the other DSLs designed to solve the same problem of relativity.

Anonymous said...

@martin dale lyness
clojure is a lisp dialect, not really a dsl.

Attila Szegedi said...

@Thoughts: thank you - these look interesting, will try to read them as soon as I have time

@Martin: what other DSLs do you have in mind? Clojure is not a DSL, it's a general purpose language, and I'm "drawn" to it mostly by virtue of listening to Rich Hickey's excellent presentations of it at various conferences. I also got to know Rich personally, and I find him to be a person of tremendous intellectual capabilities who seems to be finding the right answers to hard questions. I derive my trust in Clojure from my trust in Rich.

Martin Dale Lyness said...

Yeah i apologize for using the term DSL so loosely, I was just trying to group the languages like Closure, Erlang, and I think Scala (guess I was trying to consider concurrency a domain :/). I'm unfamiliar with any of these languages but after reading through the Closure pdf presentation, the concepts used, seem invaluable when thinking about concurrent programming.

John Ryskamp said...

There's just one problem. New work in the history of set theory has allowed us to see where Einstein, a constructivist mathematician (he called it "practical geometry" and wrote a famous essay on it called "Geometry and Experience"), actually USED practical geometry in formulating the relativity of simultaneity.

What is the problem with this? Well, if you know anything about Einstein's mathematical orientation, you know that he did not believe arguments could have logical content, that all arguments ended in paradox unless some arbitrary insertion was made in them.

Until now, physicists just thought that was all fluff, because it was unclear where Einstein actually made this insertion in the relativity of simultaneity. The many critiques of the relativity of simultaneity have been very off point, but it is clear now that they were pointing toward the precise logical problem, without ever being able to pinpoint it.

But now we know. If you look at the train experiment, which is the clearer of the two relativity of simultaneity experiments (the other is the clock experiment--but it is simply the train experiment in another form), you will see that Einstein says point M and M' "naturally" coincide. And this "naturally" is the problem.

It is nowhere defined, and yet it cannot be removed from the argument--the classic problem with an argument with a logical flaw. You will immediately see that the relativity of simultaneity cannot be said to have logical content if this "natural" coincidence is retained, nor can it be said to have logical content if this "natural" coincidence is removed. This ends the relativity of simultaneity as an argument with logical content, which, again, many physicists felt it did possess since they could see nothing wrong with it.

However, it fulfills the constructivist program very well--it does everything Einstein says a constructivist argument should do.

So there it is, you cannot use the relativity of simultaneity if you demand an argument which has logical content. The relativity of simultanetiy has no logical content.

And that's not an objection to Einstein's program, because, again, Einstein did not believe in logical content. It's just that most people are not constructivist mathematicians--they demand logical content in an argument, or they refuse to deal further with the argument.

Since physicists couldn't see where Einstein had used "practical geometry," they felt the relativity of simultaneity had logical content, because they had examined it closely and couldn't find any problem with it.

You'll see a more extended discussion of the train experiment at the end of the paper linked below.

The history of all this is, first, the pervasive influence of constructivist mathematics since Aristostle, who was worried about Zeno's "paradox" (which is not a paradox).

Constructivism got a huge boost from such propagandists as Russell and Poincare, when, around the turn of the 20th century, Cantorian set theory seemed to generate new paradoxes. And so Poincare made a strong pitch for constructivism in Science and Hypothesis, which, if you know your Einstein, you know had a tremendous influence on Einstein.

If you're interested in how the "natural" coincidence flaw in the relativity of simultaneity was identified, do the background reading, above all A. Garciadiego's myth-debunking Bertrand Russell and the Origins of the Set-Theoretic 'Paradoxes.' You should also read Grattan-Guinness, The Search for Mathematical Roots, for his scathing indictment of Poincare's understanding of set theory issues.

Poincare was really a journalist, not a mathematician. How Einstein could have taken him seriously, how he could not have taken the time to investigate whether Poincare understood what he was talking about, is beyond me.

In any event, you can't use the relativity of simultaneity anymore, because it's over as a logical argument. The main thing is that now we can't logically get to the Standard Model.

Probably the most important implication is for the Pythagorean theorem. That does not obtain under general relativity, as is well known, but if we can't get to general relativity because of "natural" coincidence, then the PT is at issue again. My own feeling is that there is a constructivist intervention in the Pythagorean theorem. But where? Various writers, such as Schopenhauer and Hegal, suggested there were logical problems with it, but they never even approached a precise critique.

Search ResultsSSRN-Paradox, Natural Mathematics, Relativity and Twentieth ... Ryskamp, John Henry,Paradox, Natural Mathematics, Relativity and Twentieth-Century Ideas(June 17, 2008). Available at SSRN: http://ssrn.com/abstract=897085 ...
papers.ssrn.com/sol3/papers.cfm?abstract_id=897085 - Similar pages -
by J Ryskamp