Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Turing Award Goes To Distributed Computing Wrangler Leslie Lamport

Soulskill posted about 6 months ago | from the and-the-alan-goes-to dept.

News 40

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."

cancel ×

40 comments

Sorry! There are no comments related to the filter you selected.

Does that mean Microsoft Network is better ? (0)

Anonymous Coward | about 6 months ago | (#46522287)

Since Mr. Lamport works for Microsoft, and his field is in distributed computing system, does that means Microsoft Network works in a more "clear, well-defined coherence" manner than those running Linux ?

Just wonder.

Re:Does that mean Microsoft Network is better ? (4, Interesting)

phantomfive (622387) | about 6 months ago | (#46522339)

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.

intrigued and annoyed (4, Informative)

raymorris (2726007) | about 6 months ago | (#46522465)

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 (2)

NoImNotNineVolt (832851) | about 6 months ago | (#46523297)

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.

Re:intrigued and annoyed (0)

Anonymous Coward | about 6 months ago | (#46526563)

A whole semester for this one concept? Daheq?

Re:intrigued and annoyed (1)

NoImNotNineVolt (832851) | about 6 months ago | (#46526671)

Indeed, a whole semester, and with only three students in the class. It was one of the most serious classes I've ever taken. The paper itself was a reasonable size, about six or eight pages if I remember correctly. However, formally proving it all, well, it took countless hours. The goal of the class was to teach us how to properly read literature in the field in preparation for having us make our own contributions. Of course, I dropped out before I was anywhere near publishing.

Also, it's spelled dafuq.

Re:Does that mean Microsoft Network is better ? (0)

Anonymous Coward | about 6 months ago | (#46522597)

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

Microsoft has apparently lots of problems in their products needing a quick solving by the best in the scientific community. ;)

Re:Does that mean Microsoft Network is better ? (4, Interesting)

TheRaven64 (641858) | about 6 months ago | (#46522671)

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:Does that mean Microsoft Network is better ? (1)

gtall (79522) | about 6 months ago | (#46523293)

More likely, the computer scientists cannot get their ideas past the marketdroids that run MS.

Re:Does that mean Microsoft Network is better ? (1)

Barlo_Mung_42 (411228) | about 6 months ago | (#46524865)

And I think that's the right approach. Judging the success of research based on how many product ideas they turn out will result in misguided research. It is a failure of the MPs on the product teams for ignoring what MSR is doing. That does seem to be changing but it used to be very bad.

Re:Does that mean Microsoft Network is better ? (1)

Millennium (2451) | about 6 months ago | (#46524137)

This depends on a number of factors. Did Microsoft use the designs he came up with when he did this work? Was Linux not allowed to use these designs? Did he (or someone else) find a way to improve upon that work, and were these improvements incorporated into Windows (or Linux)?

Even a rockstar can be hobbled by bad management, and we all know that the quality of Microsoft's management has, at times, been questionable. It's entirely possible that this could have happened here. Or maybe it didn't. We can't be sure from the Microsoft side.

Re:Does that mean Microsoft Network is better ? (0)

Anonymous Coward | about 6 months ago | (#46527463)

This depends on a number of factors. Did Microsoft use the designs he came up with when he did this work? Was Linux not allowed to use these designs? Did he (or someone else) find a way to improve upon that work, and were these improvements incorporated into Windows (or Linux)?

Uh, the work in question was done in the late 70s and 80s, when Lamport was at SRI and DEC. He joined Microsoft in 2001.

Passed the Turing Test? (0)

Anonymous Coward | about 6 months ago | (#46522317)

I was half asleep when I read this, and thought that the article was claiming that a Microsoft employee passed the Turing test! Apparently the award isn't given out to everyone who passes the Turing test, only some.

And a million heads asploded. (4, Insightful)

Anonymous Coward | about 6 months ago | (#46522327)

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. (3, Interesting)

swillden (191260) | about 6 months ago | (#46524093)

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.

Well-merited (4, Interesting)

vikingpower (768921) | about 6 months ago | (#46522349)

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.

Re: Well-merited (0)

Anonymous Coward | about 6 months ago | (#46524791)

He also wrote "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess
Programs.", which defines the concept of sequential consistency and is the basis for modern work on language and processor memory models.

Very we'll deserved indeed.

Plus (2, Insightful)

MouseTheLuckyDog (2752443) | about 6 months ago | (#46522407)

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

Re: Plus (2, Informative)

Anonymous Coward | about 6 months ago | (#46522899)

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.

Wrong problem identification (1)

mha (1305) | about 6 months ago | (#46523087)

I'm not sure why you care if *Microsoft* uses (La)Tex. This is a choice for the *customers*, and given that (La)Tex has always been easily and freely available for everyone I'm not sure what mindset you have to blame Microsoft. Because you don't dare insult *everyone* at once (the overwhelming customer majority), because then everyone reading your comment would have seen the lack of thinking that went into it? So you instead gained some "Insightful" votes from equally zealous MS haters, congrats, well done (from your POV).

Re:Plus (2)

gtall (79522) | about 6 months ago | (#46523305)

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.

Heh heh (0, Troll)

Anonymous Coward | about 6 months ago | (#46522413)

Turing award goes to a man named Leslie!

(cue Beavis and Butthead laughing)

Re:Heh heh (1)

Millennium (2451) | about 6 months ago | (#46523343)

Leslie Nielsen would like to have a word with you.

Re:Heh heh (1)

Anonymous Coward | about 6 months ago | (#46523651)

Leslie Nielsen would like to have a word with you.

Surely you can't be serious!

Re:Heh heh (0)

Anonymous Coward | about 6 months ago | (#46523689)

Surely you can't be serious!

Don't call me Shirley!

Congrats! Great time to leave MS. (-1)

Anonymous Coward | about 6 months ago | (#46522457)

Are you ready to go out and make a real difference?

Re:Congrats! Great time to leave MS. (2)

TheRaven64 (641858) | about 6 months ago | (#46522679)

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.

Bout time (-1)

Anonymous Coward | about 6 months ago | (#46522579)

a chick did something noteworthy in CS, but I have to wonder, does she have facial hair?

Re:Bout time (1)

misof (617420) | about 6 months ago | (#46522763)

Sorry to disappoint you, but he's a guy [wikipedia.org] .

hoa vu (0)

Anonymous Coward | about 6 months ago | (#46522599)

great article, visit his friend learned a lot to offer, thank you

lioa [lioa.net.vn]
on ap [lioa.net.vn]
sua lioa [lioa.net.vn]
sua on ap [standavietnam.vn]

supercilious bastress (5, Interesting)

epine (68316) | about 6 months ago | (#46522649)

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 [microsoft.com] 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:supercilious bastress (1)

godrik (1287354) | about 6 months ago | (#46524113)

The only thing that surprised me is that he did not already have won that award.

Re:supercilious bastress (1)

sadboyzz (1190877) | about 6 months ago | (#46524115)

That's a good one, probably explains why Lamport only just got the award now and not much sooner :)

Lamport's Law (1)

Jahta (1141213) | about 6 months ago | (#46522907)

"A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable."

Microsoft > Apple (-1)

Anonymous Coward | about 6 months ago | (#46523135)

This is why Microsoft > Apple.

FIRST POST (1)

hackingbear (988354) | about 6 months ago | (#46526371)

my request counter is 0!

Welcome to Lamport's Bakery! (1)

Mr Z (6791) | about 6 months ago | (#46531583)

My first encounter with Leslie's work was Lamport's Bakery. It's a serialization primitive with some surprising properties. For example, it doesn't require properly arbitrated access to memory as the initial value read from memory on entrance to the "bakery" actually doesn't matter!

Dr. Lamport was actually kind enough to reply to an email of mine regarding said primitive. I was optimizing a version of it for a multiprocessor device we were making where I work, and I had come upon what I thought was a clever optimization. (I actually vectorized a portion of the algorithm by way of the "unroll and jam" transformation, so I could test the state of multiple processors in parallel, rather than in serial order as described in the algorithm.) He actually took the time to respond to my email, and was quite gracious. His reply:

In the Bakery Algorithm, process i must wait until a certain condition holds for each other process. The order in which it checks for the different other processes does not matter. So, the algorithm can be parallelized in the manner you suggest.

The only time I was more thrilled on a topic like this was when Dr. Knuth replied to mail I sent him regarding a particular algorithm in Volume 4 of TAOCP. I actually received a hand written reply. Well, he hand wrote notes on a printed copy of the email I had sent to his TAOCP feedback address. Dr. Knuth also encourages me to let all my friends know how much I like TAOCP. So, consider yourself informed: I think Knuth's The Art of Computer Programming series is worth its weight in gold, and if you consider yourself a computer scientist or computer engineer, you should consider getting yourself a copy, and investing the time to at least skim it. (Let's face it, to truly understand everything in there would require as much time as Don put into writing it.)

Re:Welcome to Lamport's Bakery! (1)

Mr Z (6791) | about 6 months ago | (#46531603)

Ok, the statement I made in my third sentence above is imprecise to the point of being inaccurate. The exact property, as described by Wikipedia:

The original proof shows that for overlapping reads and writes to the same storage cell only the write must be correct. The read operation can return an arbitrary number. Therefore this algorithm can be used to implement mutual exclusion on memory that lacks synchronisation primitives

So the part about not needing "properly arbitrated memory access" is mostly true—a read that collides with a write to the same location can return garbage. Writes still must update memory properly, and presumably must be sequentially consistent.

Check for New Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>