FLP Impossibility Theorem

Mon Mar 01 2021

tags: draft programming computer science self study notes public 6.824 MIT

What does asychronous mean?

You have a distributed system

Introduction

We work under message passing model Asynchronous: clocks are unreliable, non bounded clock skew no assumptions on timing

Question: N nodes have a value between 0 and 1. Eventually all nodes must agree on a value that is meaningful (non-vacuous). If all nodes were given 0, then we have to agree on 0, and if all nodes were given 1, then we have to agree on 1.

Given a set of processors, each with an initial value:

• All non-faulty processes eventually decide on a value
• All processes that decide do so on the same value
• The value that has been decided must have proposed by some process

These three properties are referred to as termination, agreement and validity. Any algorithm that has these three properties can be said to solve the consensus problem.

What is the relation with the two generals problem?

• The FLP is a generalisation of the two generals problem, for N.
• If the two generals have a shared clock, this is possible.

Impossibility theorem:

Also your messages will always be delivered. I may crash any one of you guys.

From your perspec

Processors are allowed to fail according to the fail-stop model - this simply means that processors that fail do so by ceasing to work correctly. There are more general failure models, such as Byzantine failures where processors fail by deviating arbitrarily from the algorithm they are executing. Again, by strengthening the model - by making strong assumptions about what is possible - the authors make their result much more general. The argument is as follows: if a given problem is proven unsolvable in a very restricted environment where only a few things can go wrong, it will certainly be unsolvable in an environment where yet more things can go wrong.

Any such algorithm that tries to give an answer in bounded time must sometimes be wrong.

Statement of the theorem

There is no algorithm that solves the problem ==> any algorithm that terminates in finite time is

Terminology

We have a vector of states $S_1, ... S_n$ We allow nodes to send or receive messages: the conent of the message, and the recipient of the message. $(p, m)$ where $p$ is the recipient and $m$ is the message.

Messages are always delivered in finite time.

Univalent and bivalent: 0-valent, 1-valent.

0-valent means

Bi-valent: if you have a state $M$,

Processes can do one of two things: they can

Allowed operations:

At every step: you may either take a message from the message pile and apply it to the state list, or you may throw a message into the message pile.

Claim: There is no algorithm that starts off in a bivalent state and ends up in a univalent state.

Assume there is a god algorithm that starts with any state list and gives you some output. Ergo, every state you feed it is a univalent state.

Gray Coding: one where you lay out the sequence of n bits and every step you go down you only change one bit. Between any two rows or wrap over back around, you only flip one bit.

There must be two rows that differ in exactly one bit, and have different values 0 and 1 (Proof is trivial.) But if you have to tolerate one crash, then

=> Ergo, there must be some state that is bivalent for any algorithm

And the idea is that we feed in a bivalent state, and keep it bivalent while passing the messages.

we have a message $e = (p, m)$ in the message pile, and there's a way to keep it bivalent

Let C denote the set of states that can be reached from T without delivering this message.

And let D as the set of states that can be reached from T with delivering this message.

In order to keep the entire system bivalent, there must be one bivalent state in D.

Assume by contradiction. So every state in D must be univalent

If a configuration in C is zero valent, delivering a message in C0 will result in a state that is also zero valent. Ditto with one-valent.

If $p$ and $p^{'}$ are different (different receivers), we can reorder the message order, ... F0 to F1 because there will be

It cannot be the case that they are different.