Turing Award Goes To Distributed Computing Wrangler Leslie Lamport

alphadogg writes "Leslie Lamport, a Microsoft Research principal, has been named the winner of the 2013 ACM A.M. Turing Award, frequently called the 'Nobel Prize in Computing.' The computer scientist was recognized by the Association for Computing Machinery for 'imposing clear, well-defined coherence on the seemingly chaotic behavior of distributed computing systems, in which several autonomous computers communicate with each other by passing messages.' His algorithms, models and verification systems have enabled distributed computer systems to play the key roles they're used in throughout the data center, security and cloud computing landscapes."

Comments

And a million heads asploded.

[Anonymous Coward]

Microsoft guy wins turing award. Nerds snicker and claim bribery.

Nerds referred to LaTex, which he wrote. Heads asplode.

Re:And a million heads asploded.

[swillden]

Microsoft guy wins turing award. Nerds snicker and claim bribery.

Nerds referred to LaTex, which he wrote. Heads asplode.

He also wrote numerous papers that provide the foundations for much of the sophisticated distributed computing infrastructure we have today. For example, he created the Paxos algorithm, which describes an effective and fairly efficient approach for achieving a consensus view of shared state among a network of distributed processes. The concepts from Paxos -- and AFAIK the actual algorithm family -- is the technology underlying all of the massively-scalable distributed databases. It provides the mechanism for achieving eventual consistency while not stopping the world to synchronize.

In particular, huge chunks of fundamental system architecture at Google are based on Paxos. Not all NoSQL data stores take this approach, but all that don't have some fundamental limitations on scalability because without a distributed consensus protocol they have to introduce bottlenecks.

Of course, I think most of his really influential work was done before he went to Microsoft.

Re:Does that mean Microsoft Network is better ?

[phantomfive]

The work he did was back in the 80s. From my recollection, he applied relativity equations to distributed computing. He realized that you didn't need to try to synchronize perfectly all your clocks; that is, the same event might happen at different times from the perspective of different computers. If I remember correctly, he said when he showed his equations to his coworkers the equations they treated him like he was Moses, coming down from the mountain with tablets of stone; but to him it seemed like kind of an obvious solution.

Also he built a huge portion of LaTeX, and wrote the most important book on the topic.

Finally, people who go to Microsoft Research tend to disappear and never be heard of again. No one knows why.

Well-merited

[vikingpower]

Lamport wrote the paper "Time, Clocks and the Ordering of Events in Distributed Systems", one of the papers that stayed with me and influenced me most, during a career of slightly over 19 years now. For that paper alone he merits an award.

Plus

[MouseTheLuckyDog]

He wrote a good typesetting system, to bad he could not convince Microsoft to use it.

Re: Plus

[Anonymous Coward]

Woah, there. He wrote a good layer over a good typesetting system. Awesome as LaTeX is, please don't gloss over the separate awesemess of TeX.

Re:Plus

[martin-boundary]

Correction: He only wrote a set of macros on top of a typesetting system designed by Don Knuth.

Re:Plus

[gtall]

You mean Knuth wrote a good typesetting system and Lamport make it easier to use for many of the common things it was being used for, i.e., writing technical papers.

intrigued and annoyed

[raymorris]

Your comment got me reading his work. As a time geek who has been going around bitching about wildly out-of-sync clocks in clusters and other tightly coupled networks, his ideas interest me.

For anyone else who is mildly curious, here's a very short summary of his key idea, as I understand it from a brief reading:

In a cluster, you sometimes need to know which of two events should be considered "first". For example, if one process writes some state data and another process reads it, you need to know whether the read comes first and should get the old value, or if the write comes first, so the read gets the new value.

System clocks aren't perfectly synchronized. With multi-Ghz processors, events can happen so fast that the system timestamp isn't accurate or precise enough to identify which request was sent first.

To solve the problem of knowing which request is considered first, you can use a counter. Each request includes it's counter value - request #1, request #2, etc. If the receiving system keeps track of the highest counter and overwrites any "past" values with its own current "now" counter, it can put requests into a defined order.

Re:intrigued and annoyed

[NoImNotNineVolt]

I spent a semester studying his "Logical Clocks" paper in grad school.

It really is brilliant and surprisingly accessible. You don't need to be a rocket surgeon to understand it, but it conveys some truly awesome ideas.

supercilious bastress

[epine]

The man deserves it. He rocks. I've loved the precision of his engagement with fundamental assumptions since my first encounter with the Baker's algorithm.

My Writings is a good time killer. One of my favorite passages is this one:

Writing the proofs turned out to be much more difficult than I had expected. I worked very hard to make them as short and easy to understand as I could. So, I was rather annoyed when a referee said that the proofs seemed to have been written quickly and could be simplified with a little effort. In my replies to the reviews, I referred to that referee as a "supercilious bastard". Some time later, Nancy Lynch confessed to being that referee. She had by then written her own proofs of clock synchronization and realized how hard they were.

They did a fair amount of work together, judging by all the other places her name appears.

Re:Does that mean Microsoft Network is better ?

[TheRaven64]

Finally, people who go to Microsoft Research tend to disappear and never be heard of again. No one knows why.

That's only true if you never go to any computer science conferences: if you do, you'll find a lot of good papers written by MSR people. They do, however, have an appalling track record of turning them into products. This has improved a bit over the past few years, but until then MS and MSR were effectively run as two different companies and ideas from MSR were unlikely to be exploited in MS products.

The cynical explanation is that MSR exists to provide talented people with a well-funded sandbox where they will play and not create companies that compete with MS. The more likely explanation is that MSR has a budget of around $5bn annually, has separate premises, and does not provide any incentive to its employees to get their work into products.

Re:Congrats! Great time to leave MS.

[TheRaven64]

If you don't think Lamport has made a real difference already, then either you have no idea who he is, or you don't think computers are very important.