WEBVTT

1
00:00:11.026 --> 00:00:14.441
<v ->Did his PhD at Stanford, was on the faculty at Cornell,</v>

2
00:00:14.441 --> 00:00:16.804
and then moved to San Diego where he was chair

3
00:00:16.804 --> 00:00:18.935
of the department for several years.

4
00:00:18.935 --> 00:00:20.322
And currently he's spending time

5
00:00:20.322 --> 00:00:22.069
at the National Science Foundation,

6
00:00:22.069 --> 00:00:24.693
where he's a division director for CNS.

7
00:00:24.693 --> 00:00:26.986
He also is an ACM fellow, for his work,

8
00:00:26.986 --> 00:00:31.153
his foundation work in networking and distributed computing.

9
00:00:33.391 --> 00:00:34.724
<v ->Oh, thank you.</v>

10
00:00:35.950 --> 00:00:40.754
And I think I had Sameer in more than one class.

11
00:00:40.754 --> 00:00:45.054
And he was the brightest student in the class.

12
00:00:45.054 --> 00:00:48.654
Anyway, so what I'm gonna do today is I'm going to,

13
00:00:48.654 --> 00:00:51.371
I'll actually show you a protocol derivation

14
00:00:51.371 --> 00:00:53.390
for a protocol that you may not know.

15
00:00:53.390 --> 00:00:55.311
So part of this talk is gonna be teaching

16
00:00:55.311 --> 00:00:57.285
you a protocol, namely Paxos.

17
00:00:57.285 --> 00:00:59.181
It's a well known protocol.

18
00:00:59.181 --> 00:01:00.908
It's been around for a while.

19
00:01:00.908 --> 00:01:05.592
But the idea is, from this talk, if you don't know Paxos,

20
00:01:05.592 --> 00:01:09.606
then by the end of it, you will think that you do.

21
00:01:09.606 --> 00:01:12.229
And if you know Paxos and have forgotten it,

22
00:01:12.229 --> 00:01:13.956
then you'll remember it

23
00:01:13.956 --> 00:01:15.899
and if you know Paxos inside out,

24
00:01:15.899 --> 00:01:17.508
you'll just enjoy the animation.

25
00:01:17.508 --> 00:01:19.925
So, by the way, this is work,

26
00:01:21.496 --> 00:01:25.830
these are my two colleagues, Alessandro Mei from La Sapienza

27
00:01:25.830 --> 00:01:28.247
and Hein Meling at Stavanger.

28
00:01:30.985 --> 00:01:34.161
So the motivation of this work really comes out

29
00:01:34.161 --> 00:01:37.411
of a fundamental problem of fault tolerance and replication.

30
00:01:37.411 --> 00:01:40.599
So the work I'm going to tell you is somewhat foundational.

31
00:01:40.599 --> 00:01:43.436
I'm going to motivate my problem with respect to some real,

32
00:01:43.436 --> 00:01:46.092
real issues, but in fact I'm gonna be showing you something,

33
00:01:46.092 --> 00:01:48.680
that is really at a sort of

34
00:01:48.680 --> 00:01:51.300
theoretical distributed computing or the interface

35
00:01:51.300 --> 00:01:53.388
in theory and practice.

36
00:01:53.388 --> 00:01:54.981
Much of this work really comes out

37
00:01:54.981 --> 00:01:57.312
of the notion of replication for fault tolerance.

38
00:01:57.312 --> 00:01:59.591
If you've ever looked in the area of fault tolerance,

39
00:01:59.591 --> 00:02:02.087
there is many ways, that you can achieve this,

40
00:02:02.087 --> 00:02:04.604
active replication, passive replication,

41
00:02:04.604 --> 00:02:07.997
software rejuvenation, and so on.

42
00:02:07.997 --> 00:02:11.551
The approach I'm using here is active replication.

43
00:02:11.551 --> 00:02:13.709
The idea here is, that if you wanna replicate something

44
00:02:13.709 --> 00:02:16.252
for failures then you, if you wanna have something

45
00:02:16.252 --> 00:02:17.789
fault tolerant with respect to failure

46
00:02:17.789 --> 00:02:19.259
when it was replicated

47
00:02:19.259 --> 00:02:22.480
and as long as those replicates are deterministic,

48
00:02:22.480 --> 00:02:24.064
you execute the same thing,

49
00:02:24.064 --> 00:02:25.445
you start from the same state,

50
00:02:25.445 --> 00:02:27.807
then they're gonna generate the same sequence of outputs,

51
00:02:27.807 --> 00:02:29.455
follow the same behaviors.

52
00:02:29.455 --> 00:02:32.050
So triple mod redundancy is an example of this.

53
00:02:32.050 --> 00:02:33.794
This is used a lot in terms

54
00:02:33.794 --> 00:02:38.069
of the general process of fault tolerance.

55
00:02:38.069 --> 00:02:41.152
The work I'm doing comes out of that.

56
00:02:42.701 --> 00:02:45.628
The other part of the work I'm doing has to do with,

57
00:02:45.628 --> 00:02:47.829
what are called, byzantine failures

58
00:02:47.829 --> 00:02:49.558
as compared to crash failures.

59
00:02:49.558 --> 00:02:53.242
Byzantine failures is work came out of Leslie Lamport,

60
00:02:53.242 --> 00:02:55.679
he also did stablish in replication.

61
00:02:55.679 --> 00:02:59.180
A byzantine failure is a very challenging failure model

62
00:02:59.180 --> 00:03:02.054
and then we say, that something is byzantine fault tolerant,

63
00:03:02.054 --> 00:03:05.162
if it can dow whatever it wants.

64
00:03:05.162 --> 00:03:06.601
While crash failures is perhaps

65
00:03:06.601 --> 00:03:08.123
the most respected failure model

66
00:03:08.123 --> 00:03:09.217
and crash failure is something can only

67
00:03:09.217 --> 00:03:12.260
fail by stopping the executing.

68
00:03:12.260 --> 00:03:14.207
And the reason, why byzantine fault tolerance

69
00:03:14.207 --> 00:03:15.384
has been interesting, well,

70
00:03:15.384 --> 00:03:18.666
Leslie invented the idea, because he was doing

71
00:03:18.666 --> 00:03:20.328
flat by wiring, he was interested

72
00:03:20.328 --> 00:03:22.514
in some interactions with partner,

73
00:03:22.514 --> 00:03:24.280
timing can make systems,

74
00:03:24.280 --> 00:03:25.480
that you thought were determined

75
00:03:25.480 --> 00:03:27.542
start taking different actions.

76
00:03:27.542 --> 00:03:29.665
So byzantine failures were those in that case.

77
00:03:29.665 --> 00:03:32.603
But going back to the work, that was done by Lisco

78
00:03:32.603 --> 00:03:34.229
and then we'll go Castro,

79
00:03:34.229 --> 00:03:36.321
they were thinking about byzantine failures being

80
00:03:36.321 --> 00:03:39.966
a way of dealing with cyber attacks.

81
00:03:39.966 --> 00:03:41.964
Since if complement is attacked,

82
00:03:41.964 --> 00:03:44.757
then it can behave in arbitrary manners well.

83
00:03:44.757 --> 00:03:46.120
And so if you can build protocols,

84
00:03:46.120 --> 00:03:47.773
that can be byzantine fault tolerant,

85
00:03:47.773 --> 00:03:49.793
then, maybe, you can also have your protocols be

86
00:03:49.793 --> 00:03:52.317
resilient against cyber attacks.

87
00:03:52.317 --> 00:03:56.006
That's the basic idea, intrusion fault tolerance.

88
00:03:56.006 --> 00:03:58.592
Byzantine fault tolerant protocols, on the other hand,

89
00:03:58.592 --> 00:04:01.983
add some problems, often, they can only tolerate

90
00:04:01.983 --> 00:04:05.945
a limited number of failures, for example,

91
00:04:05.945 --> 00:04:07.636
the normal version of byzantine Paxos

92
00:04:07.636 --> 00:04:12.102
can only tolerate up to one third faulty complements.

93
00:04:12.102 --> 00:04:14.660
This is problematic if you can image a system

94
00:04:14.660 --> 00:04:17.254
in which one third of the complements can be attacked,

95
00:04:17.254 --> 00:04:19.857
then maybe they share a vulnerability

96
00:04:19.857 --> 00:04:22.231
and, therefore, more than one third can be attacked.

97
00:04:22.231 --> 00:04:24.567
And so there's been questions in the community

98
00:04:24.567 --> 00:04:26.662
by how impactful his work is.

99
00:04:26.662 --> 00:04:29.007
The way, that Liscov and Castro got around this

100
00:04:29.007 --> 00:04:30.896
is they did N-version programming

101
00:04:30.896 --> 00:04:33.613
in effort to try and spread all the vulnerabilities

102
00:04:33.613 --> 00:04:35.278
with all graduate students,

103
00:04:35.278 --> 00:04:37.195
so outside of je-ke-ra,

104
00:04:38.569 --> 00:04:41.702
this work is looking shared vulnerabilities

105
00:04:41.702 --> 00:04:44.325
across different platforms and using that,

106
00:04:44.325 --> 00:04:45.866
understand how to give the kind of

107
00:04:45.866 --> 00:04:48.454
orthogonality necessary for progress.

108
00:04:48.454 --> 00:04:50.157
So there's some techniques you can do with that,

109
00:04:50.157 --> 00:04:53.081
but still, byzantine fault tolerance has its issues,

110
00:04:53.081 --> 00:04:55.581
in terms of plant and restore.

111
00:04:58.684 --> 00:05:00.200
One of the things we started doing

112
00:05:00.200 --> 00:05:02.005
was trying to think more carefully

113
00:05:02.005 --> 00:05:04.848
about the assumptions we're making about the application

114
00:05:04.848 --> 00:05:07.041
of byzantine fault tolerance.

115
00:05:07.041 --> 00:05:09.120
And we started playing with something

116
00:05:09.120 --> 00:05:12.360
we called Mutually Suspicious Domains.

117
00:05:12.360 --> 00:05:15.307
The idea here is really a fake fate sharing model.

118
00:05:15.307 --> 00:05:16.930
If you have a collection of computers,

119
00:05:16.930 --> 00:05:18.938
that are all being operated in a single domain,

120
00:05:18.938 --> 00:05:20.570
same within this department,

121
00:05:20.570 --> 00:05:22.074
if you have a system to distribute.

122
00:05:22.074 --> 00:05:24.340
Or with an NSF will be for own rules.

123
00:05:24.340 --> 00:05:25.570
Then there's a kind of fate sharing,

124
00:05:25.570 --> 00:05:29.030
that's going on with those computers.

125
00:05:29.030 --> 00:05:31.585
For example, at UCSD, we found,

126
00:05:31.585 --> 00:05:33.959
that those machines, that were in the machine room,

127
00:05:33.959 --> 00:05:35.535
usually at clustering computing,

128
00:05:35.535 --> 00:05:38.757
they can did a fail independently from the computers, say,

129
00:05:38.757 --> 00:05:40.783
outside of the machine room, indeed.

130
00:05:40.783 --> 00:05:44.745
Those machines had the highest failure as it turned out.

131
00:05:44.745 --> 00:05:45.793
They are the most common wise,

132
00:05:45.793 --> 00:05:49.412
because their code was not being turned pretty frequently.

133
00:05:49.412 --> 00:05:52.242
And so there's a kind of fate turning that goes on.

134
00:05:52.242 --> 00:05:55.124
If you have an attack within your administrative domain,

135
00:05:55.124 --> 00:05:58.110
then all those computers are liable to be vulnerable.

136
00:05:58.110 --> 00:05:59.781
At least a large percentage, which means,

137
00:05:59.781 --> 00:06:02.180
that you're going to use a different approach,

138
00:06:02.180 --> 00:06:03.884
than if you're having attacks that are crossing

139
00:06:03.884 --> 00:06:06.226
administrative domains.

140
00:06:06.226 --> 00:06:09.263
And so in the Mutually Suspicious Domain model,

141
00:06:09.263 --> 00:06:11.126
what we said, was within in a domain,

142
00:06:11.126 --> 00:06:14.010
we'll assume a very benign fail model, that of crashes,

143
00:06:14.010 --> 00:06:15.990
which we know is not realistic,

144
00:06:15.990 --> 00:06:18.332
but it's probably okay for a long time

145
00:06:18.332 --> 00:06:20.541
and if you have some kind of problem,

146
00:06:20.541 --> 00:06:23.068
where you have vetted in cyber attack,

147
00:06:23.068 --> 00:06:25.783
byzantine fault tolerance is not gonna help you anywhere.

148
00:06:25.783 --> 00:06:27.487
So you might as well use some other technique

149
00:06:27.487 --> 00:06:30.854
to detection of carving technique, be an intrusion.

150
00:06:30.854 --> 00:06:34.093
And where you should spending your byzantine nibbles

151
00:06:34.093 --> 00:06:36.245
is across domains, saying, that things,

152
00:06:36.245 --> 00:06:37.566
that you don't control,

153
00:06:37.566 --> 00:06:40.870
they are the be-acting in byzantine fault tolerance.

154
00:06:40.870 --> 00:06:43.127
And that's out Mutually Suspicious Domain model.

155
00:06:43.127 --> 00:06:46.794
And we've look at state machine replication.

156
00:06:49.502 --> 00:06:52.823
And so the work I'm going to show you is work,

157
00:06:52.823 --> 00:06:56.323
that comes out of this kind of assumption.

158
00:06:57.414 --> 00:06:59.713
In particular, I'm gonna derive a protocol for you,

159
00:06:59.713 --> 00:07:02.780
called BP Fast Paxos, it's a terrible name,

160
00:07:02.780 --> 00:07:05.981
BP stand for byzantine proposer,

161
00:07:05.981 --> 00:07:09.697
fast has to do with a technical kind of Paxos.

162
00:07:09.697 --> 00:07:11.390
There is a version of Paxos, that was developed,

163
00:07:11.390 --> 00:07:14.761
called Fast Paxos, it's not very practical it turns out,

164
00:07:14.761 --> 00:07:16.178
but it is faster.

165
00:07:18.050 --> 00:07:19.961
So what I'm gonna do is, I'm gonna start

166
00:07:19.961 --> 00:07:22.537
with a very simple definition of Paxos.

