0:06

In this lecture we'll see the,

Â um, FLP proof of the impossibility of consensus

Â in asynchronous distributed systems.

Â So consensus is impossible to solve

Â in the asynchronous distributed system.

Â This is a result that was proved,

Â uh, in a now-famous result by Fischer, Lynch and Patterson

Â in 1983, also known as the FLP result,

Â using the, uh, first letters of the last names

Â of the three coauthors of that paper.

Â Uh, before then, many distributed systems designers

Â had been claiming 100% reliability,

Â uh, for their systems,

Â and this result stopped them dead in their tracks.

Â A lot of claims of reliability vanished overnight,

Â and one of the, uh, long-term side effects of this

Â was the multiple 9s of reliability,

Â um, offerings that vendors now publicize

Â for their products and services.

Â 0:50

So once again, just to remind you, um,

Â the asynchronous distributed system has

Â no bounds on message delays and p-or processing delays

Â or, uh, clock drift rates.

Â These might be arbitrarily long or arbitrarily short.

Â The consensus problem requires each process, uh, p,

Â uh, to decide on the same value.

Â So each process p has a state

Â which consists of the program counter, the registers,

Â the stack, the local variables, the heap,

Â anything else that you would consider to be a part of the,

Â uh, core, uh, dump of the process.

Â It also has initial, um, an input register xp,

Â which is initially either 0 or 1.

Â Different processes might have different,

Â uh, input register values,

Â that is, those processes', uh, um, proposal to the group,

Â and then each process also has an output register yp

Â which is initially undecided but needs to be set to 0 or 1.

Â The only constraint is once you set the output register

Â you cannot change it.

Â 1:43

And remember that each,

Â uh, process has its own output register,

Â um, and you want to make sure, uh, that the consensus,

Â uh, uh, protocol at the end, um,

Â uh, has all the non-faulty processes

Â set their output variables to be all-0s or-or all-1s.

Â So you want an all-0s decision

Â among the non-faulty processes

Â or an all-1s decision among the non-faulty processes.

Â Once again, this problem just by itself, just with these, uh,

Â two, uh, constraints is enough, uh, to solve consensus

Â because you can just say,

Â "Well, everyone set their output variables to be 0

Â all the time, and that solves it,"

Â but that is not interesting or, uh, useful at all.

Â So we have the non-triviality clause that says that

Â at least one initial system state leads to each

Â of the above outcomes,

Â meaning that at least one initial system state

Â leads to an all-0s outcome,

Â and at least one initial system state

Â leads to an all-1s outcome.

Â 4:11

Now we also define an event.

Â This is slightly different from the Lamport events

Â you've seen before.

Â An event consists of, uh,

Â three steps which are executed atomically, or in one shot.

Â Uh, the event starts with the receipt of a message

Â by a process, say a process p.

Â Then the message is processed by the process p.

Â Uh, this may change the recipient's state.

Â Process p's state might change as a result of this,

Â and p might also resi-decide to send out some messages,

Â as a result of this receipt,

Â and those messages that then result,

Â are then deposited in the global message buffer.

Â Uh, so all these three, uh, steps put together,

Â uh, determine an event.

Â So an event essentially consists

Â of a process p receiving a message,

Â uh, processing it and then depositing the resulting,

Â uh, messages into the global message buffer and then,

Â uh, that's an event.

Â 4:55

Next we'll define a schedule.

Â A schedule is simply a linear sequence of events,

Â so one event followed by another event followed by another event,

Â that's a schedule, okay?

Â So here on the left is an example of a schedule.

Â You start with a configuration or a global state;

Â we label that as c.

Â An event e' is applied to it.

Â This means that process p' receives m',

Â uh, processes it and deposits any resulting messages

Â into the global message buffer.

Â That changes the state of process p'.

Â It also changes the state

Â of the global message buffer potentially,

Â and that means the configuration itself has changed,

Â and it has changed to something else which we label as c'.

Â A different event, e'',

Â will change the configuration again similarly to, uh,

Â another configuration c''.

Â Now, these two events, e' followed by e'',

Â is a schedule, because it's a linear sequence of events,

Â and we call that a schedule s.

Â When the schedule s is applied on the initial configuration c,

Â this c here is the same as this c here,

Â it results in the configuration c''.

Â Again, this c'' is the same as the c, this c''.

Â So the left side of the slide

Â is equivalent to the right side of the slide.

