1 00:00:03,300 --> 00:00:08,363 My name is Leslie Lamport and I am a computer scientist, 2 00:00:09,539 --> 00:00:12,500 which is something that didn't really exist 3 00:00:12,500 --> 00:00:14,740 when I started being a computer scientist 4 00:00:14,740 --> 00:00:18,160 and it took me a while to figure out that I was one. 5 00:00:18,160 --> 00:00:20,960 My relationship with computers began. 6 00:00:20,960 --> 00:00:23,869 As a programmer, it's never quite occurred to me 7 00:00:23,869 --> 00:00:26,289 that I was doing anything scientific 8 00:00:26,289 --> 00:00:28,990 until after I had published enough papers 9 00:00:28,990 --> 00:00:31,760 that it finally occurred to me. 10 00:00:31,760 --> 00:00:34,160 My education was as a mathematician. 11 00:00:34,160 --> 00:00:39,500 It was just natural for me to think about computers as a mathematician. 12 00:00:39,920 --> 00:00:41,808 When you write an algorithm, 13 00:00:41,808 --> 00:00:45,200 you need to have a proof that it's correct. 14 00:00:45,200 --> 00:00:49,240 An algorithm without a proof is a conjecture, 15 00:00:49,240 --> 00:00:51,280 it's not a theorem. 16 00:00:51,280 --> 00:00:56,349 And if you're proving things well, that's means "Mathematics". 17 00:00:56,699 --> 00:01:01,120 Computer scientists tend to think in terms of programming languages. 18 00:01:01,120 --> 00:01:05,540 One of the epiphanies in my career was the realization 19 00:01:05,540 --> 00:01:08,938 that I was not writing programs as a computer scientist 20 00:01:08,938 --> 00:01:10,989 I was designing algorithms. 21 00:01:11,039 --> 00:01:14,640 I came to realize that if I'm not writing a program, 22 00:01:14,640 --> 00:01:17,430 I shouldn't use a programming language. 23 00:01:17,600 --> 00:01:20,880 People confuse "Programming" with "Coding". 24 00:01:20,880 --> 00:01:25,040 Coding is to programming, while typing is to writing. 25 00:01:25,040 --> 00:01:27,420 Writing is something that involves mental effort. 26 00:01:27,420 --> 00:01:29,990 You're thinking about what you're going to say. 27 00:01:29,990 --> 00:01:31,519 The words have some importance 28 00:01:31,519 --> 00:01:35,440 but in some sense, even they are secondary to the ideas. 29 00:01:35,960 --> 00:01:39,670 In the same way, programs are built on ideas. 30 00:01:39,670 --> 00:01:41,030 They have to do something. 31 00:01:41,030 --> 00:01:42,690 And what they're supposed to do, 32 00:01:42,690 --> 00:01:46,659 I mean it's like what writing is supposed to convey. 33 00:01:46,799 --> 00:01:49,209 If people are trying to learn programming 34 00:01:49,209 --> 00:01:50,990 by being taught to code 35 00:01:50,990 --> 00:01:55,799 well, they're being taught writing by being taught how to type. 36 00:01:55,799 --> 00:01:58,030 And that doesn't make much sense. 37 00:01:59,119 --> 00:02:03,000 The best way I have for teaching about programming 38 00:02:03,000 --> 00:02:05,660 as distinct from coding is to think about 39 00:02:05,660 --> 00:02:08,739 what the program is supposed to do mathematically. 40 00:02:08,739 --> 00:02:11,799 There's a very big practical problem with this. 41 00:02:11,799 --> 00:02:15,999 The mathematical education in this country is pretty terrible. 42 00:02:15,999 --> 00:02:19,330 Most people wind up being afraid of mathematics. 43 00:02:19,330 --> 00:02:22,149 This is even senior programmers. 44 00:02:22,149 --> 00:02:24,911 I've developed a language called TLA+ 45 00:02:24,911 --> 00:02:29,520 for writing down the ideas that go into the program. 46 00:02:29,520 --> 00:02:34,440 Before you do any coding, it's a pretty hard thing for engineers to get into. 47 00:02:34,440 --> 00:02:39,390 But when they do, it develops their ability to think mathematically. 48 00:02:51,760 --> 00:02:54,560 A distributed system is one 49 00:02:54,560 --> 00:02:59,280 in which your computer can be rendered useless 50 00:02:59,280 --> 00:03:04,400 by the failure of a computer that you didn't even know existed. 51 00:03:04,400 --> 00:03:08,810 Non-distributed computing is when different processes communicate 52 00:03:08,810 --> 00:03:11,199 by using the same memory. 53 00:03:11,199 --> 00:03:14,330 And distributed computing means that 54 00:03:14,330 --> 00:03:18,020 they're communicating with one another by sending messages. 55 00:03:18,320 --> 00:03:24,174 Now my interest in distributed systems came about by serendipity. 56 00:03:24,174 --> 00:03:29,999 I received a preprint of a paper by Robert Thomas and Paul Johnson, 57 00:03:29,999 --> 00:03:33,730 who had an algorithm for implementing distributed databases. 58 00:03:33,730 --> 00:03:34,789 These are databases 59 00:03:34,789 --> 00:03:39,719 where you could have multiple copies of the data sitting at different computers. 60 00:03:39,719 --> 00:03:43,790 So that programs on each computer could have rapid access to the data. 61 00:03:43,790 --> 00:03:46,759 But they had to be synchronized 62 00:03:46,759 --> 00:03:52,679 so that processes on all the computers got consistent views of what the data was. 63 00:03:52,879 --> 00:03:57,180 I happen to have become quite familiar with special relativity. 64 00:03:57,180 --> 00:04:00,160 One of the things that special relativity teaches you 65 00:04:00,160 --> 00:04:02,829 is that two different observers 66 00:04:02,879 --> 00:04:06,850 have different notions of what at the same time means. 67 00:04:07,040 --> 00:04:10,239 But there's one notion that is invariant: 68 00:04:10,239 --> 00:04:14,860 there's a certain notion of one event happening before another event. 69 00:04:14,860 --> 00:04:16,043 And that means 70 00:04:16,043 --> 00:04:23,098 that it's possible for information to be transmitted from one event to the others. 71 00:04:23,605 --> 00:04:27,430 When the information cannot travel faster than the speed of light, 72 00:04:27,600 --> 00:04:29,680 I realized that 73 00:04:29,680 --> 00:04:35,969 that notion of causality was violated by the algorithm of Thomas and Johnson. 74 00:04:35,969 --> 00:04:40,670 It's completely analogous to the relation in special relativity. 75 00:04:40,880 --> 00:04:46,880 So what I did is I wrote a paper that explained this notion of causality. 76 00:04:46,980 --> 00:04:51,354 One could solve any distributed system problem 77 00:04:51,354 --> 00:04:55,680 by building what I called a state machine. 78 00:04:55,680 --> 00:04:59,929 Think of it as an abstract computer that has one thing at a time. 79 00:04:59,929 --> 00:05:05,100 You make sure that all the computers in this distributed system 80 00:05:05,100 --> 00:05:10,490 cooperate to implement a single state machine. 81 00:05:10,490 --> 00:05:14,729 And that idea has become fundamental 82 00:05:14,729 --> 00:05:19,360 in the way, people think about building distributed systems. 83 00:05:19,360 --> 00:05:24,730 I had never even thought about a distributed system before I wrote that paper. 84 00:05:25,680 --> 00:05:28,180 As I progressed in my career, 85 00:05:28,180 --> 00:05:31,750 I came to appreciate the idea of working in industry. 86 00:05:31,750 --> 00:05:35,019 That's where most of the interesting problems that I found came from 87 00:05:35,019 --> 00:05:38,490 You know from engineers having a problem to solve. 88 00:05:38,660 --> 00:05:42,729 It reminds me actually of something that ''Auguste Renoir''. 89 00:05:42,729 --> 00:05:48,879 Once said if someone asked him why he painted outside rather than in his studio. 90 00:05:48,879 --> 00:05:49,820 And what he said is 91 00:05:49,820 --> 00:05:53,360 "If I were painting in the studio and I wanted to paint a leaf, 92 00:05:53,360 --> 00:05:55,760 I would be able to you think of only a half dozen 93 00:05:55,760 --> 00:05:57,980 or so different kinds of leaves that I could paint. 94 00:05:57,980 --> 00:06:00,480 But when I was painting outdoors, 95 00:06:00,480 --> 00:06:04,000 there were just these millions of different kinds of leaves 96 00:06:04,000 --> 00:06:06,550 that were there that I could paint from." 97 00:06:06,720 --> 00:06:09,520 I found my research the same way 98 00:06:09,520 --> 00:06:11,840 that if I sat down, you know, and just, 99 00:06:11,840 --> 00:06:13,679 you know, contemplated my navel 100 00:06:13,679 --> 00:06:14,759 and think about problems, you know, 101 00:06:14,759 --> 00:06:17,599 there's a small number of problems that I could think of. 102 00:06:17,759 --> 00:06:19,840 But there were just scares of them, 103 00:06:19,840 --> 00:06:23,090 sitting out in industry, waiting to be, to be solved. 104 00:06:23,360 --> 00:06:27,581 My favorite of my algorithms is the bakery algorithm. 105 00:06:27,581 --> 00:06:29,680 It's to solve the mutual exclusion problem 106 00:06:29,680 --> 00:06:33,520 that is keep two processes from using the printer at the same time. 107 00:06:33,680 --> 00:06:36,700 Processes choose a number, based on the numbers 108 00:06:36,700 --> 00:06:40,668 that have been chosen by other processes, and use an algorithm, 109 00:06:40,668 --> 00:06:43,250 so that the lowest is allowed to use the printer. 110 00:06:43,250 --> 00:06:45,546 But what is amazing about it 111 00:06:45,546 --> 00:06:48,947 is it does not make an assumption 112 00:06:48,947 --> 00:06:51,870 that almost every other algorithm makes 113 00:06:51,870 --> 00:06:53,500 the assumption being that 114 00:06:53,500 --> 00:06:58,060 if I say I'm changing my number from 47 to 100 115 00:06:58,060 --> 00:07:02,089 and you read that number, you'll either get 47 or 100. 116 00:07:02,089 --> 00:07:06,240 But that algorithm works even if instead of getting 47 or 100, 117 00:07:06,240 --> 00:07:11,459 you maybe got 4 700 or maybe you got 9 999. 118 00:07:11,919 --> 00:07:13,919 The algorithm still works. 119 00:07:13,919 --> 00:07:16,910 I didn't intend it to, I mean I didn't intend that 120 00:07:16,910 --> 00:07:19,680 I just discovered that when I wrote the proof. 121 00:07:19,680 --> 00:07:21,959 I never needed to make the assumption. 122 00:07:21,959 --> 00:07:24,000 That is just so beautiful! 123 00:07:25,120 --> 00:07:32,100 And, you know, I'm really proud that I stumbled on it.