167
00:07:22.537 --> 00:07:25.083
Simple, that everybody knows.

168
00:07:25.083 --> 00:07:27.403
And i'll teach you the protocol, so by the end,

169
00:07:27.403 --> 00:07:29.442
you'll have an idea how it works.

170
00:07:29.442 --> 00:07:32.794
And I'm going to take this protocol

171
00:07:32.794 --> 00:07:36.714
and move it to this one, called BP Fast Paxos.

172
00:07:36.714 --> 00:07:40.422
And thus I have a byzantine error right, Hss.

173
00:07:40.422 --> 00:07:42.176
That's called not having your reading glasses on,

174
00:07:42.176 --> 00:07:44.166
when doing your slides.

175
00:07:44.166 --> 00:07:47.343
So the nice thing about BP Fast Paxos is,

176
00:07:47.343 --> 00:07:50.084
that it's based on this Mutually Suspicious Domain

177
00:07:50.084 --> 00:07:53.048
for a cluster environment.

178
00:07:53.048 --> 00:07:54.716
That is, all the servers are gonna preside

179
00:07:54.716 --> 00:07:56.568
within a single cluster,

180
00:07:56.568 --> 00:07:57.918
which means they have fate sharing

181
00:07:57.918 --> 00:08:00.601
and I'm replicating them for purposes of fault tolerance.

182
00:08:00.601 --> 00:08:01.895
That means within that cluster,

183
00:08:01.895 --> 00:08:04.236
I'm going to be using crash failures.

184
00:08:04.236 --> 00:08:05.471
The clients will be outside

185
00:08:05.471 --> 00:08:08.908
and they can be byzantine fault proof.

186
00:08:08.908 --> 00:08:10.980
In fact, the peripheral computers,

187
00:08:10.980 --> 00:08:13.407
the ones in which the clients are talking to the cluster,

188
00:08:13.407 --> 00:08:14.880
can also be our turn of the fault,

189
00:08:14.880 --> 00:08:17.600
because that then with between the net interfaces,

190
00:08:17.600 --> 00:08:19.887
in many ways, it can communicate.

191
00:08:19.887 --> 00:08:22.974
Then the peripheral computers will form a firewall

192
00:08:22.974 --> 00:08:25.029
and a defense mechanism.

193
00:08:25.029 --> 00:08:26.241
And so the interface between them

194
00:08:26.241 --> 00:08:28.358
and the rest of the servers will be narrow

195
00:08:28.358 --> 00:08:31.844
and it'll be assumed, they can be arbitrarily faulty,

196
00:08:31.844 --> 00:08:34.812
they can't affect the behavior on its own.

197
00:08:34.812 --> 00:08:36.166
Or if they do, it'll be wide spread

198
00:08:36.166 --> 00:08:38.919
and you have to protect that from happening.

199
00:08:38.919 --> 00:08:40.789
It's going to have, as you'll see,

200
00:08:40.789 --> 00:08:42.732
more realistic replication limitations

201
00:08:42.732 --> 00:08:45.081
as compared to what I said before,

202
00:08:45.081 --> 00:08:47.351
this is quite fault tolerant.

203
00:08:47.351 --> 00:08:50.530
It offers protection from denial of service attacks,

204
00:08:50.530 --> 00:08:51.517
which is a nice feature

205
00:08:51.517 --> 00:08:53.739
and this what we're doing now, which is,

206
00:08:53.739 --> 00:08:56.385
sends detection recoveries in,

207
00:08:56.385 --> 00:08:59.133
we're working on pulling information

208
00:08:59.133 --> 00:09:00.658
out of the execution of protocol

209
00:09:00.658 --> 00:09:03.575
to detect when attack is happening.

210
00:09:04.518 --> 00:09:06.509
So that's a direction I'm going in.

211
00:09:06.509 --> 00:09:07.749
I'm gonna start from Paxos

212
00:09:07.749 --> 00:09:11.713
and I'm ready to give you a protocol called BP Fast Paxos.

213
00:09:11.713 --> 00:09:13.409
And by the way, this will get you half a way

214
00:09:13.409 --> 00:09:17.576
to PBFT, which is the protocol, that Castro and Liscov did.

215
00:09:26.546 --> 00:09:29.546
Now I'm gonna do a slight hand here,

216
00:09:30.405 --> 00:09:32.962
I've been talking about application of servers

217
00:09:32.962 --> 00:09:35.962
for fault tolerance and I've eluting

218
00:09:37.156 --> 00:09:38.578
to the distinguishing approach,

219
00:09:38.578 --> 00:09:41.191
if you've research in this area,

220
00:09:41.191 --> 00:09:42.941
you know what I'm talking about.

221
00:09:42.941 --> 00:09:45.725
But what I'm gonna do is, I wanna pluck a central protocol

222
00:09:45.725 --> 00:09:47.856
out of this called Consensus.

223
00:09:47.856 --> 00:09:48.899
The reason I'm doing that is,

224
00:09:48.899 --> 00:09:50.252
that's a hard protocol.

225
00:09:50.252 --> 00:09:51.697
There are other things, that you need to solve

226
00:09:51.697 --> 00:09:53.639
to take something, that's also Consensus

227
00:09:53.639 --> 00:09:55.474
to implementing replicating state machines

228
00:09:55.474 --> 00:09:57.015
and they're not trivial,

229
00:09:57.015 --> 00:09:59.305
there are interesting engineering aspects to them.

230
00:09:59.305 --> 00:10:00.540
But if you can solve this problem,

231
00:10:00.540 --> 00:10:02.085
you've gotten most of the way there.

232
00:10:02.085 --> 00:10:04.249
We have taken this all the way to state machines,

233
00:10:04.249 --> 00:10:05.564
but for the purpose of this talk,

234
00:10:05.564 --> 00:10:07.972
I'm just gonna talk about Consensus.

235
00:10:07.972 --> 00:10:10.997
Consensus is a fundamental problem of distributing computing

236
00:10:10.997 --> 00:10:14.266
if you haven't come across before, i'll define it for you.

237
00:10:14.266 --> 00:10:16.715
The idea is you have the center of processes, agents,

238
00:10:16.715 --> 00:10:20.216
whatever you wish, that all have some initial value

239
00:10:20.216 --> 00:10:24.907
and they'd like to do is agree on a value, okay?

240
00:10:24.907 --> 00:10:27.400
So it's that kind of arbitrary problem.

241
00:10:27.400 --> 00:10:32.198
And the rules are, we propose values and we choose values.

242
00:10:32.198 --> 00:10:35.336
And the chosen value will ask you what are proposed values.

243
00:10:35.336 --> 00:10:36.872
That gets rid of the trivial assumption

244
00:10:36.872 --> 00:10:39.329
and just choose zero.

245
00:10:39.329 --> 00:10:41.963
You have to choose some kind of value as proposed.

246
00:10:41.963 --> 00:10:44.495
All these singles values chosen, you can't change you mind,

247
00:10:44.495 --> 00:10:49.099
once the value is chosen, they're all gonna agree.

248
00:10:49.099 --> 00:10:50.751
Some proposed values eventually chosen,

249
00:10:50.751 --> 00:10:52.160
that is, there's alliance.

250
00:10:52.160 --> 00:10:53.989
We're eventually gonna be able to do this.

251
00:10:53.989 --> 00:10:56.629
So in the context of state machines, you can imagine,

252
00:10:56.629 --> 00:10:57.670
that you have a set of clients,

253
00:10:57.670 --> 00:10:59.204
that are proposing commands,

254
00:10:59.204 --> 00:11:02.044
that are executed by the machines.

255
00:11:02.044 --> 00:11:03.496
Another way to put it, is you have a service,

256
00:11:03.496 --> 00:11:05.345
they all want different actions to take.

257
00:11:05.345 --> 00:11:06.425
This is going to guarantee,

258
00:11:06.425 --> 00:11:08.100
that one action is gonna be taken

259
00:11:08.100 --> 00:11:10.962
and all the replicas will agree on what action to take.

260
00:11:10.962 --> 00:11:13.891
That's the Consensus protocol.

261
00:11:13.891 --> 00:11:17.207
Consensus has been studied a lot, this again,

262
00:11:17.207 --> 00:11:19.873
was first done Leslie Lamport,

263
00:11:19.873 --> 00:11:22.292
he did a lot of work in this area.

264
00:11:22.292 --> 00:11:24.295
I'm going to be doing it in a context

265
00:11:24.295 --> 00:11:28.215
of asynchronous systems, that's why I'm using Paxos.

266
00:11:28.215 --> 00:11:29.976
An asynchronous system is one in,

267
00:11:29.976 --> 00:11:31.920
which there's no sense of time,

268
00:11:31.920 --> 00:11:33.744
which means I can't put a bound

269
00:11:33.744 --> 00:11:35.527
on how quickly things execute,

270
00:11:35.527 --> 00:11:37.204
I can't out a bound in how long it takes

271
00:11:37.204 --> 00:11:39.537
messages to be communicated.

272
00:11:40.710 --> 00:11:43.389
This is appropriate for most systems we have,

273
00:11:43.389 --> 00:11:45.408
although there are certainly some applications,

274
00:11:45.408 --> 00:11:47.771
where more synchronous models make sense.

275
00:11:47.771 --> 00:11:49.511
This is a very general result.

276
00:11:49.511 --> 00:11:51.057
And there's been a lot work in Paxos,

277
00:11:51.057 --> 00:11:53.243
because with such a beautiful protocol,

278
00:11:53.243 --> 00:11:55.203
there are crash fault tolerant versions

279
00:11:55.203 --> 00:11:56.505
and when you show you wanted them,

280
00:11:56.505 --> 00:11:58.270
there's byzantine fault tolerant versions,

281
00:11:58.270 --> 00:12:00.095
I've mentioned a couple others,

282
00:12:00.095 --> 00:12:02.152
that are slow latency versions.

283
00:12:02.152 --> 00:12:04.694
This has been for a while the real rule binder

284
00:12:04.694 --> 00:12:07.694
of research and understanding Paxos.

285
00:12:09.658 --> 00:12:10.491
Okay.

286
00:12:11.688 --> 00:12:14.224
I think I've set this up.

287
00:12:14.224 --> 00:12:17.931
Now, what I'm gonna do in the next 10 minutes, 15 minutes,

288
00:12:17.931 --> 00:12:19.770
is I'm gonna teach you Paxos.

289
00:12:19.770 --> 00:12:21.372
See if you can get this.

290
00:12:21.372 --> 00:12:23.884
How many here already know Paxos?

291
00:12:23.884 --> 00:12:25.801
A few, excellent, okay.

292
00:12:26.758 --> 00:12:29.798
You can tell me when I'm wrong.

293
00:12:29.798 --> 00:12:33.256
So remember, Paxos is a protocol for solving Consensus.

294
00:12:33.256 --> 00:12:35.667
Consensus is where you have a set of precesses,

295
00:12:35.667 --> 00:12:37.612
that want to propose a value

296
00:12:37.612 --> 00:12:40.118
and eventually they're all going to agree on a value,

297
00:12:40.118 --> 00:12:41.942
that they choose, the accepted value.

298
00:12:41.942 --> 00:12:45.089
Yes, a kind of arbitrary problem.

299
00:12:45.089 --> 00:12:47.285
The way Paxos is normally presented

300
00:12:47.285 --> 00:12:50.851
is we represent three different kind of agents.

301
00:12:50.851 --> 00:12:52.479
And this is just for clarity.

302
00:12:52.479 --> 00:12:55.154
When you actually deploy Paxos,

303
00:12:55.154 --> 00:12:59.811
you can have processes take on two or three of these roles,

304
00:12:59.811 --> 00:13:01.830
it really depends on how you want to use them.

305
00:13:01.830 --> 00:13:02.847
But for these purposes,

306
00:13:02.847 --> 00:13:04.364
we're going to have three kinds of agents,

307
00:13:04.364 --> 00:13:06.017
that are called proposers.

308
00:13:06.017 --> 00:13:08.533
Proposers propose values.

309
00:13:08.533 --> 00:13:11.865
We have acceptors, acceptors accept values,

310
00:13:11.865 --> 00:13:12.833
also good that we have

311
00:13:12.833 --> 00:13:14.129
and then we have learners.

312
00:13:14.129 --> 00:13:17.966
Learners are the ones, that learn the chosen value.

313
00:13:17.966 --> 00:13:19.940
That's just how we're gonna separate this.

314
00:13:19.940 --> 00:13:21.699
And we're gonna describe the actions of Paxos

315
00:13:21.699 --> 00:13:23.945
in terms of what proposers do,

316
00:13:23.945 --> 00:13:27.100
except there's new network externals.

317
00:13:27.100 --> 00:13:29.100
Most of the action is gonna be taking place,

318
00:13:29.100 --> 00:13:32.759
as you can imagine, between the proposers and the acceptors,

319
00:13:32.759 --> 00:13:35.149
because they're the ones, that have to figure out this

320
00:13:35.149 --> 00:13:36.907
arbitration problem.

321
00:13:36.907 --> 00:13:39.023
They're giving all the problems values being proposed

322
00:13:39.023 --> 00:13:41.404
and yet one of them has to be accepted

323
00:13:41.404 --> 00:13:42.696
or one of these has to be chosen.

324
00:13:42.696 --> 00:13:44.178
So they are the ones, that are working.

325
00:13:44.178 --> 00:13:45.753
A learner's job is just to understand

326
00:13:45.753 --> 00:13:47.238
which is the one that's the top.

327
00:13:47.238 --> 00:13:49.891
It turns out, learners are really important.

328
00:13:49.891 --> 00:13:51.458
They solve a hard problem,

329
00:13:51.458 --> 00:13:54.348
but in terms of their function they are not doing very much.

330
00:13:54.348 --> 00:13:56.839
Paxos is beautiful, because it's safe for

331
00:13:56.839 --> 00:13:58.260
any network crash failures,

332
00:13:58.260 --> 00:14:00.510
it's a quite robust protocol

333
00:14:00.510 --> 00:14:04.256
and I can make progress with up to t a crash failures,

334
00:14:04.256 --> 00:14:06.223
you'll see, why I put a subscript in there,

335
00:14:06.223 --> 00:14:09.007
given these two t a plus one acceptors.

