0:00:03.300,0:00:08.363
My name is Leslie Lamport and I am a computer scientist,

0:00:09.539,0:00:12.500
which is something that didn't really exist

0:00:12.500,0:00:14.740
when I started being a computer scientist

0:00:14.740,0:00:18.160
and it took me a while to figure out that I was one.

0:00:18.160,0:00:20.960
My relationship with computers began.

0:00:20.960,0:00:23.869
As a programmer, it's never quite occurred to me

0:00:23.869,0:00:26.289
that I was doing anything scientific

0:00:26.289,0:00:28.990
until after I had published enough papers

0:00:28.990,0:00:31.760
that it finally occurred to me.

0:00:31.760,0:00:34.160
My education was as a mathematician.

0:00:34.160,0:00:39.500
It was just natural for me to think about computers as a mathematician.

0:00:39.920,0:00:41.808
When you write an algorithm,

0:00:41.808,0:00:45.200
you need to have a proof that it's correct.

0:00:45.200,0:00:49.240
An algorithm without a proof is a conjecture,

0:00:49.240,0:00:51.280
it's not a theorem.

0:00:51.280,0:00:56.349
And if you're proving things well, that's means "Mathematics".

0:00:56.699,0:01:01.120
Computer scientists tend to think in terms of programming languages.

0:01:01.120,0:01:05.540
One of the epiphanies in my career was the realization

0:01:05.540,0:01:08.938
that I was not writing programs as a computer scientist

0:01:08.938,0:01:10.989
I was designing algorithms.

0:01:11.039,0:01:14.640
I came to realize that if I'm not writing a program,

0:01:14.640,0:01:17.430
I shouldn't use a programming language.

0:01:17.600,0:01:20.880
People confuse "Programming" with "Coding".

0:01:20.880,0:01:25.040
Coding is to programming, while typing is to writing.

0:01:25.040,0:01:27.420
Writing is something that involves mental effort.

0:01:27.420,0:01:29.990
You're thinking about what you're going to say.

0:01:29.990,0:01:31.519
The words have some importance

0:01:31.519,0:01:35.440
but in some sense, even they are secondary to the ideas.

0:01:35.960,0:01:39.670
In the same way, programs are built on ideas.

0:01:39.670,0:01:41.030
They have to do something.

0:01:41.030,0:01:42.690
And what they're supposed to do,

0:01:42.690,0:01:46.659
I mean it's like what writing is supposed to convey.

0:01:46.799,0:01:49.209
If people are trying to learn programming

0:01:49.209,0:01:50.990
by being taught to code

0:01:50.990,0:01:55.799
well, they're being taught writing by being taught how to type.

0:01:55.799,0:01:58.030
And that doesn't make much sense.

0:01:59.119,0:02:03.000
The best way I have for teaching about programming

0:02:03.000,0:02:05.660
as distinct from coding is to think about

0:02:05.660,0:02:08.739
what the program is supposed to do mathematically.

0:02:08.739,0:02:11.799
There's a very big practical problem with this.

0:02:11.799,0:02:15.999
The mathematical education in this country is pretty terrible.

0:02:15.999,0:02:19.330
Most people wind up being afraid of mathematics.

0:02:19.330,0:02:22.149
This is even senior programmers.

0:02:22.149,0:02:24.911
I've developed a language called TLA+

0:02:24.911,0:02:29.520
for writing down the ideas that go into the program.

0:02:29.520,0:02:34.440
Before you do any coding, it's a pretty hard thing for engineers to get into.

0:02:34.440,0:02:39.390
But when they do, it develops their ability to think mathematically.

0:02:51.760,0:02:54.560
A distributed system is one

0:02:54.560,0:02:59.280
in which your computer can be rendered useless

0:02:59.280,0:03:04.400
by the failure of a computer that you didn't even know existed.

0:03:04.400,0:03:08.810
Non-distributed computing is when different processes communicate

0:03:08.810,0:03:11.199
by using the same memory.

0:03:11.199,0:03:14.330
And distributed computing means that

0:03:14.330,0:03:18.020
they're communicating with one another by sending messages.

0:03:18.320,0:03:24.174
Now my interest in distributed systems came about by serendipity.

0:03:24.174,0:03:29.999
I received a preprint of a paper by Robert Thomas and Paul Johnson,

0:03:29.999,0:03:33.730
who had an algorithm for implementing distributed databases.

0:03:33.730,0:03:34.789
These are databases

0:03:34.789,0:03:39.719
where you could have multiple copies of the data sitting at different computers.

0:03:39.719,0:03:43.790
So that programs on each computer could have rapid access to the data.

0:03:43.790,0:03:46.759
But they had to be synchronized

0:03:46.759,0:03:52.679
so that processes on all the computers got consistent views of what the data was.

