Sites Inria

Version française

Turing Award 2013

Olivier Lapirot - 3/06/2014

Leslie Lamport: working at the heart of modern computer science

The American Leslie Lamport, a researcher at the Microsoft Research-Inria joint laboratory, has won the 2013 Turing Award for his contributions to the theory and practice of distributed systems. His work is decrypted by the Inria researcher Damien Doligez.

What is Leslie Lamport's contribution to research in computer science?

- Leslie has worked on distributed computing systems for over 30 years. In the 1980s, his research was highly theoretical, but the subject has now become extremely practical with the emergence of data centers. His work allows all the computers in these centres to work together properly. Leslie Lamport has created two key concepts within this context, namely liveliness and safety . When several computers work together, they communicate by sending each other messages, but none of them know exactly what is happening at any given time. However, two types of blockage can occur: either each computer can wait for the others to do something and nothing happens or the system goes round in circles, giving the false impression that it is working. Leslie developed theories and then techniques to ensure that such blockages do not occur. Liveliness ensures that the system will find something after a certain amount of time. Safety ensures that if the system finds something, it is what is being asked for. These two principles guarantee a good result.

What are the resulting applications?

- The Paxos algorithm, which is at the heart of the Google and Bing search engines, illustrates Leslie's discoveries. When an Internet user sends a request, the servers have to decide which one will handle the request. Paxos tells them how to make the decision. It works even if some of the machines break down. For this reason, Paxos is also one of the building blocks of cloud computing.

His work also involves our individual computers; these have multi-core processors and are part of distributed systems. Each core processor acts like a computer which calculates on its own and communicates with the others through the memory. The principle of "sequential consistency", as described by Leslie Lamport, is a fundamental tool for managing this joint memory as effectively as possible, whilst avoiding bugs.

Keywords: Google Microsoft Research ACM Distributed system Turing Award