336
00:14:09.007 --> 00:14:11.725
That is, the acceptors up to,

337
00:14:11.725 --> 00:14:14.590
but not a majority of acceptors can crash

338
00:14:14.590 --> 00:14:17.130
and the thing will still make problems.

339
00:14:17.130 --> 00:14:18.595
So it's very resilient.

340
00:14:18.595 --> 00:14:21.279
And it works fine in an asynchronous system,

341
00:14:21.279 --> 00:14:22.931
not only that, you can drop messages,

342
00:14:22.931 --> 00:14:25.318
you can reorder messages, I'm not gonna talk

343
00:14:25.318 --> 00:14:26.456
about any of that stuff,

344
00:14:26.456 --> 00:14:27.756
because it's just confusing,

345
00:14:27.756 --> 00:14:30.776
but it's really a wonderful protocol.

346
00:14:30.776 --> 00:14:33.755
If you don't know Paxos and after this,

347
00:14:33.755 --> 00:14:37.554
you oughta read simple cases of this room.

348
00:14:37.554 --> 00:14:39.221
Okay, so here we go,

349
00:14:40.291 --> 00:14:43.563
I'm going to teach you Paxos by showing you examples.

350
00:14:43.563 --> 00:14:46.457
I know this not a robust way to do it,

351
00:14:46.457 --> 00:14:48.933
but in the end you'll understand why.

352
00:14:48.933 --> 00:14:50.816
So proposers are going to be circles,

353
00:14:50.816 --> 00:14:53.242
acceptors are squares and learners are triangles

354
00:14:53.242 --> 00:14:54.736
or diamonds, I should say.

355
00:14:54.736 --> 00:14:56.645
And I'm gonna show you state.

356
00:14:56.645 --> 00:14:57.877
Our proposers are gonna have

357
00:14:57.877 --> 00:14:59.373
little thought clouds above them,

358
00:14:59.373 --> 00:15:01.140
that's a value they'd like to propose,

359
00:15:01.140 --> 00:15:03.640
that's the one they're going to propose if they can.

360
00:15:03.640 --> 00:15:06.455
And the options state and acceptors are half state,

361
00:15:06.455 --> 00:15:07.516
that then accepted them.

362
00:15:07.516 --> 00:15:08.544
Learners have a single value,

363
00:15:08.544 --> 00:15:10.605
when they find and learn the outcome,

364
00:15:10.605 --> 00:15:14.245
they chosen value changes in the chosen one they have.

365
00:15:14.245 --> 00:15:16.161
This protocol's round based,

366
00:15:16.161 --> 00:15:19.089
which means, we're gonna be executing round after round.

367
00:15:19.089 --> 00:15:21.928
It may go this forever, the protocol's not live.

368
00:15:21.928 --> 00:15:24.860
This is a fundamental result from Fisher Lynch Patterson,

369
00:15:24.860 --> 00:15:27.105
we can't solve this problem in UI.

370
00:15:27.105 --> 00:15:29.081
You have to leak in a little synchronism

371
00:15:29.081 --> 00:15:32.081
if we guarantee, that it terminates.

372
00:15:33.247 --> 00:15:36.882
What's gonna happen is, a proposer is gonna choose a round,

373
00:15:36.882 --> 00:15:38.844
the round is gonna be a unique round,

374
00:15:38.844 --> 00:15:40.511
that no one else has chosen.

375
00:15:40.511 --> 00:15:41.869
We're not gonna really argue again

376
00:15:41.869 --> 00:15:44.460
how they can do that, it turns out that's not hard.

377
00:15:44.460 --> 00:15:46.793
And in each round they're gonna be trying

378
00:15:46.793 --> 00:15:50.970
to get enough acceptors to agree on their value.

379
00:15:50.970 --> 00:15:53.376
If they can get enough accepts to accept their value,

380
00:15:53.376 --> 00:15:54.997
namely a majority of them,

381
00:15:54.997 --> 00:15:56.380
then that value's gonna be the one,

382
00:15:56.380 --> 00:15:58.655
that the learners will learn.

383
00:15:58.655 --> 00:16:02.759
Once a majority of acceptors accept the same value,

384
00:16:02.759 --> 00:16:05.627
that's a value that's chosen.

385
00:16:05.627 --> 00:16:07.634
So clearly there has to be some rules,

386
00:16:07.634 --> 00:16:10.335
because you can't have two values given a majority.

387
00:16:10.335 --> 00:16:11.925
That's why the interactions

388
00:16:11.925 --> 00:16:14.599
with proposers and acceptors is complex.

389
00:16:14.599 --> 00:16:18.785
So they do these rounds and learners will learnt the value.

390
00:16:18.785 --> 00:16:22.017
The rounds each consist of two phases,

391
00:16:22.017 --> 00:16:24.779
so it's a two phase protocol.

392
00:16:24.779 --> 00:16:28.892
And in fact, I can show that to you right now.

393
00:16:28.892 --> 00:16:32.246
In the first phase, proposers are gonna be trying

394
00:16:32.246 --> 00:16:34.341
to get acceptors to accept their value.

395
00:16:34.341 --> 00:16:36.809
Get them to a promise to accept their value.

396
00:16:36.809 --> 00:16:38.324
And acceptors will promise as long

397
00:16:38.324 --> 00:16:42.772
as it isn't super seeded by a proposer with a larger round.

398
00:16:42.772 --> 00:16:44.689
So in other words, you may have to propose and say,

399
00:16:44.689 --> 00:16:47.298
"I'm trying round five, take my value",

400
00:16:47.298 --> 00:16:48.252
and the acceptors will say,

401
00:16:48.252 --> 00:16:53.110
"sure, I will not take anything less, than round five".

402
00:16:53.110 --> 00:16:55.534
And as long as no one and says,

403
00:16:55.534 --> 00:16:57.234
"Do my round, round six".

404
00:16:57.234 --> 00:17:00.234
Then the proposer's value is chosen.

405
00:17:03.343 --> 00:17:04.541
So it's gonna be these two phases,

406
00:17:04.541 --> 00:17:05.748
first one, get them to promise,

407
00:17:05.748 --> 00:17:08.997
the second one, to actually accept the values.

408
00:17:08.997 --> 00:17:10.567
We're gonna do this with messages, proposers,

409
00:17:10.567 --> 00:17:14.393
we'll send a message, called prepare, with its current round

410
00:17:14.393 --> 00:17:15.711
that's what that first value is,

411
00:17:15.711 --> 00:17:17.690
that's a round it's driving towards

412
00:17:17.690 --> 00:17:20.257
and the value is the value that it's driving toward.

413
00:17:20.257 --> 00:17:22.596
So in the first round it tells acceptors,

414
00:17:22.596 --> 00:17:25.620
"Prepare yourself, promise me, that you'll do this round

415
00:17:25.620 --> 00:17:27.552
or he needs it nonetheless"

416
00:17:27.552 --> 00:17:29.471
and then they will respond with a promise,

417
00:17:29.471 --> 00:17:30.963
saying, "I will do that".

418
00:17:30.963 --> 00:17:33.359
They'll say what round, that they're at,

419
00:17:33.359 --> 00:17:34.903
they're also saying the value,

420
00:17:34.903 --> 00:17:37.770
that they last accepted in which round,

421
00:17:37.770 --> 00:17:39.875
you'll see why it's important soon.

422
00:17:39.875 --> 00:17:43.365
And then once the proposers get these promises back,

423
00:17:43.365 --> 00:17:47.584
they say, "Please accept my value, here's my value"

424
00:17:47.584 --> 00:17:51.380
and If the acceptor has not lost his value,

425
00:17:51.380 --> 00:17:53.857
then it will actually tell the learners,

426
00:17:53.857 --> 00:17:57.054
otherwise, we're not invited.

427
00:17:57.054 --> 00:17:59.276
Okay, so I'm now gonna show you

428
00:17:59.276 --> 00:18:00.788
a couple of executions of Paxos,

429
00:18:00.788 --> 00:18:02.705
just to see it's going.

430
00:18:04.369 --> 00:18:06.463
So here's our initial state,

431
00:18:06.463 --> 00:18:10.229
we have three proposers, three acceptors and three learners.

432
00:18:10.229 --> 00:18:13.590
And we can tolerate how many failures of acceptors?

433
00:18:13.590 --> 00:18:14.635
One, right?

434
00:18:14.635 --> 00:18:16.968
Because the majority is two.

435
00:18:17.852 --> 00:18:20.494
Okay, first proposer is hoping,

436
00:18:20.494 --> 00:18:22.534
that 11 is the value that gets chosen,

437
00:18:22.534 --> 00:18:24.519
the second one wants 76

438
00:18:24.519 --> 00:18:26.357
and the third one wants 22.

439
00:18:26.357 --> 00:18:28.795
And no one knows, it's all the initial state.

440
00:18:28.795 --> 00:18:32.777
So the learners, for example, don't know.

441
00:18:32.777 --> 00:18:35.652
Our first proposer sends a message out.

442
00:18:35.652 --> 00:18:37.498
It chooses round one.

443
00:18:37.498 --> 00:18:39.232
How did it choose round one, it doesn't matter,

444
00:18:39.232 --> 00:18:40.468
it's just a unique round.

445
00:18:40.468 --> 00:18:43.141
You'll see later, I'll show you how we can fix that.

446
00:18:43.141 --> 00:18:45.775
But all I ask to do is choose a unique number

447
00:18:45.775 --> 00:18:47.548
and this can be done in many ways.

448
00:18:47.548 --> 00:18:49.277
So it sends, prepare yourself for one

449
00:18:49.277 --> 00:18:50.638
and these go to all the acceptors.

450
00:18:50.638 --> 00:18:52.860
In this case, one of the messages are slower

451
00:18:52.860 --> 00:18:54.463
and never gets down to this one.

452
00:18:54.463 --> 00:18:57.063
It's an asynchronous program.

453
00:18:57.063 --> 00:19:00.789
And these acceptors respond, saying,

454
00:19:00.789 --> 00:19:04.867
"Okay, I now promise not to accept any value,

455
00:19:04.867 --> 00:19:07.308
that has a round less than one".

456
00:19:07.308 --> 00:19:08.903
This is an easy promise to make,

457
00:19:08.903 --> 00:19:10.820
because one is the lowest round.

458
00:19:10.820 --> 00:19:14.870
But nonetheless, they promise it, okay?

459
00:19:14.870 --> 00:19:16.684
The next thing this guy's gonna do then

460
00:19:16.684 --> 00:19:21.220
is trying to get the acceptors to accept its value.

461
00:19:21.220 --> 00:19:25.086
Unfortunately, first they come back and say,

462
00:19:25.086 --> 00:19:26.039
"Okay, I promise".

463
00:19:26.039 --> 00:19:28.606
And they've never accepted the value before,

464
00:19:28.606 --> 00:19:32.620
so they just come back with empty values.

465
00:19:32.620 --> 00:19:36.453
Now the next step, this one, chooses round two

466
00:19:37.734 --> 00:19:41.198
and sends messages to acceptors, saying,

467
00:19:41.198 --> 00:19:46.138
"Promise, that you won't take anything less than two".

468
00:19:46.138 --> 00:19:47.239
Now this is a real promise,

469
00:19:47.239 --> 00:19:50.385
because there is a round one.

470
00:19:50.385 --> 00:19:51.802
And they do that.

471
00:19:53.238 --> 00:19:55.688
And notice now, in doing so, this proposer

472
00:19:55.688 --> 00:19:58.536
has cut out this proposer up here.

473
00:19:58.536 --> 00:20:00.669
Cuz this one is driving towards round one

474
00:20:00.669 --> 00:20:02.810
and so this one promise to say,

475
00:20:02.810 --> 00:20:04.563
"I will not take anything less than one",

476
00:20:04.563 --> 00:20:07.584
is now saying, "I will not take anything less than two".

477
00:20:07.584 --> 00:20:09.184
And so it won't accept the value

478
00:20:09.184 --> 00:20:11.851
coming from that first proposal.

479
00:20:14.769 --> 00:20:17.721
They respond with their promises, saying yes,

480
00:20:17.721 --> 00:20:19.462
each acceptor tells this proposer,

481
00:20:19.462 --> 00:20:23.629
"I will not accept any new, unless it's round two".

482
00:20:26.860 --> 00:20:29.337
In the mean time, our proposer up here,

483
00:20:29.337 --> 00:20:31.676
now is trying to drive its value forward.

484
00:20:31.676 --> 00:20:34.054
It's trying to get one to be the chosen value.

485
00:20:34.054 --> 00:20:36.648
And so it send a message out, this is the second phase,

486
00:20:36.648 --> 00:20:40.592
saying, "Accept my value, it's round one

487
00:20:40.592 --> 00:20:42.750
and the value's up".

488
00:20:42.750 --> 00:20:45.448
And the first one is going to be quite happy to take that,

489
00:20:45.448 --> 00:20:47.688
because it promised, it will take anything,

490
00:20:47.688 --> 00:20:49.974
that's one or higher.

491
00:20:49.974 --> 00:20:52.493
Second one can't, because it's already taken this,

492
00:20:52.493 --> 00:20:53.826
I can't go back.

493
00:20:54.951 --> 00:20:57.569
So the first one is going to accept the values

494
00:20:57.569 --> 00:20:59.463
and now it says, "I'm in round one,

495
00:20:59.463 --> 00:21:01.171
I accepted the value of round one,

496
00:21:01.171 --> 00:21:04.746
that the value I accepted was 11".

497
00:21:04.746 --> 00:21:05.937
And the second one does nothing,

498
00:21:05.937 --> 00:21:08.437
because it's already read off.

499
00:21:12.380 --> 00:21:13.815
The acceptor having learned the value

500
00:21:13.815 --> 00:21:15.778
sends a message to the acceptor, saying,

501
00:21:15.778 --> 00:21:19.195
"I learned a value, round one, value 11".

502
00:21:21.682 --> 00:21:25.067
This is unimportant, because it's the only acceptor,

503
00:21:25.067 --> 00:21:26.357
that's accepted the value,

504
00:21:26.357 --> 00:21:31.158
but if any learner receives that message from two acceptors,

505
00:21:31.158 --> 00:21:32.876
it's learned the chose value,

506
00:21:32.876 --> 00:21:35.793
because it's gotten from round two.