Â 'Kay, so the schedule is, essentially,

Â a compact way of representing a sequence of events

Â rather than mentioning each event separately.

Â So, here is our first, uh, lemma, or our first result.

Â It says that disjoint schedules are commutative.

Â What does this mean?

Â If I have a schedule s1,

Â consisting of some sequence of events,

Â and another schedule s2,

Â consisting of another sequence of events,

Â if the sets of receiving processes in s1,

Â remember that each schedule consists of a set of messages

Â being received as a set of processes,

Â if I consider all these processes in s1,

Â which received messages,

Â and all the processes in s2, that receive messages,

Â if these two sets are disjoint,

Â meaning there are no processes in common,

Â uh, receiving messages in both s1 and s2,

Â then these schedules are commutative.

Â In other words, their order can be flipped.

Â So if you apply s1 first on a configuration c

Â and then s2 to reach, to reach a state c'',

Â then in a different scenario,

Â if you apply s2 first on, uh, c, and then s1,

Â you would reach the same final configuration,

Â c'', okay?

Â So, uh, w-why is this true?

Â Well, um, this is true because

Â these are disjoint sets of receiving processes,

Â and applying s1 or s2 in any order

Â would result in the same final outcome.

Â In fact, interweaving s1 and s2

Â would also result in the same outcome,

Â which would be the configuration c''.

Â So earlier, uh, we saw consensus problem here.

Â We tried to prove the impossibility

Â about an easier consensus problem where some process,

Â not just all, but some process, eventually sets its yp variable,

Â its upper variable, to be 0 or a 1.

Â 'Kay, and also we'll assume that only one process crashes,

Â but we are free to choose which process, uh, crashes.

Â Uh, we define configurations to have valences.

Â Uh, configuration C may have

Â a set of decision values V reachable from it,

Â and since we are only considering 0 or 1 decisions,

Â um, there might be either 2 or 1 decisions reachable from it.

Â If both the decisions, both,

Â and all-0s and an all-1s outcome are reachable from it,

Â then we say that the size of the valency is 2,

Â and we say that the configuration C is bivalent.

Â If only one decision is reachable from it,

Â either a 0, an all-0s decision,

Â or an all-1s decision, uh, not both, uh,

Â then the configuration C is said to be, uh,

Â 0-valent or 1-valent, respectively.

Â 8:57

So let's show the first, um, part of this proof,

Â that's the second lemma.

Â Uh, i-uh, here we show that

Â some initial configuration is bivalent.

Â Well let's assume, uh, that this is not true;

Â let's prove it by contradiction.

Â Let's assume that all initial configurations are either

Â 0-valent or 1-valent, okay?

Â Now, if there are N processes in the system,

Â there are 2^N positive initial configurations.

Â Well, why is this?

Â Well each of the processes can propose either 0 or 1

Â for its input variable,

Â and so you have two possibilities for each process,

Â and so this means that there are 2^N

Â possible initial configurations.

Â Now we create a lattice here,

Â this is, of course, a virtual lattice,

Â uh, where the nodes in the lattice

Â are the initial configurations,

Â so there are 2^N, uh, nodes in this lattice.

Â This lattice is essentially a hypercube, uh, with dimension N.

Â uh, we, uh, link two, uh, configurations together,

Â we join them by an edge, uh,

Â if they're d-if they differ in the initial xp,

Â the initial input variable value for exactly one process, okay?

Â Uh, this means that, uh,

Â you know, suppose I have, uh, 2 processes, P1 and P2,

Â uh, then I'm going to have a lattice that has, uh, four, um,

Â uh, nodes in it, four initial configurations

Â where the initial values for, uh, the, um, uh, for the, uh,

Â uh, uh, ini-for the input variables are 0,0,1,0,1,1,

Â and um, uh, 0,1.

Â And in this, uh, the 0,0 node is going to be linked

Â to the 1,0 node because they,

Â uh, differ in the input variable values for P1 only,

Â exactly 1 process.

Â Also, the 1,1, uh, node is going to be linked to the, um,

Â 1,0 node because, uh, these 2 configurations differ

Â in the input variable values for P2.

Â And so, essentially, the hypercube in this 2 process case

Â looks like a square.

Â The hypercube for the 3 process case

Â looks like a cube,

Â and so on and so forth, okay?

Â Now, essentially, um, this, uh, here we are saying

Â that each configuration is either 0-valent or 1-valent,

