WEBVTT 00:00:03.300 --> 00:00:08.363 My name is Leslie Lamport and I am a computer scientist, 00:00:09.539 --> 00:00:12.500 which is something that didn't really exist 00:00:12.500 --> 00:00:14.740 when I started being a computer scientist 00:00:14.740 --> 00:00:18.160 and it took me a while to figure out that I was one. 00:00:18.160 --> 00:00:20.960 My relationship with computers began. 00:00:20.960 --> 00:00:23.869 As a programmer, it's never quite occurred to me 00:00:23.869 --> 00:00:26.289 that I was doing anything scientific 00:00:26.289 --> 00:00:28.990 until after I had published enough papers 00:00:28.990 --> 00:00:31.760 that it finally occurred to me. 00:00:31.760 --> 00:00:34.160 My education was as a mathematician. 00:00:34.160 --> 00:00:39.500 It was just natural for me to think about computers as a mathematician. 00:00:39.920 --> 00:00:41.808 When you write an algorithm, 00:00:41.808 --> 00:00:45.200 you need to have a proof that it's correct. 00:00:45.200 --> 00:00:49.240 An algorithm without a proof is a conjecture, 00:00:49.240 --> 00:00:51.280 it's not a theorem. 00:00:51.280 --> 00:00:56.349 And if you're proving things well, that's means "Mathematics". 00:00:56.699 --> 00:01:01.120 Computer scientists tend to think in terms of programming languages. 00:01:01.120 --> 00:01:05.540 One of the epiphanies in my career was the realization 00:01:05.540 --> 00:01:08.938 that I was not writing programs as a computer scientist 00:01:08.938 --> 00:01:10.989 I was designing algorithms. 00:01:11.039 --> 00:01:14.640 I came to realize that if I'm not writing a program, 00:01:14.640 --> 00:01:17.430 I shouldn't use a programming language. 00:01:17.600 --> 00:01:20.880 People confuse "Programming" with "Coding". 00:01:20.880 --> 00:01:25.040 Coding is to programming, while typing is to writing. 00:01:25.040 --> 00:01:27.420 Writing is something that involves mental effort. 00:01:27.420 --> 00:01:29.990 You're thinking about what you're going to say. 00:01:29.990 --> 00:01:31.519 The words have some importance 00:01:31.519 --> 00:01:35.440 but in some sense, even they are secondary to the ideas. 00:01:35.960 --> 00:01:39.670 In the same way, programs are built on ideas. 00:01:39.670 --> 00:01:41.030 They have to do something. 00:01:41.030 --> 00:01:42.690 And what they're supposed to do, 00:01:42.690 --> 00:01:46.659 I mean it's like what writing is supposed to convey. 00:01:46.799 --> 00:01:49.209 If people are trying to learn programming 00:01:49.209 --> 00:01:50.990 by being taught to code 00:01:50.990 --> 00:01:55.799 well, they're being taught writing by being taught how to type. 00:01:55.799 --> 00:01:58.030 And that doesn't make much sense. 00:01:59.119 --> 00:02:03.000 The best way I have for teaching about programming 00:02:03.000 --> 00:02:05.660 as distinct from coding is to think about 00:02:05.660 --> 00:02:08.739 what the program is supposed to do mathematically. 00:02:08.739 --> 00:02:11.799 There's a very big practical problem with this. 00:02:11.799 --> 00:02:15.999 The mathematical education in this country is pretty terrible. 00:02:15.999 --> 00:02:19.330 Most people wind up being afraid of mathematics. 00:02:19.330 --> 00:02:22.149 This is even senior programmers. 00:02:22.149 --> 00:02:24.911 I've developed a language called TLA+ 00:02:24.911 --> 00:02:29.520 for writing down the ideas that go into the program. 00:02:29.520 --> 00:02:34.440 Before you do any coding, it's a pretty hard thing for engineers to get into. 00:02:34.440 --> 00:02:39.390 But when they do, it develops their ability to think mathematically. 00:02:51.760 --> 00:02:54.560 A distributed system is one 00:02:54.560 --> 00:02:59.280 in which your computer can be rendered useless 00:02:59.280 --> 00:03:04.400 by the failure of a computer that you didn't even know existed. 00:03:04.400 --> 00:03:08.810 Non-distributed computing is when different processes communicate 00:03:08.810 --> 00:03:11.199 by using the same memory. 00:03:11.199 --> 00:03:14.330 And distributed computing means that 00:03:14.330 --> 00:03:18.020 they're communicating with one another by sending messages. 00:03:18.320 --> 00:03:24.174 Now my interest in distributed systems came about by serendipity. 00:03:24.174 --> 00:03:29.999 I received a preprint of a paper by Robert Thomas and Paul Johnson, 00:03:29.999 --> 00:03:33.730 who had an algorithm for implementing distributed databases. NOTE Paragraph 00:03:33.730 --> 00:03:34.789 These are databases 00:03:34.789 --> 00:03:39.719 where you could have multiple copies of the data sitting at different computers. 00:03:39.719 --> 00:03:43.790 So that programs on each computer could have rapid access to the data. 00:03:43.790 --> 00:03:46.759 But they had to be synchronized 00:03:46.759 --> 00:03:52.679 so that processes on all the computers got consistent views of what the data was. 00:03:52.879 --> 00:03:57.180 I happen to have become quite familiar with special relativity. 00:03:57.180 --> 00:04:00.160 One of the things that special relativity teaches you 00:04:00.160 --> 00:04:02.829 is that two different observers 00:04:02.879 --> 00:04:06.850 have different notions of what at the same time means. 00:04:07.040 --> 00:04:10.239 But there's one notion that is invariant: 00:04:10.239 --> 00:04:14.860 there's a certain notion of one event happening before another event. 00:04:14.860 --> 00:04:16.043 And that means 00:04:16.043 --> 00:04:23.098 that it's possible for information to be transmitted from one event to the others. 00:04:23.605 --> 00:04:27.430 When the information cannot travel faster than the speed of light, 00:04:27.600 --> 00:04:29.680 I realized that 00:04:29.680 --> 00:04:35.969 that notion of causality was violated by the algorithm of Thomas and Johnson. 00:04:35.969 --> 00:04:40.670 It's completely analogous to the relation in special relativity. 00:04:40.880 --> 00:04:46.880 So what I did is I wrote a paper that explained this notion of causality. 00:04:46.980 --> 00:04:51.354 One could solve any distributed system problem 00:04:51.354 --> 00:04:55.680 by building what I called a state machine. 00:04:55.680 --> 00:04:59.929 Think of it as an abstract computer that has one thing at a time. 00:04:59.929 --> 00:05:05.100 You make sure that all the computers in this distributed system 00:05:05.100 --> 00:05:10.490 cooperate to implement a single state machine. 00:05:10.490 --> 00:05:14.729 And that idea has become fundamental 00:05:14.729 --> 00:05:19.360 in the way, people think about building distributed systems. 00:05:19.360 --> 00:05:24.730 I had never even thought about a distributed system before I wrote that paper. 00:05:25.680 --> 00:05:28.180 As I progressed in my career, 00:05:28.180 --> 00:05:31.750 I came to appreciate the idea of working in industry. 00:05:31.750 --> 00:05:35.019 That's where most of the interesting problems that I found came from 00:05:35.019 --> 00:05:38.490 You know from engineers having a problem to solve. 00:05:38.660 --> 00:05:42.729 It reminds me actually of something that ''Auguste Renoir''. 00:05:42.729 --> 00:05:48.879 Once said if someone asked him why he painted outside rather than in his studio. 00:05:48.879 --> 00:05:49.820 And what he said is 00:05:49.820 --> 00:05:53.360 "If I were painting in the studio and I wanted to paint a leaf, 00:05:53.360 --> 00:05:55.760 I would be able to you think of only a half dozen 00:05:55.760 --> 00:05:57.980 or so different kinds of leaves that I could paint. 00:05:57.980 --> 00:06:00.480 But when I was painting outdoors, 00:06:00.480 --> 00:06:04.000 there were just these millions of different kinds of leaves 00:06:04.000 --> 00:06:06.550 that were there that I could paint from." 00:06:06.720 --> 00:06:09.520 I found my research the same way 00:06:09.520 --> 00:06:11.840 that if I sat down, you know, and just, 00:06:11.840 --> 00:06:13.679 you know, contemplated my navel 00:06:13.679 --> 00:06:14.759 and think about problems, you know, 00:06:14.759 --> 00:06:17.599 there's a small number of problems that I could think of. 00:06:17.759 --> 00:06:19.840 But there were just scares of them, 00:06:19.840 --> 00:06:23.090 sitting out in industry, waiting to be, to be solved. 00:06:23.360 --> 00:06:27.581 My favorite of my algorithms is the bakery algorithm. 00:06:27.581 --> 00:06:29.680 It's to solve the mutual exclusion problem 00:06:29.680 --> 00:06:33.520 that is keep two processes from using the printer at the same time. 00:06:33.680 --> 00:06:36.700 Processes choose a number, based on the numbers 00:06:36.700 --> 00:06:40.668 that have been chosen by other processes, and use an algorithm, 00:06:40.668 --> 00:06:43.250 so that the lowest is allowed to use the printer. 00:06:43.250 --> 00:06:45.546 But what is amazing about it 00:06:45.546 --> 00:06:48.947 is it does not make an assumption 00:06:48.947 --> 00:06:51.870 that almost every other algorithm makes 00:06:51.870 --> 00:06:53.500 the assumption being that 00:06:53.500 --> 00:06:58.060 if I say I'm changing my number from 47 to 100 00:06:58.060 --> 00:07:02.089 and you read that number, you'll either get 47 or 100. 00:07:02.089 --> 00:07:06.240 But that algorithm works even if instead of getting 47 or 100, 00:07:06.240 --> 00:07:11.459 you maybe got 4 700 or maybe you got 9 999. 00:07:11.919 --> 00:07:13.919 The algorithm still works. 00:07:13.919 --> 00:07:16.910 I didn't intend it to, I mean I didn't intend that 00:07:16.910 --> 00:07:19.680 I just discovered that when I wrote the proof. 00:07:19.680 --> 00:07:21.959 I never needed to make the assumption. 00:07:21.959 --> 00:07:24.000 That is just so beautiful! 00:07:25.120 --> 00:07:32.100 And, you know, I'm really proud that I stumbled on it.