507
00:21:37.038 --> 00:21:38.538
You are not bored?

508
00:21:47.066 --> 00:21:49.775
This one, now, is continuing along

509
00:21:49.775 --> 00:21:52.994
and it's going to to try to get the value two,

510
00:21:52.994 --> 00:21:55.661
sorry, 22 accepted in round two.

511
00:21:57.054 --> 00:21:58.547
It sends out its message

512
00:21:58.547 --> 00:22:00.265
and because it's an asynchronous system,

513
00:22:00.265 --> 00:22:02.408
it only gets to the second acceptor.

514
00:22:02.408 --> 00:22:04.303
This is a terrible execution,

515
00:22:04.303 --> 00:22:06.826
we're making no progress very quickly here.

516
00:22:06.826 --> 00:22:10.463
But I'm using this to try to show you the protocol.

517
00:22:10.463 --> 00:22:12.679
And it will accept the value, so notice,

518
00:22:12.679 --> 00:22:14.484
it now says, "I'm in round two

519
00:22:14.484 --> 00:22:16.828
and the last value accepted was in round two

520
00:22:16.828 --> 00:22:19.330
and that values is 22".

521
00:22:19.330 --> 00:22:23.110
And the next thing it will do is it will tell the learners,

522
00:22:23.110 --> 00:22:26.245
that it accepted value two in round 22.

523
00:22:26.245 --> 00:22:27.906
The first learner up here knows,

524
00:22:27.906 --> 00:22:29.650
that that one took something in round one,

525
00:22:29.650 --> 00:22:31.028
this one took something in round two,

526
00:22:31.028 --> 00:22:34.081
they're not the same round, so it doesn't matter.

527
00:22:34.081 --> 00:22:35.569
The other learners, this is the first time

528
00:22:35.569 --> 00:22:36.697
they've heard about anything.

529
00:22:36.697 --> 00:22:38.186
If they hear from any other acceptor,

530
00:22:38.186 --> 00:22:40.584
that value two, 22 has been accepted,

531
00:22:40.584 --> 00:22:42.528
then that's the chosen value,

532
00:22:42.528 --> 00:22:44.861
but that's not gonna happen.

533
00:22:47.554 --> 00:22:49.378
Okay, this one now starts

534
00:22:49.378 --> 00:22:51.967
and it's going to do round three.

535
00:22:51.967 --> 00:22:54.219
Again, it just has to do defense.

536
00:22:54.219 --> 00:22:58.476
So it sends out a prepare message, it gets to these two.

537
00:22:58.476 --> 00:23:00.892
And they end up both saying,

538
00:23:00.892 --> 00:23:04.221
they will not take anything earlier than round three

539
00:23:04.221 --> 00:23:07.561
and they are going to send back the message, saying,

540
00:23:07.561 --> 00:23:10.692
"what is the last value you've accepted?"

541
00:23:10.692 --> 00:23:12.758
So the top one says," the last value I accepted

542
00:23:12.758 --> 00:23:14.918
was round one value 11"

543
00:23:14.918 --> 00:23:18.501
and this acceptor hasn't accepted anything.

544
00:23:19.362 --> 00:23:21.191
This is the last part, if you understand this,

545
00:23:21.191 --> 00:23:23.191
you'll understand Paxos.

546
00:23:25.479 --> 00:23:27.541
Now what's our poor proposer supposed to do

547
00:23:27.541 --> 00:23:28.663
with this information?

548
00:23:28.663 --> 00:23:30.425
What did it just find out?

549
00:23:30.425 --> 00:23:33.024
It found out, that that acceptor up there,

550
00:23:33.024 --> 00:23:35.691
accepted a value 11 in round one

551
00:23:37.066 --> 00:23:40.524
and this one hasn't accepted anything, right?

552
00:23:40.524 --> 00:23:42.188
But it doesn't know anything about the middle,

553
00:23:42.188 --> 00:23:44.999
because that message got dropped.

554
00:23:44.999 --> 00:23:46.569
It's possible that acceptor

555
00:23:46.569 --> 00:23:49.486
has accepted value 11 in round one.

556
00:23:51.817 --> 00:23:53.956
It turns out it didn't, but it doesn't know.

557
00:23:53.956 --> 00:23:56.193
That's a possible world.

558
00:23:56.193 --> 00:24:00.301
And because of that, had that acceptor accepted that value,

559
00:24:00.301 --> 00:24:04.081
then 11 would have been the chosen value in round one,

560
00:24:04.081 --> 00:24:06.991
because two acceptors would have chosen the same value.

561
00:24:06.991 --> 00:24:11.554
So at this point our proposer is constrained.

562
00:24:11.554 --> 00:24:12.887
It can't propose any value,

563
00:24:12.887 --> 00:24:14.509
because it's impossible,

564
00:24:14.509 --> 00:24:17.479
that 11 was the chose value in round one.

565
00:24:17.479 --> 00:24:21.646
So that means our proposer can't propose 76 anymore.

566
00:24:22.810 --> 00:24:26.075
It has to propose 11, because there's a possible world

567
00:24:26.075 --> 00:24:28.825
in which 11 was the chosen value.

568
00:24:30.586 --> 00:24:32.753
That's the trick of Paxos.

569
00:24:34.189 --> 00:24:37.106
So all it's going to do is go ahead

570
00:24:38.296 --> 00:24:40.546
and say, "Accept three 11".

571
00:24:41.561 --> 00:24:42.710
It's a constrained value,

572
00:24:42.710 --> 00:24:45.669
that 11 being the one, that might have been accepted.

573
00:24:45.669 --> 00:24:48.411
And again, this message is gonna get lost up there,

574
00:24:48.411 --> 00:24:50.614
because of these two.

575
00:24:50.614 --> 00:24:53.791
They accepted values and now they are three, three, 11

576
00:24:53.791 --> 00:24:55.800
and they both stand, because of that,

577
00:24:55.800 --> 00:24:57.078
we now have a chosen value,

578
00:24:57.078 --> 00:24:59.483
two things have chosen the same value acceptors.

579
00:24:59.483 --> 00:25:03.186
And they send out the learn messages

580
00:25:03.186 --> 00:25:04.068
and that way we have two learners,

581
00:25:04.068 --> 00:25:07.235
that are figuring out what's going on.

582
00:25:08.495 --> 00:25:09.578
That's Paxos.

583
00:25:10.766 --> 00:25:12.503
Now there's a lot of messiness in here

584
00:25:12.503 --> 00:25:15.074
I'm not really gonna go into, for example,

585
00:25:15.074 --> 00:25:17.208
what about that second learner there?

586
00:25:17.208 --> 00:25:18.661
It never learned when it went on,

587
00:25:18.661 --> 00:25:20.713
because the message got dropped.

588
00:25:20.713 --> 00:25:22.256
That one turns out to be easy to solve,

589
00:25:22.256 --> 00:25:23.827
all it has to do, when it gets tired,

590
00:25:23.827 --> 00:25:27.304
is ask a proposer to propose something

591
00:25:27.304 --> 00:25:28.752
and they'll go off and do it.

592
00:25:28.752 --> 00:25:31.170
There's a lot of details here I haven't shown you,

593
00:25:31.170 --> 00:25:33.442
but that's really the core of Paxos.

594
00:25:33.442 --> 00:25:36.840
Its two phase protocol, where proposers find out

595
00:25:36.840 --> 00:25:41.207
if the value can possible been accepted or been chosen,

596
00:25:41.207 --> 00:25:44.235
if so, they continue to choose that value,

597
00:25:44.235 --> 00:25:45.265
to propose that value.

598
00:25:45.265 --> 00:25:48.932
If not, they can propose whatever they want.

599
00:25:50.789 --> 00:25:54.526
And this is the protocol if you wanna see it in pseudocode.

600
00:25:54.526 --> 00:25:57.942
It's actually a pretty simple protocol.

601
00:25:57.942 --> 00:26:01.133
When I teach at UC, I take three hours

602
00:26:01.133 --> 00:26:03.507
to derive the protocol.

603
00:26:03.507 --> 00:26:06.077
Understand, I will get going pretty fast here,

604
00:26:06.077 --> 00:26:09.236
so if you're a little bit fuzzy about it, it's okay.

605
00:26:09.236 --> 00:26:11.610
But what I really want you to understand from this

606
00:26:11.610 --> 00:26:13.259
is the basic idea,

607
00:26:13.259 --> 00:26:14.553
because what I'm going to do now

608
00:26:14.553 --> 00:26:16.096
is take this protocol,

609
00:26:16.096 --> 00:26:18.666
I'm gonna modify it in a couple of ways

610
00:26:18.666 --> 00:26:21.103
to get to my protocol.

611
00:26:21.103 --> 00:26:23.027
At least I want you to believe this is correct

612
00:26:23.027 --> 00:26:23.989
and know what the phases are,

613
00:26:23.989 --> 00:26:27.286
so you see where my modifications are.

614
00:26:27.286 --> 00:26:30.185
Any questions, before it goes, or something?

615
00:26:30.185 --> 00:26:31.249
<v Listener>You skipped about this,</v>

616
00:26:31.249 --> 00:26:33.181
but how are you generating the numbers?

617
00:26:33.181 --> 00:26:34.138
Are you using randomness

618
00:26:34.138 --> 00:26:36.519
or some other way of generating the numbers?

619
00:26:36.519 --> 00:26:39.521
<v ->Randomness is not a great solution.</v>

620
00:26:39.521 --> 00:26:44.419
Usually they're preassigned by some modern technology.

621
00:26:44.419 --> 00:26:46.726
The first protocol, that was Paxos slight,

622
00:26:46.726 --> 00:26:49.054
was by Chandra and Toueg.

623
00:26:49.054 --> 00:26:51.920
And they did as realm base.

624
00:26:51.920 --> 00:26:54.536
In fact I'm gonna be doing similar notion.

625
00:26:54.536 --> 00:26:56.751
But usually, they're based on the knowledge.

626
00:26:56.751 --> 00:26:58.063
And the other way to do that, though,

627
00:26:58.063 --> 00:27:00.013
is you have proposers coming in and out,

628
00:27:00.013 --> 00:27:02.945
then you can the realms reassigned

629
00:27:02.945 --> 00:27:05.369
by a command during the state shifts.

630
00:27:05.369 --> 00:27:07.453
So there's lots of ways to do that.

631
00:27:07.453 --> 00:27:08.674
It's one of those so many blocks,

632
00:27:08.674 --> 00:27:11.169
because it seems like I'm solving Consensus

633
00:27:11.169 --> 00:27:13.905
by having them agree on round inverse, originally,

634
00:27:13.905 --> 00:27:18.072
so it seems circular, but actually agree on numbers.

635
00:27:19.608 --> 00:27:21.994
Any other questions?

636
00:27:21.994 --> 00:27:24.577
Okay, that was a good question.

637
00:27:25.591 --> 00:27:29.187
Okay, here we are, we're going to go from Paxos

638
00:27:29.187 --> 00:27:30.604
to BP Fast Paxos.

639
00:27:32.181 --> 00:27:35.296
I'm going to do this in three steps.

640
00:27:35.296 --> 00:27:38.181
The first step, by the way, Paxos is really an item

641
00:27:38.181 --> 00:27:41.897
and it is very close for you, Cornell students.

642
00:27:41.897 --> 00:27:44.305
But there is no agriculture in Paxos.

643
00:27:44.305 --> 00:27:46.349
What I'm gonna do is three steps.

644
00:27:46.349 --> 00:27:49.280
First thing I'm going to do is continue in a crash model,

645
00:27:49.280 --> 00:27:51.882
but I'm going to change the notion of trust

646
00:27:51.882 --> 00:27:54.932
in a way, that is useful for my protocol.

647
00:27:54.932 --> 00:27:56.188
The second thing I'm gonna do is

648
00:27:56.188 --> 00:27:58.258
I'm gonna consider one way in which proposers

649
00:27:58.258 --> 00:28:00.548
can exhibit byzantine faulty behavior

650
00:28:00.548 --> 00:28:02.577
and I'm gonna solve that problem.

651
00:28:02.577 --> 00:28:04.608
And then that's all I'm gonna leave one other way,

652
00:28:04.608 --> 00:28:08.098
that byzantine proposers can affect behavior,

653
00:28:08.098 --> 00:28:10.384
I'm gonna solve that problem too.

654
00:28:10.384 --> 00:28:13.067
So it turns out, because of the protocol, simple enough,

655
00:28:13.067 --> 00:28:17.596
byzantine failures are pretty easy to solve in this case.

656
00:28:17.596 --> 00:28:20.072
So I'm gonna do these three steps.

657
00:28:20.072 --> 00:28:23.240
Of these, actually, the hardest one is the first one,

658
00:28:23.240 --> 00:28:26.236
which has a number of byzantine failures.

659
00:28:26.236 --> 00:28:27.836
This is the architecture I'm assuming,

660
00:28:27.836 --> 00:28:31.118
just so you see where I'm coming from.

661
00:28:31.118 --> 00:28:35.767
My servers are in cloud, that is a com-pen-se,

662
00:28:35.767 --> 00:28:38.387
really an administrative domain and they're running

663
00:28:38.387 --> 00:28:40.521
both acceptors and learners.

664
00:28:40.521 --> 00:28:41.813
So because they are the one's,

665
00:28:41.813 --> 00:28:43.390
that have to know the outcome.

666
00:28:43.390 --> 00:28:45.659
And so acceptors and learners really enlighten upon,

667
00:28:45.659 --> 00:28:47.230
they are gonna be collocated

668
00:28:47.230 --> 00:28:48.496
and the proposers are gonna

669
00:28:48.496 --> 00:28:50.624
be running out these edge machines,

670
00:28:50.624 --> 00:28:52.288
providing an interface for the clients.

671
00:28:52.288 --> 00:28:53.926
The clients need to know about the proposers,

672
00:28:53.926 --> 00:28:55.682
that can be done in a variety of ways,

673
00:28:55.682 --> 00:28:58.099
they can just be DNS for cup.

674
00:28:59.175 --> 00:29:01.425
The proposers are gonna be assumed

675
00:29:01.425 --> 00:29:03.798
and the entity, byzantine fault tolerant,

676
00:29:03.798 --> 00:29:06.676
so they can't affect the outcome of the servers.