Â there are no bivalent configurations.

Â So we tag each configuration with a 0 or a 1

Â according to its, uh, valency, either 0-valent or 1-valent.

Â 11:24

So this means that these two configurations differ

Â in the input variables for exactly one process,

Â say that process is p,

Â and let's say we consider around

Â where this process p has crashed;

Â that is, it is silent throughout.

Â Both the initial configurations are indistinguishable,

Â because the only thing that differed

Â between these configurations is the state of p,

Â but p has crashed, so as far as the system running is concerned,

Â p has no effect on it,

Â but this means that both these initial configurations

Â are in fact the same.

Â One of them will, in fact, result in an all-0's outcome,

Â the 0-valent configuration,

Â and the other one will result in a one-in an all-1's outcome

Â because it's a 1-valent configuration.

Â So this initial configuration,

Â either one of these two configurations

Â where p has crashed is, in fact, a bivalent configuration

Â because it may result in an all-0's decision

Â or it may result in an all-1's decision.

Â 'Kay, so we have shown

Â that when you have one process that could crash,

Â and we can choose which process is the one that crashes,

Â you can have at least one bivalent configuration

Â that is the initial configuration in the system.

Â Okay, so that's the first part of the proof.

Â 12:28

Next we need to show that,

Â um, starting from a bivalent configuration,

Â there is always another bivalent configuration that is reachable.

Â Notice that this proof doesn't say

Â that you can never reach consensus ever.

Â It says that there is always some way in which

Â you can be prevented from reaching consensus.

Â Let the red configuration be a bivalent configuration,

Â and let, uh, the event e,

Â which consists of the process p receiving a message m,

Â that is the global message buffer in the red configuration,

Â the sum event that is applicable to the initial configuration,

Â so m is in the global message buffer in the red configuration.

Â Now let's put our hand on e and prevent e from being applied.

Â This means that you might be able to still apply

Â some other events on the red configuration,

Â and there are some configurations

Â that you might be able to reach,

Â starting from this red configuration.

Â We call that set to be C, okay?

Â Those are the blue configurations

Â that are shown in the triangle.

Â These are the configurations

Â that are reached without applying the special event e.

Â why are we not applying e?

Â You'll see in a moment, there is a reason for it.

Â Now, if you take any one of these

Â blue or the red configurations in the-in the triangle,

Â and you apply the single event e to it,

Â the special event e to it,

Â you will reach another dark blue event.

Â Let that set of events, the dark blue set of events,

Â be called as D, 'kay?

Â Once again, D, any event in,

Â any configuration D is reached by applying the special event e

Â on any one of the configurations in the triangle.

Â Now, this is the summary of what we have discussed.

Â You have the initial bivalent configuration, the red one.

Â You don't apply the event e to it, and you reach,

Â and all the possible states, uh,

Â that are reachable are in the triangle.

Â You take one of the configurations in the triangle

Â and you apply the event e to it,

Â you'll reach a state that is,

Â or a configuration that is in the set D.

Â Okay, so we claim that

Â the set D contains a bivalent configuration, okay,

Â and, again, the proof here is by contradiction.

Â If you can show that the state D contains

Â a bivalent configuration,

Â then you can show that

Â there is a sequence that consists of at least one event

Â that starts from a bivalent configuration, the red one,

Â that also leads to another bivalent configuration.

Â Let's assume the contradiction.

Â Suppose that D only has 0 and 1-valent contradiction, uh,

Â configurations and no, uh, bivalent ones.

Â Okay, So there are these states in D,

Â are going to be tagged with a 0 or a 1,

Â and because each stated D has a parent in, uh, C from which,

Â on which e was applied to obtain that D state,

Â we also, uh, tag its parent with the corresponding 0 or 1.

Â Now what you have is you have a C of mixing 0's and 1's here,

Â and therefore, just by the same argument that we use before,

Â where we showed that

Â there has to be at least one bivalent configuration

Â because at least one 0-valence state and one 1-valence state

Â are adjacent to each other,

Â you can show here as well, that in this triangle

Â there's going to be at least two configurations,

Â that are adjacent to each other,

Â because all of them are linked by other events other than e

Â so that one is tagged with a 0, the other is tagged with a 1.

Â In other words, it has to be the case that there are states

Â or configurations D0 and D1, both in D,

Â and C0 and C1 both in C

Â such that D0 is 0-valent, D1 is 1-valent.