0:03:52.879,0:03:57.180
I happen to have become quite familiar with special relativity.

0:03:57.180,0:04:00.160
One of the things that special relativity teaches you

0:04:00.160,0:04:02.829
is that two different observers

0:04:02.879,0:04:06.850
have different notions of what at the same time means.

0:04:07.040,0:04:10.239
But there's one notion that is invariant:

0:04:10.239,0:04:14.860
there's a certain notion of one event happening before another event.

0:04:14.860,0:04:16.043
And that means

0:04:16.043,0:04:23.098
that it's possible for information to be transmitted from one event to the others.

0:04:23.605,0:04:27.430
When the information cannot travel faster than the speed of light,

0:04:27.600,0:04:29.680
I realized that

0:04:29.680,0:04:35.969
that notion of causality was violated by the algorithm of Thomas and Johnson.

0:04:35.969,0:04:40.670
It's completely analogous to the relation in special relativity.

0:04:40.880,0:04:46.880
So what I did is I wrote a paper that explained this notion of causality.

0:04:46.980,0:04:51.354
One could solve any distributed system problem

0:04:51.354,0:04:55.680
by building what I called a state machine.

0:04:55.680,0:04:59.929
Think of it as an abstract computer that has one thing at a time.

0:04:59.929,0:05:05.100
You make sure that all the computers in this distributed system

0:05:05.100,0:05:10.490
cooperate to implement a single state machine.

0:05:10.490,0:05:14.729
And that idea has become fundamental

0:05:14.729,0:05:19.360
in the way, people think about building distributed systems.

0:05:19.360,0:05:24.730
I had never even thought about a distributed system before I wrote that paper.

0:05:25.680,0:05:28.180
As I progressed in my career,

0:05:28.180,0:05:31.750
I came to appreciate the idea of working in industry.

0:05:31.750,0:05:35.019
That's where most of the interesting problems that I found came from

0:05:35.019,0:05:38.490
You know from engineers having a problem to solve.

0:05:38.660,0:05:42.729
It reminds me actually of something that ''Auguste Renoir''.

0:05:42.729,0:05:48.879
Once said if someone asked him why he painted outside rather than in his studio.

0:05:48.879,0:05:49.820
And what he said is

0:05:49.820,0:05:53.360
"If I were painting in the studio and I wanted to paint a leaf,

0:05:53.360,0:05:55.760
I would be able to you think of only a half dozen

0:05:55.760,0:05:57.980
or so different kinds of leaves that I could paint.

0:05:57.980,0:06:00.480
But when I was painting outdoors,

0:06:00.480,0:06:04.000
there were just these millions of different kinds of leaves

0:06:04.000,0:06:06.550
that were there that I could paint from."

0:06:06.720,0:06:09.520
I found my research the same way

0:06:09.520,0:06:11.840
that if I sat down, you know, and just,

0:06:11.840,0:06:13.679
you know, contemplated my navel

0:06:13.679,0:06:14.759
and think about problems, you know,

0:06:14.759,0:06:17.599
there's a small number of problems that I could think of.

0:06:17.759,0:06:19.840
But there were just scares of them,

0:06:19.840,0:06:23.090
sitting out in industry, waiting to be, to be solved.

0:06:23.360,0:06:27.581
My favorite of my algorithms is the bakery algorithm.

0:06:27.581,0:06:29.680
It's to solve the mutual exclusion problem

0:06:29.680,0:06:33.520
that is keep two processes from using the printer at the same time.

0:06:33.680,0:06:36.700
Processes choose a number, based on the numbers

0:06:36.700,0:06:40.668
that have been chosen by other processes, and use an algorithm,

0:06:40.668,0:06:43.250
so that the lowest is allowed to use the printer.

0:06:43.250,0:06:45.546
But what is amazing about it

0:06:45.546,0:06:48.947
is it does not make an assumption

0:06:48.947,0:06:51.870
that almost every other algorithm makes

0:06:51.870,0:06:53.500
the assumption being that

0:06:53.500,0:06:58.060
if I say I'm changing my number from 47 to 100

0:06:58.060,0:07:02.089
and you read that number, you'll either get 47 or 100.

0:07:02.089,0:07:06.240
But that algorithm works even if instead of getting 47 or 100,

0:07:06.240,0:07:11.459
you maybe got 4 700 or maybe you got 9 999.

0:07:11.919,0:07:13.919
The algorithm still works.

0:07:13.919,0:07:16.910
I didn't intend it to, I mean I didn't intend that

0:07:16.910,0:07:19.680
I just discovered that when I wrote the proof.

0:07:19.680,0:07:21.959
I never needed to make the assumption.

0:07:21.959,0:07:24.000
That is just so beautiful!

0:07:25.120,0:07:32.100
And, you know, I'm really proud that I stumbled on it.