677
00:29:06.676 --> 00:29:09.963
And that's because clients have very broad interface

678
00:29:09.963 --> 00:29:13.022
to the proposers, they can communicate with them,

679
00:29:13.022 --> 00:29:15.950
that proposers have very narrow interface in the circuits,

680
00:29:15.950 --> 00:29:18.103
so compromising that would be hard,

681
00:29:18.103 --> 00:29:19.531
it'd be where, if it happens,

682
00:29:19.531 --> 00:29:22.781
then you do it with detection protocol.

683
00:29:25.148 --> 00:29:27.148
Okay, step one is trust.

684
00:29:28.389 --> 00:29:31.019
Right now, Paxos, the way I've described it,

685
00:29:31.019 --> 00:29:33.796
another thing, that I thought might be asked,

686
00:29:33.796 --> 00:29:36.388
was how does this thing ever terminate, right?

687
00:29:36.388 --> 00:29:37.806
I show you this example,

688
00:29:37.806 --> 00:29:40.530
where these proposers were all stepping triple's toes

689
00:29:40.530 --> 00:29:43.752
and, in fact, the way Paxos normally terminates,

690
00:29:43.752 --> 00:29:45.901
because it's really behaved, usually,

691
00:29:45.901 --> 00:29:49.666
one proposer's the one, that's doing he proposing.

692
00:29:49.666 --> 00:29:54.489
What I'm going to do is make that kind of trust relationship

693
00:29:54.489 --> 00:29:57.306
of the proposer doing something more explicit.

694
00:29:57.306 --> 00:30:00.237
This I'm gonna trust change in Paxos.

695
00:30:00.237 --> 00:30:02.708
So I'm going to first preassign rounds to proposers,

696
00:30:02.708 --> 00:30:04.496
like in round format.

697
00:30:04.496 --> 00:30:07.847
So the first proposer might have one, four, seven,

698
00:30:07.847 --> 00:30:09.764
the next one and so on.

699
00:30:11.219 --> 00:30:16.014
And any acceptor will be able to cause the round to change.

700
00:30:16.014 --> 00:30:19.241
That is, it can say, "I no longer trust what's going on".

701
00:30:19.241 --> 00:30:21.280
And they can just say, change the round.

702
00:30:21.280 --> 00:30:23.317
And in doing so, then another proposer

703
00:30:23.317 --> 00:30:25.244
is going to be used.

704
00:30:25.244 --> 00:30:27.434
So rather, than having a proposers riving in,

705
00:30:27.434 --> 00:30:30.354
the acceptors are going to take a more direct in role

706
00:30:30.354 --> 00:30:33.104
in when the protocol is faulty.

707
00:30:33.104 --> 00:30:36.591
So when an acceptor stops trusting the proposer for round,

708
00:30:36.591 --> 00:30:39.190
remember now, rounds are assigned to proposers,

709
00:30:39.190 --> 00:30:41.555
it's going to send a trust change message

710
00:30:41.555 --> 00:30:44.259
to all the acceptors, remember, this is crash faulty,

711
00:30:44.259 --> 00:30:47.183
so this is an easy thing to do.

712
00:30:47.183 --> 00:30:49.298
And it's just going to say,

713
00:30:49.298 --> 00:30:51.750
"I'm going to round r n d plus one".

714
00:30:51.750 --> 00:30:53.657
So it was in round four, now saying,

715
00:30:53.657 --> 00:30:55.773
"I'm going to round five".

716
00:30:55.773 --> 00:30:57.091
And the acceptor, once it gets that,

717
00:30:57.091 --> 00:30:59.175
if it is at round four earlier,

718
00:30:59.175 --> 00:31:01.098
it's gonna go round five as well.

719
00:31:01.098 --> 00:31:05.098
It's in some later round it will just ignore it.

720
00:31:06.251 --> 00:31:08.318
So when an acceptor receives trust changer,

721
00:31:08.318 --> 00:31:11.734
so that increments is round and sets that.

722
00:31:11.734 --> 00:31:14.891
And it's going to send a promise message back out.

723
00:31:14.891 --> 00:31:16.309
So let me show you this example,

724
00:31:16.309 --> 00:31:18.495
just so you can see how this works.

725
00:31:18.495 --> 00:31:21.066
It's actually the same protocol,

726
00:31:21.066 --> 00:31:24.586
except I'm changing how the messages are being generated.

727
00:31:24.586 --> 00:31:26.737
So here we are again, you'll remember this example,

728
00:31:26.737 --> 00:31:29.246
mod proposers, acceptors and learners.

729
00:31:29.246 --> 00:31:32.919
And then 11, 76 and 22, the only thing different in this

730
00:31:32.919 --> 00:31:34.218
is I have these numbers here

731
00:31:34.218 --> 00:31:35.947
and these are the preassigned rounds.

732
00:31:35.947 --> 00:31:39.421
So this proposer has rounds three, six and nine,

733
00:31:39.421 --> 00:31:42.004
two, five and eight, and so on.

734
00:31:43.008 --> 00:31:47.485
And also this has changed too, they're all at round one,

735
00:31:47.485 --> 00:31:50.794
because they all, they're sort of driving this,

736
00:31:50.794 --> 00:31:52.202
so they just start in the initial state,

737
00:31:52.202 --> 00:31:53.058
which round nine.

738
00:31:53.058 --> 00:31:55.055
Again, that's an empty promise,

739
00:31:55.055 --> 00:31:58.707
cuz you'll never receive a round as cluster remark.

740
00:31:58.707 --> 00:32:02.374
So, in this case, our proposer or round one,

741
00:32:04.356 --> 00:32:07.028
that guy up there, sends out his accept message,

742
00:32:07.028 --> 00:32:10.144
one, 11, those that didn't have to do anything,

743
00:32:10.144 --> 00:32:12.128
it just sends it out, because it's the one,

744
00:32:12.128 --> 00:32:13.793
that owns that round.

745
00:32:13.793 --> 00:32:18.484
And once that message is received by these two,

746
00:32:18.484 --> 00:32:21.822
they only have Consensus, so it's quite efficient.

747
00:32:21.822 --> 00:32:23.617
Of course, the other can be just as efficient as well,

748
00:32:23.617 --> 00:32:25.457
there can be two messages rather than one,

749
00:32:25.457 --> 00:32:27.556
but still, this is quite efficient.

750
00:32:27.556 --> 00:32:31.139
And then this sends out the learn messages.

751
00:32:32.549 --> 00:32:34.729
Now let's say, for some reason,

752
00:32:34.729 --> 00:32:37.876
this one here, this acceptor is tired

753
00:32:37.876 --> 00:32:40.367
of waiting for a message from that proposer,

754
00:32:40.367 --> 00:32:42.493
so it loses faith and it says,

755
00:32:42.493 --> 00:32:44.473
"I no longer trust that one",

756
00:32:44.473 --> 00:32:46.823
so it does a trust change.

757
00:32:46.823 --> 00:32:48.426
When it does that trust change,

758
00:32:48.426 --> 00:32:50.259
these are accepted 11.

759
00:32:51.211 --> 00:32:52.705
Trust change.

760
00:32:52.705 --> 00:32:53.995
I didn't show the messages,

761
00:32:53.995 --> 00:32:55.767
but it convinced this one, also,

762
00:32:55.767 --> 00:32:57.962
that there was a trust change, that message got through,

763
00:32:57.962 --> 00:33:00.034
this one never heard it.

764
00:33:00.034 --> 00:33:01.380
So now we have two acceptors,

765
00:33:01.380 --> 00:33:05.666
that have now decided they're moving on to round two.

766
00:33:05.666 --> 00:33:06.836
Since they move to round two,

767
00:33:06.836 --> 00:33:09.468
they then send out the information they have,

768
00:33:09.468 --> 00:33:11.420
the promise messages to this one,

769
00:33:11.420 --> 00:33:12.761
because that's the one that's two.

770
00:33:12.761 --> 00:33:16.094
So this one didn't have to try to pre-charge this,

771
00:33:16.094 --> 00:33:18.650
this is all based on the fact, that this got tired.

772
00:33:18.650 --> 00:33:20.969
They send out their state

773
00:33:20.969 --> 00:33:22.593
and now what is this acceptor going up

774
00:33:22.593 --> 00:33:25.176
gonna do with this information?

775
00:33:26.073 --> 00:33:27.428
It's gonna try to do an accept

776
00:33:27.428 --> 00:33:29.218
and when the same situation four,

777
00:33:29.218 --> 00:33:33.206
it knows one, cuz accepted the value 11 in round one,

778
00:33:33.206 --> 00:33:34.866
this one hasn't done anything

779
00:33:34.866 --> 00:33:36.924
and so it doesn't know what the value is,

780
00:33:36.924 --> 00:33:38.567
but it's going to assume

781
00:33:38.567 --> 00:33:40.842
that might have been 11 in round one.

782
00:33:40.842 --> 00:33:44.425
And so it's going to send out accept to 11.

783
00:33:48.287 --> 00:33:51.037
That just learned and we're done.

784
00:33:52.643 --> 00:33:57.283
So all I did in this case is I moved the responsibility

785
00:33:57.283 --> 00:33:58.883
from the proposers to acceptors.

786
00:33:58.883 --> 00:34:02.050
This gives the acceptors more control.

787
00:34:03.117 --> 00:34:06.450
This, by the way, first occurred in PDFT

788
00:34:09.562 --> 00:34:10.548
by Castro and Listov,

789
00:34:10.548 --> 00:34:13.800
except it was buried in a protocol, had to extract it.

790
00:34:13.800 --> 00:34:17.967
But this is exactly what they're doing for that purpose.

791
00:34:20.761 --> 00:34:22.371
Okay.

792
00:34:22.371 --> 00:34:23.371
Second step.

793
00:34:24.594 --> 00:34:26.472
I have byzantine faulty proposers.

794
00:34:26.472 --> 00:34:29.427
The last one I showed you is a perfectly correct

795
00:34:29.427 --> 00:34:32.391
Paxos protocol, that works only for crash failures.

796
00:34:32.391 --> 00:34:34.150
So now I'm gonna take a next step

797
00:34:34.150 --> 00:34:35.548
and say how are we going to tolerate

798
00:34:35.548 --> 00:34:37.469
byzantine faulty proposers.

799
00:34:37.469 --> 00:34:40.258
This means the proposer can do whatever it wants to do.

800
00:34:40.258 --> 00:34:44.551
While the context of Paxos, proposers don't do a lot,

801
00:34:44.551 --> 00:34:48.906
all they do is they send out accept messages.

802
00:34:48.906 --> 00:34:50.991
It never sent out a message,

803
00:34:50.991 --> 00:34:52.607
that the old one used to send out a message,

804
00:34:52.607 --> 00:34:54.006
saying please go to this round,

805
00:34:54.006 --> 00:34:54.979
but now it's not doing that,

806
00:34:54.979 --> 00:34:57.499
because it only sends one message, acceptance message.

807
00:34:57.499 --> 00:34:59.938
So you only have to look at what can happen

808
00:34:59.938 --> 00:35:00.771
with an acceptance situation.

809
00:35:00.771 --> 00:35:03.478
Of course, I'm going to have to authenticate channels,

810
00:35:03.478 --> 00:35:04.311
I have to know the message

811
00:35:04.311 --> 00:35:06.140
is coming from who is supposed to be.

812
00:35:06.140 --> 00:35:07.917
So I'm going to have to put keys on that.

813
00:35:07.917 --> 00:35:09.388
But in terms of the protocol,

814
00:35:09.388 --> 00:35:11.289
the only thing, that can go wrong

815
00:35:11.289 --> 00:35:13.211
is going to happen with acceptance message,

816
00:35:13.211 --> 00:35:14.064
cuz that's the only message,

817
00:35:14.064 --> 00:35:15.703
that comes from the proposer.

818
00:35:15.703 --> 00:35:17.335
And proposers can misbehave

819
00:35:17.335 --> 00:35:20.878
in terms of that message in two ways, in terms of safety.

820
00:35:20.878 --> 00:35:22.984
First, it can send an incorrect,

821
00:35:22.984 --> 00:35:24.950
but consistent values in accept.

822
00:35:24.950 --> 00:35:26.621
It can just send whatever it wants,

823
00:35:26.621 --> 00:35:28.747
but it can send it to everyone.

824
00:35:28.747 --> 00:35:33.021
Or it can send different values to the different acceptors.

825
00:35:33.021 --> 00:35:35.125
So either it send a correct message

826
00:35:35.125 --> 00:35:37.541
or it sends an incorrect message,

827
00:35:37.541 --> 00:35:39.048
but that is not what the protocol said,

828
00:35:39.048 --> 00:35:40.992
but the same one to all the acceptors.

829
00:35:40.992 --> 00:35:42.812
Or it sends different values to acceptors,

830
00:35:42.812 --> 00:35:46.683
which means at least one of the is gonna be.

831
00:35:46.683 --> 00:35:49.384
So those are the cases we're in.

832
00:35:49.384 --> 00:35:52.096
And I'm first going to do this one

833
00:35:52.096 --> 00:35:54.679
and then I'm gonna do that one.

834
00:35:57.294 --> 00:36:00.687
The first one is actually fairly easy to solve.

835
00:36:00.687 --> 00:36:02.036
What i'll do is i'll use a trick,

836
00:36:02.036 --> 00:36:05.398
that's used often, when you're trying to take a protocol

837
00:36:05.398 --> 00:36:07.481
and make it byzantine fault tolerant.

838
00:36:07.481 --> 00:36:10.053
And it's called using proofs.

839
00:36:10.053 --> 00:36:12.475
That is, whenever a process sends a message,

840
00:36:12.475 --> 00:36:15.133
if you can have in that message a proof,

841
00:36:15.133 --> 00:36:17.640
saying why you're sending that message

842
00:36:17.640 --> 00:36:20.140
and then that proof can be validated

843
00:36:20.140 --> 00:36:22.345
by the receiving process,

844
00:36:22.345 --> 00:36:24.633
then you can mask a byzantine failure,

845
00:36:24.633 --> 00:36:28.890
because if the message doesn't match the proof,

846
00:36:28.890 --> 00:36:30.952
then the message is faulty,