Â D0 is obtained from C0 by applying e,

Â D1 is obtained from

Â C1 by applying e, and C1 is adjacent to C0,

Â which means that C0 is, on C0 if you apply some event e'

Â a special event e', you will obtain C1.

Â So given this, there are two possibilities.

Â First, that the process, receiving the message p'

Â in the special event e' is the same as p,

Â which is the process receiving the message in event e,

Â and the second case is that p' is, uh, not the same as p,

Â 'Kay, so let's consider the first case,

Â p' is not the-the same as p.

Â from the previous slides,

Â C0, when you apply e' to it, you get C1.

Â C0, when you apply e to it, you get D0.

Â C1, when e is applied to it you get D1.

Â Since e and e'

Â have different sets of receiving processes,

Â these are disjoint sequences,

Â and so flipping the order in which they are applied,

Â e' first, followed by e, or e followed by e',

Â will give you the same final configuration.

Â In other words, you can draw this red arrow here

Â and show that you can reach from D0 you can reach D1 as well.

Â But this is a contradiction, because we said D0 was 0-valent,

Â but we have just showed that

Â from D0 you can reach a 1-valent state as well,

Â which means that in fact D0 is bivalent,

Â and that is a contradiction.

Â 17:26

uh, and it does not take any steps

Â in this schedule s over here.

Â But it's a deciding round,

Â which means that when final configuration A is reached,

Â a decision has been made, okay?

Â Now, what is that decision?

Â Well, we don't know what the decision is.

Â So now, since p is not there in the schedule s,

Â the schedule s is disjoint from the schedule consisting

Â of the single event e,

Â and so these two schedules can be commutated.

Â So if you apply e first followed by schedule s,

Â that is, you apply schedule s on D0, you reach some state E0,

Â which has to be a 0-valent state because D0 is 0-valent.

Â On the other hand, if you apply schedule s first followed by e,

Â in other words, when you apply e on A,

Â you get the same 0-valent state E0.

Â On the other hand, if you apply e' and e followed by s,

Â or s followed by e' and e,

Â remember that these two schedules are disjoint

Â because p appears in only this schedule but doesn't appear here

Â and then what you will see is

Â that you, uh, reach from A another sche-configuration E1,

Â which is also reachable from D1.

Â But because it's reachable from D1,

Â E1 must be a 1-valent configuration.

Â However, we said that A was a deciding state

Â in which either an all-0's decision

Â or an all-1's decision had already been reached.

Â However, here you can see that from A you can reach both

Â a 0-valent configuration E0

Â as well as 1-valent configuration E1.

Â This is a contradiction, because said that A is a deciding state,

Â and this means that from C0

Â you, might never, ever be able to reach a decision, okay?

Â So this is a contradiction for the second case,

Â and this completes our proof.

Â Here we have shown that, uh,

Â starting from a bivalent configuration,

Â there is always another bivalent configuration that is reachable

Â by applying at least one event,

Â uh, from the initial bivalent configuration.

Â Okay, so essentially this means that, um, uh,

Â there is always something that can go wrong in the system

Â that, uh, keeps the system in a bivalent state.

Â This doesn't mean that

Â the system will never reach consensus.

Â It means that there is at least some path,

Â some sequence of events,

Â that, um, will prevent the system from reaching consensus,

Â that is, it stays bivalent forever.

Â 19:28

So in summary here,

Â the consensus problem is an important problem

Â because it deals with agreement in distributed systems.

Â Solutions exist in the synchronous system model,

Â but we have just shown here that it is impossible to solve

Â in the asynchronous system model.

Â Uh, this is important because asynchronous system model

Â is what is true in the internet,

Â um, um, uh, and the other, uh,

Â distributed systems that appear in cloud computing systems.

Â The key idea in the FLP impossibility proof

Â is that just one slow or, uh,

Â crashed process can prevent the other processes in the system

Â from ever reaching a-a decision.

Â And again, nowhere in the proof that we've seen, so far,

Â have we actually discussed

Â details of the consensus protocol that you might propose.

Â Uh, wh-what we have discussed so far

Â applies to any consensus protocol that you might propose,

Â and that's the beauty of the proof,

Â that it is generic

Â and it applies no matter what the protocol is trying to do.

Â It, all it assumes is that protocols, uh, send messages.

Â Okay, and this is one of the most fundamental results

Â in distributed systems, uh, and that's why we have discussed it.

Â