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.