847
00:36:30.952 --> 00:36:33.527
that is you hit an arbitrarily faulty mechanic.

848
00:36:33.527 --> 00:36:36.053
And this case, what the message is,

849
00:36:36.053 --> 00:36:39.589
that a proposer is sending, based on the promises messages,

850
00:36:39.589 --> 00:36:41.315
is well defined.

851
00:36:41.315 --> 00:36:43.721
It's based on its states.

852
00:36:43.721 --> 00:36:47.888
And so what we'll do here is for any round bridge at zero,

853
00:36:48.964 --> 00:36:51.837
well first, acceptors, when they send promises,

854
00:36:51.837 --> 00:36:53.910
they're going to send their values,

855
00:36:53.910 --> 00:36:55.585
remember, they send their current round

856
00:36:55.585 --> 00:36:58.452
and any value they've agreed on in the earlier round,

857
00:36:58.452 --> 00:37:02.619
both the round and the value, they're gonna be signed.

858
00:37:03.532 --> 00:37:06.421
And then when a proposer sends a value,

859
00:37:06.421 --> 00:37:08.665
it's going to send not only the round and the value,

860
00:37:08.665 --> 00:37:10.523
it's gonna send all these things in collective,

861
00:37:10.523 --> 00:37:14.690
which is basically the data used to say why is that value.

862
00:37:18.651 --> 00:37:20.876
This is actually a nice use of symmetries,

863
00:37:20.876 --> 00:37:24.287
I can use hash based authentication codes,

864
00:37:24.287 --> 00:37:27.244
because I'm not authenticating the source of the message,

865
00:37:27.244 --> 00:37:29.643
I'm just sending information back to the retreat,

866
00:37:29.643 --> 00:37:33.016
so this is actually cheap to do.

867
00:37:33.016 --> 00:37:35.442
And so when an acceptor gives this message,

868
00:37:35.442 --> 00:37:37.672
the round, the value and assigned values,

869
00:37:37.672 --> 00:37:39.913
it will then see, whether the value it got

870
00:37:39.913 --> 00:37:41.798
and the round is supported by these messages,

871
00:37:41.798 --> 00:37:45.025
that were sent by all the acceptors that base this decision.

872
00:37:45.025 --> 00:37:46.451
If any of the signatures were wrong

873
00:37:46.451 --> 00:37:48.010
or if the value was wrong,

874
00:37:48.010 --> 00:37:49.460
then it triggers the trust change,

875
00:37:49.460 --> 00:37:51.683
because something was wrong.

876
00:37:51.683 --> 00:37:54.266
Otherwise it accepts the value.

877
00:37:58.156 --> 00:38:00.615
Again, this is one of the standard tricks we use

878
00:38:00.615 --> 00:38:03.242
for making protocol for byzantine fault tolerance.

879
00:38:03.242 --> 00:38:06.962
It just works out really well in this example.

880
00:38:06.962 --> 00:38:08.366
Okay, that's step one.

881
00:38:08.366 --> 00:38:10.117
<v Listener>So how does your simian</v>

882
00:38:10.117 --> 00:38:14.313
n squared symmetric keys, like Castro did?

883
00:38:14.313 --> 00:38:17.063
Without the authentication codes.

884
00:38:19.539 --> 00:38:22.512
<v ->But these are cheap, these are just halves,</v>

885
00:38:22.512 --> 00:38:24.146
cuz they don't have to, in this case,

886
00:38:24.146 --> 00:38:26.411
authenticate the proposer,

887
00:38:26.411 --> 00:38:27.806
I'm just authenticating the value,

888
00:38:27.806 --> 00:38:30.389
that was sent by the acceptors.

889
00:38:34.483 --> 00:38:36.220
Okay, this second case I have tow worry about

890
00:38:36.220 --> 00:38:40.387
is what happens, when the proposer send inconsistent values.

891
00:38:42.226 --> 00:38:45.753
This is going to be more a problem

892
00:38:45.753 --> 00:38:48.889
if there is no proof available to show,

893
00:38:48.889 --> 00:38:52.376
that the value the proposer is sending is inconsistent.

894
00:38:52.376 --> 00:38:53.314
And there are two cases,

895
00:38:53.314 --> 00:38:56.853
when a proposer doesn't have to give a proof.

896
00:38:56.853 --> 00:38:59.853
The first one is in the first round,

897
00:39:00.769 --> 00:39:02.058
because there is no proof.

898
00:39:02.058 --> 00:39:04.264
The second one, it can send unconstrained values,

899
00:39:04.264 --> 00:39:07.722
if the values are getting faster than the acceptor

900
00:39:07.722 --> 00:39:10.405
are all saying, "I've never accepted a value before",

901
00:39:10.405 --> 00:39:12.716
which is a problem.

902
00:39:12.716 --> 00:39:14.451
In which case it can send any value,

903
00:39:14.451 --> 00:39:16.078
so there's no way to prove,

904
00:39:16.078 --> 00:39:16.911
that the value it's sending

905
00:39:16.911 --> 00:39:18.701
is consistent across all of them.

906
00:39:18.701 --> 00:39:20.903
So I need some way to solve that.

907
00:39:20.903 --> 00:39:23.297
So again, the signature's not constraining the value

908
00:39:23.297 --> 00:39:24.797
or its round form.

909
00:39:26.505 --> 00:39:27.894
I'm gonna call equivocation

910
00:39:27.894 --> 00:39:29.479
and I'm gonna solve equivocation

911
00:39:29.479 --> 00:39:32.157
by increasing my replication requirement.

912
00:39:32.157 --> 00:39:35.411
For those who have studied Paxos,

913
00:39:35.411 --> 00:39:38.411
the variant for crash Paxos as fast,

914
00:39:39.519 --> 00:39:42.205
called Fast Paxos uses a similar technique,

915
00:39:42.205 --> 00:39:44.788
because it has similar problem.

916
00:39:46.093 --> 00:39:49.150
<v Listener>Even if there were sufficient signatures</v>

917
00:39:49.150 --> 00:39:51.308
to constrain the value, that somebody,

918
00:39:51.308 --> 00:39:52.586
that's just stand out,

919
00:39:52.586 --> 00:39:53.835
can we still get to the second case,

920
00:39:53.835 --> 00:39:57.843
just no showing some of the signatures of the receiver?

921
00:39:57.843 --> 00:40:01.460
Can it always post themselves into the second case?

922
00:40:01.460 --> 00:40:03.293
<v ->I skipped over that.</v>

923
00:40:09.872 --> 00:40:14.448
So I am gonna adhere how acceptors also be learners.

924
00:40:14.448 --> 00:40:16.281
But at the other case,

925
00:40:18.802 --> 00:40:20.789
you can imagine a case, what acceptor,

926
00:40:20.789 --> 00:40:22.952
who has not learned anything,

927
00:40:22.952 --> 00:40:25.439
because it may have not received any values

928
00:40:25.439 --> 00:40:28.188
and they still be stuck on round one.

929
00:40:28.188 --> 00:40:29.475
<v Listener>No, what I mean is,</v>

930
00:40:29.475 --> 00:40:31.424
in order for me to propose something,

931
00:40:31.424 --> 00:40:32.689
I might be constrained,

932
00:40:32.689 --> 00:40:34.881
because everything, that I've learned, right?

933
00:40:34.881 --> 00:40:37.869
But then I could just not add the signatures

934
00:40:37.869 --> 00:40:39.420
of things I've learned, except,

935
00:40:39.420 --> 00:40:41.924
that I always look like I'm on constraint.

936
00:40:41.924 --> 00:40:45.770
<v ->Right and some acceptor will know it's going on</v>

937
00:40:45.770 --> 00:40:48.182
if the value could have been consistent.

938
00:40:48.182 --> 00:40:50.806
Could have been decided, chosen.

939
00:40:50.806 --> 00:40:54.167
So I'm going to allow acceptors to be learners.

940
00:40:54.167 --> 00:40:55.820
So I'm gonna solve that problem that way,

941
00:40:55.820 --> 00:40:57.282
I should have put that in here.

942
00:40:57.282 --> 00:40:59.274
I didn't think I'd need it over here.

943
00:40:59.274 --> 00:41:00.425
He played it on a flaw, that I knew about,

944
00:41:00.425 --> 00:41:01.357
but I forgot about it.

945
00:41:01.357 --> 00:41:02.656
So thank you for pointing that out,

946
00:41:02.656 --> 00:41:05.989
it's not a flaw, it's a detail on paper.

947
00:41:10.677 --> 00:41:12.901
Okay, so let me get back to this.

948
00:41:12.901 --> 00:41:15.887
So the way I'm gonna solve the equivocation problem

949
00:41:15.887 --> 00:41:19.309
is I'm gonna increase my replication.

950
00:41:19.309 --> 00:41:22.062
I'm going to have acceptors also be learners,

951
00:41:22.062 --> 00:41:26.003
of course, not all learners have to be acceptors.

952
00:41:26.003 --> 00:41:29.740
If two learned messages and acceptors detects equivocation,

953
00:41:29.740 --> 00:41:32.294
because they see different values coming from the same round

954
00:41:32.294 --> 00:41:35.905
then they trigger a trust change, it's an easy thing to do.

955
00:41:35.905 --> 00:41:39.342
And detecting equivocation, as you'll see as inner party,

956
00:41:39.342 --> 00:41:40.765
increase the number of acceptors

957
00:41:40.765 --> 00:41:43.627
to at least three t plus the value to this.

958
00:41:43.627 --> 00:41:47.139
This is the same value, that is for Fast Paxos.

959
00:41:47.139 --> 00:41:49.297
Now let me show you how this is.

960
00:41:49.297 --> 00:41:51.671
So let's assume here I have two acceptors

961
00:41:51.671 --> 00:41:53.711
and I add up to one faulty value.

962
00:41:53.711 --> 00:41:54.878
One can crash.

963
00:41:55.848 --> 00:41:58.211
And assume I have one acceptor chose to value v

964
00:41:58.211 --> 00:42:00.831
and another acceptor chosen to value v prime,

965
00:42:00.831 --> 00:42:02.698
so it's equivocation.

966
00:42:02.698 --> 00:42:05.372
Now in this world it is possible,

967
00:42:05.372 --> 00:42:09.272
that v was the chosen value, as possible,

968
00:42:09.272 --> 00:42:12.000
v prime was the chosen value, we can't tell,

969
00:42:12.000 --> 00:42:15.275
because we didn't find out what this value is.

970
00:42:15.275 --> 00:42:18.057
You may have to wait for his turn.

971
00:42:18.057 --> 00:42:22.531
So with only three replicas I can't get out.

972
00:42:22.531 --> 00:42:26.906
On the other hand, if I increase myself to four replicas,

973
00:42:26.906 --> 00:42:30.393
for again, one crash failure, then I can solve this.

974
00:42:30.393 --> 00:42:34.464
So if I have two that are assigned worth value v

975
00:42:34.464 --> 00:42:38.631
and one, that has accepted v prime, then we know that,

976
00:42:40.231 --> 00:42:42.898
it's possible that v was chosen,

977
00:42:43.965 --> 00:42:47.711
if we have in this case by a super majority three.

978
00:42:47.711 --> 00:42:50.955
But if this were v prime, then nothing has been chosen,

979
00:42:50.955 --> 00:42:53.955
so it's safe to move forward with v.

980
00:42:56.469 --> 00:42:58.724
So this is the bad case, obviously,

981
00:42:58.724 --> 00:43:00.141
if there are three different value,

982
00:43:00.141 --> 00:43:03.406
v one, v two, v three, then no value could have been chosen.

983
00:43:03.406 --> 00:43:05.498
So if two are the same, if they're all three the same,

984
00:43:05.498 --> 00:43:08.022
then v have been chosen, we know what happens.

985
00:43:08.022 --> 00:43:10.371
If it gets three value and one is different,

986
00:43:10.371 --> 00:43:12.971
it is certainly possible v has been chosen,

987
00:43:12.971 --> 00:43:15.875
so a proposer has to move forward with v,

988
00:43:15.875 --> 00:43:17.743
on the other hand, if it were v prime,

989
00:43:17.743 --> 00:43:19.681
the v prime was no chosen, so in the end,

990
00:43:19.681 --> 00:43:21.613
it would stick with, probably, v.

991
00:43:21.613 --> 00:43:22.797
So by increasing my replicas

992
00:43:22.797 --> 00:43:24.740
form three to four for one failure,

993
00:43:24.740 --> 00:43:26.907
I made a well named model.

994
00:43:31.419 --> 00:43:34.218
So putting that into the rule,

995
00:43:34.218 --> 00:43:38.879
my proposer needs to get at least n minus t promises,

996
00:43:38.879 --> 00:43:42.661
so in this case, three promises and one failure.

997
00:43:42.661 --> 00:43:44.911
And it's going to take the,

998
00:43:46.116 --> 00:43:48.569
well this is just the description,

999
00:43:48.569 --> 00:43:50.910
if Q x V is the set of promises for the largest round,

1000
00:43:50.910 --> 00:43:53.648
at least n minus two times, then in this case two,

1001
00:43:53.648 --> 00:43:55.989
that's what I get, then that's the value, that I have,

1002
00:43:55.989 --> 00:43:57.812
otherwise it's unconstrained.

1003
00:43:57.812 --> 00:43:59.673
So that example, if I had two that were the same,

1004
00:43:59.673 --> 00:44:00.962
I would have to do that,

1005
00:44:00.962 --> 00:44:01.795
because a lot have been chosen,

1006
00:44:01.795 --> 00:44:02.855
if I had only one,

1007
00:44:02.855 --> 00:44:05.883
the a constraint can choose whatever it wishes.

1008
00:44:05.883 --> 00:44:09.270
And then learners are just going to wait until they get

1009
00:44:09.270 --> 00:44:12.207
at least, in this case, three values out of four

1010
00:44:12.207 --> 00:44:13.927
and for all the same in a single round

1011
00:44:13.927 --> 00:44:17.557
and that's the chosen value and obviously would seize

1012
00:44:17.557 --> 00:44:21.724
and equivocation, and as an acceptor it can go too.

1013
00:44:23.260 --> 00:44:25.093
So that's the problem.

1014
00:44:28.533 --> 00:44:29.779
It looks a little more complex,

1015
00:44:29.779 --> 00:44:32.279
but actually it's quite cheap.

