12

In the known paper Impossibility of Distributed Consensus with one Faulty Process (JACM85), FLP (Fisher, Lynch and Paterson) proved the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death.

In Lemma 3, after showing that D contains both 0-valent and 1-valent configurations, it says:

Call two configurations neighbors if one results from the other in a single step. By an easy induction, there exist neighbors C₀, C₁ ∈ C such that Dᵢ = e(Cᵢ) is i-valent, i = 0, 1.

I can follow the whole proof except when they claim the existence of such C₀ and C₁. Could you please give me some hints?

nbro
  • 15,395
  • 32
  • 113
  • 196
hengxin
  • 1,867
  • 2
  • 21
  • 42
  • 1
    This specific Lemma is the heart of this paper and I observed that it has been used extensively to prove consensus number of a synchroniztion object in another paper "Wait Free Synchronization" by Herlihy. – ultimate cause Feb 01 '17 at 03:58

3 Answers3

6

D (the set of possible configurations after applying e to elements of C) contains both 0-valent and 1-valent configurations (and is assumed to contain no bivalent configurations).

That is — e maps every element in C to either a 0-valent or a 1-valent configuration. By definition of C, there must be a root element that is connected to all other elements by a series of "neighbour" relationships, so there must be a boundary point where an element in C that leads to a 0-valent configuration after e is neighbours with an element in C that leads to a 1-valent configuration after e.

Mankarse
  • 39,818
  • 11
  • 97
  • 141
  • What is a an element in a configuration? More specifically, what is a root element? – nbro Nov 09 '18 at 18:20
  • I guess "element" here is the "processor" mentioned in the paper. But I concern about the definition of "root element", too? Can you clarify this? – hqt Oct 29 '20 at 07:50
  • `By definition of C, there must be a root element that is connected to all other elements by a series of "neighbour" relationships,` And why the definition of C can lead to this statement? – hqt Oct 29 '20 at 09:55
  • I was using the language of the question. `C` in the question and in my answer corresponds to `\mathscr{C}` in the paper. This is a set of configurations defined by "Let `\mathscr{C}` be the set of configurations reachable from C without applying e". Elements of `\mathscr{C}` are configurations. The definition of `\mathscr{C}` describes it as a set of reachable configurations, that is, a set of elements that are all connected by "neighbour" relationships. – Mankarse Oct 30 '20 at 00:04
1

Define a mapping f such that f(C) = 0, if e(C) is 0-valent, otherwise, f(C) = 1, if e(C) is 1-valent.

Because e(C) could not be bivalent, if we assume that D has no bivalent configuration, f(C) could only be either 0 or 1.

Arrange accessible configurations from the initial bivalent configuration in a tree, there must be two neighbors C0, C1 in the tree that f(C0) != f(C1). Because, if not, all f(C) are the same, which means that D has only either all 0-valent configurations or all 1-valent configurations.

nbro
  • 15,395
  • 32
  • 113
  • 196
lxy
  • 91
  • 3
1

I once went down the path of reading all these papers only to discover its a complete waste of time.

The result is not surprising at all.

The paper you mention "[Impossibility of Distributed Consensus with One Faulty Process]" 1

is a long list of complex mathematical proofs that simply equate to:

1) Consensus is a deterministic state

2) one (or more) faulty systems within an environment is a non deterministic environment

3) No deterministic state, action or outcome can ever be reached within a non deterministic environment.

The end. No further thought is required.

This is how it works in the real world outside of acadamia.

If you wish for agents to reach consensus then Synchronous (Timing model) approximation constructs have to be added to make the environment deterministic within a given set of constraints. For example simple constructs like Timeouts, Ack/Nack, Handshake, Witness, or way more complex constructs.

The closer you wish to get to a Synchronous deterministic model the more complex the constructs become. A hypothetical Synchronous model would have infinitely complex constructs. Also bearing in mind that a fully deterministic Synchronous model can never be achieved in a non trivial distributed system. This is because in any non trivial dynamic multi variate system with a variable initial state there exists an infinite number of possible states, actions and outcomes at any point in time. Chaos Theory

Consider the complexity of a construct for detecting a dropped TCP packets because of buffer overflow errors in a router at hop number 21. And the complexity of detecting the same buffer overflow error dropping the detection signal from the construct itself.

tcwicks
  • 495
  • 3
  • 11