1016
00:44:33.589 --> 00:44:37.756
It requires signatures, but it's efficient in that,

1017
00:44:40.954 --> 00:44:44.013
I'm assuming crash failures for the acceptors,

1018
00:44:44.013 --> 00:44:48.571
so even if I need one extra for a single failure,

1019
00:44:48.571 --> 00:44:50.278
but in terms of there were messages,

1020
00:44:50.278 --> 00:44:54.741
it's the same speed as i had before in learning Paxos.

1021
00:44:54.741 --> 00:44:55.927
And since it's crash failures,

1022
00:44:55.927 --> 00:44:57.258
I don't have that same problem,

1023
00:44:57.258 --> 00:44:58.628
I have the byzantine failures and right,

1024
00:44:58.628 --> 00:45:01.211
if one's problematic, then all.

1025
00:45:04.179 --> 00:45:07.929
Okay, let me say a few more comments on this.

1026
00:45:12.028 --> 00:45:14.083
Remember when I started this problem,

1027
00:45:14.083 --> 00:45:17.245
I said I'm using this Mutually Suspicious Domain model,

1028
00:45:17.245 --> 00:45:18.899
so with this I'm assuming,

1029
00:45:18.899 --> 00:45:22.926
that I have these steps, in this case, acceptors

1030
00:45:22.926 --> 00:45:24.988
all within the same domain,

1031
00:45:24.988 --> 00:45:26.728
but you might still worry about what happens

1032
00:45:26.728 --> 00:45:28.356
if those acceptors were attacked,

1033
00:45:28.356 --> 00:45:30.553
how can you detect what's going on?

1034
00:45:30.553 --> 00:45:32.758
Well it turns out, you can take this protocol,

1035
00:45:32.758 --> 00:45:36.377
BP Fast Paxos and move towards something, that detects them.

1036
00:45:36.377 --> 00:45:40.544
Also the case when proposers are byzantine faulty.

1037
00:45:42.044 --> 00:45:44.180
And then doing so, you're actually moving closer

1038
00:45:44.180 --> 00:45:47.906
to the existing protocols for byzantine Paxos.

1039
00:45:47.906 --> 00:45:50.683
And there's two ways to do this.

1040
00:45:50.683 --> 00:45:53.395
This protocol is technically a two step protocol,

1041
00:45:53.395 --> 00:45:55.800
that means it's the fastest that you can have Paxos,

1042
00:45:55.800 --> 00:45:57.896
it's a very efficient protocol.

1043
00:45:57.896 --> 00:46:01.438
If you want to do master of these kinds of behaviors,

1044
00:46:01.438 --> 00:46:03.274
I'm going to have to increase the number of replicas

1045
00:46:03.274 --> 00:46:07.274
to five t plus one and this is the FaB protocol.

1046
00:46:09.411 --> 00:46:11.407
And if you will increase the number of steps,

1047
00:46:11.407 --> 00:46:14.664
then you end up with PBFT, the models for that purpose.

1048
00:46:14.664 --> 00:46:16.671
And so I really hit a point here,

1049
00:46:16.671 --> 00:46:19.580
where if you're trying to handle

1050
00:46:19.580 --> 00:46:21.790
these byzantine failures and acceptors,

1051
00:46:21.790 --> 00:46:22.623
you're gonna end up going

1052
00:46:22.623 --> 00:46:25.790
to these more and efficient protocols.

1053
00:46:27.360 --> 00:46:30.535
Detection of misbehaving acceptors is easier,

1054
00:46:30.535 --> 00:46:32.020
I'm not gonna give you results on that,

1055
00:46:32.020 --> 00:46:33.251
cuz we're still working on that,

1056
00:46:33.251 --> 00:46:34.930
I don't have the lower bounds yet,

1057
00:46:34.930 --> 00:46:37.054
but there certainly are a set of scenarios,

1058
00:46:37.054 --> 00:46:38.434
where you can tell when there's been

1059
00:46:38.434 --> 00:46:40.851
arbitrarily faulty behaviors.

1060
00:46:44.408 --> 00:46:47.658
They involve more expensive signatures.

1061
00:46:49.870 --> 00:46:53.427
The current status of this, I have a student,

1062
00:46:53.427 --> 00:46:55.757
who has implemented this in Mace.

1063
00:46:55.757 --> 00:46:59.609
Mace is a nice program Chip Killney and Berdough,

1064
00:46:59.609 --> 00:47:02.228
it's nice, because if you model check

1065
00:47:02.228 --> 00:47:05.515
and also execute it, it's all in the same language.

1066
00:47:05.515 --> 00:47:08.706
And so this allows us to model check the protocols,

1067
00:47:08.706 --> 00:47:12.213
execute it and ease close to in the next two weeks,

1068
00:47:12.213 --> 00:47:13.576
have this up and running in the platform

1069
00:47:13.576 --> 00:47:15.555
and see what's going on.

1070
00:47:15.555 --> 00:47:17.607
I have colleagues, that would use these datas,

1071
00:47:17.607 --> 00:47:19.795
these are experts in intrusion detection,

1072
00:47:19.795 --> 00:47:22.167
Karl Levitt, Matt Bishop and Jeff Rowe

1073
00:47:22.167 --> 00:47:24.841
and we've been talking about, actually,

1074
00:47:24.841 --> 00:47:27.319
we were working hard on seeing how we want to integrate

1075
00:47:27.319 --> 00:47:29.813
this protocol with intrusion detection.

1076
00:47:29.813 --> 00:47:31.721
Because, obviously, these kind of suspicions,

1077
00:47:31.721 --> 00:47:33.920
that are going within the protocol trust changes

1078
00:47:33.920 --> 00:47:37.625
are also useful for intrusion detection and vice versa,

1079
00:47:37.625 --> 00:47:38.778
maybe the intrusion is extra system

1080
00:47:38.778 --> 00:47:41.246
will now drive the protocol.

1081
00:47:41.246 --> 00:47:44.203
This is has been fairly challenging,

1082
00:47:44.203 --> 00:47:47.978
because the level of detail is quite different,

1083
00:47:47.978 --> 00:47:49.600
intrusion detection are usually looking

1084
00:47:49.600 --> 00:47:52.500
in one set of events time reel, which are fairly generic.

1085
00:47:52.500 --> 00:47:55.803
I'm looking down at what's happening inside my protocol

1086
00:47:55.803 --> 00:47:57.970
and were still developing.

1087
00:48:01.133 --> 00:48:02.383
That's my talk.

1088
00:48:03.367 --> 00:48:05.617
(applause)

1089
00:48:07.994 --> 00:48:09.903
Those protocol derivations, so for any questions,

1090
00:48:09.903 --> 00:48:12.455
I'm more than happy to go back to this.

1091
00:48:12.455 --> 00:48:14.122
<v Listener>I just,</v>

1092
00:48:14.961 --> 00:48:16.655
so I just wanna check things,

1093
00:48:16.655 --> 00:48:19.597
understand what happens, that proposers send the message

1094
00:48:19.597 --> 00:48:22.868
and the acceptor always accepts the first message,

1095
00:48:22.868 --> 00:48:26.040
that he has received and accept

1096
00:48:26.040 --> 00:48:28.997
if he's not promised it later.

1097
00:48:28.997 --> 00:48:30.330
Is that correct?

1098
00:48:31.878 --> 00:48:35.149
<v ->Your statement is just as hard as my statement.</v>

1099
00:48:35.149 --> 00:48:37.941
<v Listener>Sure, i'll try again so,</v>

1100
00:48:37.941 --> 00:48:41.272
each step proposers ask for attempt of promises,

1101
00:48:41.272 --> 00:48:43.213
they'll take nothing before they're on.

1102
00:48:43.213 --> 00:48:44.046
<v ->Correct.</v>

1103
00:48:44.046 --> 00:48:46.137
<v Listener>And then at some point the process says,</v>

1104
00:48:46.137 --> 00:48:49.713
okay accept my value, can we accept to choose to save all,

1105
00:48:49.713 --> 00:48:51.883
I promise to accept nothing before,

1106
00:48:51.883 --> 00:48:54.095
I don't wanna accept your value anyway,

1107
00:48:54.095 --> 00:48:55.241
so then have to accept it

1108
00:48:55.241 --> 00:48:58.324
if he has not promised a later round.

1109
00:48:59.476 --> 00:49:02.249
<v ->In terms of wideness, yes.</v>

1110
00:49:02.249 --> 00:49:05.072
In terms of safety it can still throw it away.

1111
00:49:05.072 --> 00:49:07.606
But the way the protocol is written,

1112
00:49:07.606 --> 00:49:11.073
if an acceptor receives a message, they accept

1113
00:49:11.073 --> 00:49:14.189
and its promise, not its promise,

1114
00:49:14.189 --> 00:49:16.717
it did not promise to not accept, so it said,

1115
00:49:16.717 --> 00:49:18.613
I'm not gonna do anything earlier than two

1116
00:49:18.613 --> 00:49:21.296
and it comes at round six, then yes,

1117
00:49:21.296 --> 00:49:22.852
it's gonna accept that message.

1118
00:49:22.852 --> 00:49:25.762
Technically it doesn't have to, it can throw it away as well

1119
00:49:25.762 --> 00:49:28.608
but it's not gonna be a very light problem.

1120
00:49:28.608 --> 00:49:29.536
<v Listener>I guess I don't understand</v>

1121
00:49:29.536 --> 00:49:30.875
why it's called Consensus,

1122
00:49:30.875 --> 00:49:33.041
this is not what I think that a Consensus is,

1123
00:49:33.041 --> 00:49:35.275
where proposers don't propose values,

1124
00:49:35.275 --> 00:49:38.133
they want to be accepted and they propose something,

1125
00:49:38.133 --> 00:49:39.651
that will get through and accept it,

1126
00:49:39.651 --> 00:49:42.150
it just end up taking what's sent to them

1127
00:49:42.150 --> 00:49:43.306
and they say don't really like them,

1128
00:49:43.306 --> 00:49:45.513
and want three, that everyone else has.

1129
00:49:45.513 --> 00:49:48.960
<v ->So the nice thing about Paxos is by separating proposers</v>

1130
00:49:48.960 --> 00:49:52.877
form acceptors, acceptors are pretty brainless.

1131
00:49:53.769 --> 00:49:55.992
And really all of the interest in action is going on

1132
00:49:55.992 --> 00:49:58.992
between the proposers and acceptors.

1133
00:50:00.779 --> 00:50:02.152
<v Listener>So one question.</v>

1134
00:50:02.152 --> 00:50:04.965
So whenever you have these assumptions about

1135
00:50:04.965 --> 00:50:07.468
the number of 40 producers,

1136
00:50:07.468 --> 00:50:10.792
typically, you use humans at the most one third or half.

1137
00:50:10.792 --> 00:50:13.959
If I make a stronger assumption, like,

1138
00:50:14.927 --> 00:50:17.055
the number of faulty processes is not more

1139
00:50:17.055 --> 00:50:20.612
than 5% of the total number.

1140
00:50:20.612 --> 00:50:22.452
Can you improve protocols,

1141
00:50:22.452 --> 00:50:24.722
maybe make them more efficient and so on

1142
00:50:24.722 --> 00:50:28.746
and it's gonna take one fifth assumption later on, right?

1143
00:50:28.746 --> 00:50:31.055
Because the concept of five there.

1144
00:50:31.055 --> 00:50:32.747
But I assume, that this number of faults

1145
00:50:32.747 --> 00:50:35.179
is much much smaller, than the total number of,

1146
00:50:35.179 --> 00:50:36.690
does that help speed up the protocol?

1147
00:50:36.690 --> 00:50:38.418
Did you why be true to the complications,

1148
00:50:38.418 --> 00:50:42.585
because you might not have 30% corrupted machines.

1149
00:50:44.227 --> 00:50:45.709
<v ->That's an interesting question.</v>

1150
00:50:45.709 --> 00:50:47.492
<v ->Because there must be some trigger,</v>

1151
00:50:47.492 --> 00:50:50.767
which means the assumption on the number of faulty processes

1152
00:50:50.767 --> 00:50:53.184
and can ravage what is there.

1153
00:50:54.279 --> 00:50:57.533
<v ->In this specific case, I don't think so.</v>

1154
00:50:57.533 --> 00:51:00.432
But the interesting trade offs come up,

1155
00:51:00.432 --> 00:51:04.599
when you consider co-dependence or co-variants of them.

1156
00:51:07.123 --> 00:51:11.093
So if you have a protocol, that has been designed

1157
00:51:11.093 --> 00:51:13.495
to one third faulty, right?

1158
00:51:13.495 --> 00:51:16.770
And you know how thing fail dependently,

1159
00:51:16.770 --> 00:51:19.391
then to try to shoe horn your protocol,

1160
00:51:19.391 --> 00:51:21.781
which is based on this threshold and to that environment,

1161
00:51:21.781 --> 00:51:24.462
it's going to cause what we'll replicate.

1162
00:51:24.462 --> 00:51:27.808
But if you know how some information of code variants,

1163
00:51:27.808 --> 00:51:29.757
doesn't have to be them, it's just probabilistic,

1164
00:51:29.757 --> 00:51:31.290
saying if this fails,

1165
00:51:31.290 --> 00:51:33.514
then the probability of this failing will increase,

1166
00:51:33.514 --> 00:51:34.806
then you come out of deployments

1167
00:51:34.806 --> 00:51:36.502
of these lesser applications.

1168
00:51:36.502 --> 00:51:39.085
Then you can be more efficient.

1169
00:51:40.541 --> 00:51:42.136
Yes?

1170
00:51:42.136 --> 00:51:44.198
<v Listener>You suggested,</v>

1171
00:51:44.198 --> 00:51:48.872
it sounded like you measured the correlated failures

1172
00:51:48.872 --> 00:51:52.172
between your servers and the servers, that are outside.

1173
00:51:52.172 --> 00:51:54.123
You guys have some sort of methodology for

1174
00:51:54.123 --> 00:51:57.677
finding the administrative domains,

1175
00:51:57.677 --> 00:51:59.260
that it's not pure.

1176
00:52:01.971 --> 00:52:03.773
<v ->No, we have no such methodology,</v>

1177
00:52:03.773 --> 00:52:06.329
right now, I would assume that would come from the outside.

1178
00:52:06.329 --> 00:52:09.041
That's a great question.

1179
00:52:09.041 --> 00:52:10.565
So some of the work I did,

1180
00:52:10.565 --> 00:52:13.947
this was a couple of years ago with my student.

1181
00:52:13.947 --> 00:52:16.920
We were looking at the false web scams,

1182
00:52:16.920 --> 00:52:20.307
that were being done within our campus

1183
00:52:20.307 --> 00:52:21.870
and out of that understanding what kinds

1184
00:52:21.870 --> 00:52:24.321
of correlated failure we were seeing.

1185
00:52:24.321 --> 00:52:26.114
That's where he found out that machine rooms clusters

1186
00:52:26.114 --> 00:52:29.231
have such high failure tolerance as compared to other rooms.

1187
00:52:29.231 --> 00:52:30.629
Turns out the worst machine we had

1188
00:52:30.629 --> 00:52:34.602
was the one that ran on our student coop machine.

1189
00:52:34.602 --> 00:52:39.499
That one was so infested with malware, it's amazing.

1190
00:52:39.499 --> 00:52:42.623
But also we were looking at the shared configurations

1191
00:52:42.623 --> 00:52:45.004
between the seagulls and our,

1192
00:52:45.004 --> 00:52:47.107
but even within a cluster there tends

1193
00:52:47.107 --> 00:52:49.863
to be a higher degree homogeneity,

1194
00:52:49.863 --> 00:52:52.331
because of them being administrated in a certain way.

1195
00:52:52.331 --> 00:52:56.302
Within a department or office, there's a lot hedge rename,

1196
00:52:56.302 --> 00:52:57.910
in terms of what they want.

1197
00:52:57.910 --> 00:53:01.092
And so our though was, that that could be used to show,

1198
00:53:01.092 --> 00:53:04.453
that you'd be less likely suffer from common attacks.

1199
00:53:04.453 --> 00:53:08.287
The problem with that is the database we're using.

1200
00:53:08.287 --> 00:53:09.908
It's a commercial database,

1201
00:53:09.908 --> 00:53:13.399
which is based on original from circuit board

1202
00:53:13.399 --> 00:53:14.913
of this insert database.

1203
00:53:14.913 --> 00:53:17.189
But I don't have a lot of faith

1204
00:53:17.189 --> 00:53:19.082
in the things they're telling you.

1205
00:53:19.082 --> 00:53:22.082
It's a narrow goal to be as generic,

1206
00:53:23.456 --> 00:53:25.168
they wanna worry you the most they can,

1207
00:53:25.168 --> 00:53:27.057
because that's how they're biased.

1208
00:53:27.057 --> 00:53:29.056
And trying to go a little farther is harder.

1209
00:53:29.056 --> 00:53:31.341
We spent some time trying to instrument machines,

1210
00:53:31.341 --> 00:53:34.341
that we get it from nation from them

1211
00:53:35.475 --> 00:53:36.926
my student started getting gray hair,

1212
00:53:36.926 --> 00:53:38.347
when he started doing all that.

1213
00:53:38.347 --> 00:53:40.040
That's just really me-cas-tus.

1214
00:53:40.040 --> 00:53:41.784
<v Listener>All the machines fail</v>

1215
00:53:41.784 --> 00:53:43.455
and you're trying to hand to run the failures,

1216
00:53:43.455 --> 00:53:45.969
but you have to record their ability.

1217
00:53:45.969 --> 00:53:48.245
<v ->It's really hard, Darryl Wong did some great on them</v>

1218
00:53:48.245 --> 00:53:51.130
a long time ago, but he was able to look at it very narrow,

1219
00:53:51.130 --> 00:53:52.181
if you're trying to identify

1220
00:53:52.181 --> 00:53:55.348
based on vulnerabilities, that's hard.

1221
00:53:56.282 --> 00:53:58.379
I think the right thing to do if you are doing this,

1222
00:53:58.379 --> 00:54:02.492
I would throw money at the people, who fix the machines,

1223
00:54:02.492 --> 00:54:04.054
run security flaws and try to build up

1224
00:54:04.054 --> 00:54:06.066
a large database from what's there,

1225
00:54:06.066 --> 00:54:09.019
so then you go mind matter, see what's going on.

1226
00:54:09.019 --> 00:54:11.071
It sounds like a big data problem.

1227
00:54:11.071 --> 00:54:12.625
<v Listener>Yeah, I know yourself has some poor data,</v>

1228
00:54:12.625 --> 00:54:15.125
so then in every fact failure.

1229
00:54:23.484 --> 00:54:27.732
<v ->Have they given that access to research facility?</v>

1230
00:54:27.732 --> 00:54:30.045
That would be cool.

1231
00:54:30.045 --> 00:54:31.197
That's why we have a big issue

1232
00:54:31.197 --> 00:54:35.616
and I was doing this work early on correlated failures.

1233
00:54:35.616 --> 00:54:38.173
One of the major divisions at UCSD

1234
00:54:38.173 --> 00:54:40.149
was experiencing lots of attacks.

1235
00:54:40.149 --> 00:54:41.089
And I can't tell you the name,

1236
00:54:41.089 --> 00:54:42.818
because they promised me not to.

1237
00:54:42.818 --> 00:54:45.066
Because if it was found out they're having attack,

1238
00:54:45.066 --> 00:54:47.955
they would be very nervous, this stuff is hard.

1239
00:54:47.955 --> 00:54:51.788
I think, that some of these are being debated.

1240
00:54:53.418 --> 00:54:54.344
Yes?

1241
00:54:54.344 --> 00:54:55.698
<v Listener>I've had two questions,</v>

1242
00:54:55.698 --> 00:54:57.615
one of them was of you.

1243
00:54:58.581 --> 00:55:02.414
We looked at byzantine failures for proposers,

1244
00:55:04.000 --> 00:55:05.301
could an acceptors also fail

1245
00:55:05.301 --> 00:55:07.265
and what would happen?

1246
00:55:07.265 --> 00:55:10.874
<v ->So right now, in the way BP Fast Paxos,</v>

1247
00:55:10.874 --> 00:55:13.816
acceptors can only by crashing.

1248
00:55:13.816 --> 00:55:17.054
If they fail by being byzantine faulty then dense are up.

1249
00:55:17.054 --> 00:55:18.647
<v Listener>All dense are up.</v>

1250
00:55:18.647 --> 00:55:20.915
And is there a proof some sort of bound,

1251
00:55:20.915 --> 00:55:24.041
which says, if they have other than crash stop failures,

1252
00:55:24.041 --> 00:55:26.414
then this approach won't work?

1253
00:55:26.414 --> 00:55:29.397
<v ->My protocol will work in proof by giving you an example.</v>

1254
00:55:29.397 --> 00:55:32.168
<v Listener>I understand that, but okay.</v>

1255
00:55:32.168 --> 00:55:35.835
<v ->But the point I was trying to say here is,</v>

1256
00:55:40.344 --> 00:55:43.078
that if you were trying to mask byzantine failures,

1257
00:55:43.078 --> 00:55:46.434
well then you get into some well known results.

1258
00:55:46.434 --> 00:55:49.444
FaB shows, that you need at least five t plus one replicas

1259
00:55:49.444 --> 00:55:52.290
to be able to mask impulsive byzantine proposers,

1260
00:55:52.290 --> 00:55:55.089
so I increased the replication

1261
00:55:55.089 --> 00:55:56.939
or I'll have to add more steps

1262
00:55:56.939 --> 00:55:59.814
and they'll take you to PDFT.

1263
00:55:59.814 --> 00:56:02.094
<v Listener>Another question, which I was,</v>

1264
00:56:02.094 --> 00:56:03.878
I'm surprised no one didn't ask,

1265
00:56:03.878 --> 00:56:07.057
so what happens with your equivocation problem,

1266
00:56:07.057 --> 00:56:11.224
if, for instance, you have a global broadcast channel?

1267
00:56:12.170 --> 00:56:13.170
Okay, sorry.

1268
00:56:17.854 --> 00:56:19.044
<v ->So the global broadcast channel</v>

1269
00:56:19.044 --> 00:56:21.264
has gotta be between the acceptors.

1270
00:56:21.264 --> 00:56:22.190
<v Listener>Sorry?</v>

1271
00:56:22.190 --> 00:56:24.458
<v ->The global broadcast channel between the acceptors.</v>

1272
00:56:24.458 --> 00:56:26.717
<v Listener>That both the acceptors and publishers</v>

1273
00:56:26.717 --> 00:56:28.921
can participate in.

1274
00:56:28.921 --> 00:56:30.682
<v ->Proposers.</v>

1275
00:56:30.682 --> 00:56:35.671
So there's this great paper by Bob Ouldoo about 15 years ago

1276
00:56:35.671 --> 00:56:38.905
where he was looking at redundant broadcast channels

1277
00:56:38.905 --> 00:56:43.836
and showing you how you can build up Consensus protocols

1278
00:56:43.836 --> 00:56:46.596
for arbitrary and crash failures,

1279
00:56:46.596 --> 00:56:48.866
is the result I would go to.

1280
00:56:48.866 --> 00:56:51.456
The problem with that, I think, is that it's synchronous

1281
00:56:51.456 --> 00:56:54.594
and I don't know anyone, but I haven't looked that hard.

1282
00:56:54.594 --> 00:56:58.344
He has solved the problem using asynchronous.

1283
00:56:59.596 --> 00:57:01.679
I assume you could do it,

1284
00:57:03.670 --> 00:57:05.397
it would be a similar kind of argument,

1285
00:57:05.397 --> 00:57:07.008
I think it's what Paxos did.

1286
00:57:07.008 --> 00:57:08.580
That would be interesting, if you ever resulted in that,

1287
00:57:08.580 --> 00:57:09.981
i would love to see it.

1288
00:57:09.981 --> 00:57:11.186
<v Listener>But a broadcast channel,</v>

1289
00:57:11.186 --> 00:57:12.858
could you have sort of partial failures?

1290
00:57:12.858 --> 00:57:14.033
<v ->Exactly right, that's what make</v>

1291
00:57:14.033 --> 00:57:15.504
broadcast channels interesting.

1292
00:57:15.504 --> 00:57:17.626
<v Listener>You can also just have the messages</v>

1293
00:57:17.626 --> 00:57:19.939
not to be accepted, but guy is who is on the line,

1294
00:57:19.939 --> 00:57:21.444
so it'd still have all sorts of issues.

1295
00:57:21.444 --> 00:57:24.762
On the other hand, if you compare to them, it becomes harder

1296
00:57:24.762 --> 00:57:26.889
because if you broadcast two different things,

1297
00:57:26.889 --> 00:57:28.618
you have no idea who heard it,

1298
00:57:28.618 --> 00:57:30.800
regardless of the technology or not.

1299
00:57:30.800 --> 00:57:32.967
<v ->So if you go back to the papers called</v>

1300
00:57:32.967 --> 00:57:36.264
Streets of Byzantia by Ozaf Babaoglu,

1301
00:57:36.264 --> 00:57:39.524
Streets of Byzantia by Ozaf Babaoglu.

1302
00:57:39.524 --> 00:57:42.145
B, a, b, a, o, g, l, u.

1303
00:57:42.145 --> 00:57:44.745
And back in the synchronous world,

1304
00:57:44.745 --> 00:57:47.054
this is ancient stuff, then the synchronous world,

1305
00:57:47.054 --> 00:57:50.293
usually, consensus protocols took granted of multiple rounds

1306
00:57:50.293 --> 00:57:52.121
because it's synchronous, so they use timeouts.

1307
00:57:52.121 --> 00:57:54.977
And the number of rounds you need is,

1308
00:57:54.977 --> 00:57:56.801
if you can tolerate up to t failures

1309
00:57:56.801 --> 00:57:59.520
inside a t plus one or f plus two,

1310
00:57:59.520 --> 00:58:00.898
or f is the actual number of failures,

1311
00:58:00.898 --> 00:58:03.346
those are then released complement protocols.

1312
00:58:03.346 --> 00:58:05.301
And the nice thing about having broadcast,

1313
00:58:05.301 --> 00:58:07.648
plus even if you can have byzantine failures

1314
00:58:07.648 --> 00:58:11.614
or partial delivery, is you can do it in two rounds.

1315
00:58:11.614 --> 00:58:16.361
It's fast and so the value of the broadcast plus a sphere.

1316
00:58:16.361 --> 00:58:17.738
It's a great resolve, if you don't know it,

1317
00:58:17.738 --> 00:58:19.571
look it up, it's good.

1318
00:58:22.237 --> 00:58:23.870
<v Listener>Can you go into a little more detail</v>

1319
00:58:23.870 --> 00:58:26.970
how Paxos is being used in Mace?

1320
00:58:26.970 --> 00:58:28.638
<v ->How Paxos is being used in Mace?</v>

1321
00:58:28.638 --> 00:58:30.055
<v Listener>Yes.</v>

1322
00:58:31.133 --> 00:58:33.415
<v ->A missed data, that's what it is.</v>

1323
00:58:33.415 --> 00:58:37.177
I'm using Mace to logic check Paxos.

1324
00:58:37.177 --> 00:58:40.470
<v Listener>Oh, okay, I'm sorry, I misread.</v>

1325
00:58:40.470 --> 00:58:44.303
<v ->If you know about Mace, you know what it is,</v>

1326
00:58:47.007 --> 00:58:49.547
if you don't, Mace is affectively a language,

1327
00:58:49.547 --> 00:58:51.447
a computer language, a programming language,

1328
00:58:51.447 --> 00:58:55.582
that can be compiled into C or it can be model checked.

1329
00:58:55.582 --> 00:58:58.336
And so you can write code with that as model to,

1330
00:58:58.336 --> 00:58:59.761
it's very useful.

1331
00:58:59.761 --> 00:59:01.322
My students use Mace a lot

1332
00:59:01.322 --> 00:59:02.812
for all the distributing algorithms,

1333
00:59:02.812 --> 00:59:05.357
because no matter what proof they have,

1334
00:59:05.357 --> 00:59:09.524
when they model check it with my interest in the face.

1335
00:59:11.620 --> 00:59:15.787
<v Listener>Okay, alright, let's finish the presentation.</v>