Impossibility of Distributed Consensus with One Faulty Process

Micheal J. Fischer

Nancy A. Lynch

Micheal S. Paterson

Presented by Kangbo Li

Nov 11th

Model Assumptions.

Consensus Protocol \(P\)

An asynchronous system of \(N\) processes,

where each process is made of

A consensus protocol \(P\) is partially correct if

  1. \(P\) never decides on two different decision values at the same time.
  2. both decision values are possible under \(P\).

Remark: a partially correct protocol may not decide.

Example: Synod

Asynchronous System of \(N = (f + 1) + (2f + 1)\) processes.

  • \(f+1\) leaders. (both proposers and learners).
  • \(2f+1\) acceptors.

Internal State: Leaders

  • ballot_num
  • wait_for
  • proposal

Internal State: Acceptors

  • ballot_num
  • accepted

Input output registers

  • For leaders:
    1. \(x_p\) is the leader's proposal.
    2. \(y_p\) is the leader's decision on the proposal.
  • For acceptors:
    1. \(x_p\) is ignored.
    2. \(y_p\) is never decided.

Example: Synod

Transition functions: Leader

  • T1: on start, do send(\(\alpha\), (p1a, self, b)) message to all acceptors for a p1b (promise).
  • T2: On receiving a (p1b, \(\alpha\), b', pval), if b==b', remove \(\alpha\) from the wait list of acceptors, and update the proposal to pval if it is set. If more than half of the acceptors have responded, do a send(\(\alpha\), (p2a, proposal, self, b)). Otherwise, update the ballot number b and do a send (\(\alpha\), (p1a, self, b)).
  • T3: On receiving a (p2b, \(\alpha\), b'), if b==b', remove \(\alpha\) from the wait list of acceptors. If more than half of the acceptors have responded, commit to the proposed value. Otherwise, update the ballot number b and do a send(\(\alpha\), (p1a, self, b)).

Example: Synod

Transition functions: Acceptors

  • T1: On receiving a (p1a, \(\lambda\), b), if b > ballot_num, update the ballot number and reply with a send(\(\lambda\), (p1b, self, ballot_num, pval)).
  • T2: On receiving a (p2a, proposal \(\lambda\), b), if b==ballot_num, accept the proposal and do a send(\(\lambda\), (p2b, self, ballot_num)).

The Message Buffer.

All the messages that are in flight.

\(A_1\) \(\emptyset\)
\(A_2\) (p1a, \(L_1\), 0) (p1a, \(L_2\), 0)
\(A_3\) (p1a, \(L_2\), 0)
\(L_1\) (p1b, \(A_1\), 0, null)
\(L_2\) \(\emptyset\)

Configuration and Step

Configuration: the state of each process + the message buffer.

Step: one process \(p\) receives a message \(m\), makes a transition, and sends some messages.

\(A_1\) \(\emptyset\)
\(A_2\) (p1a, \(L_1\), 0) (p1a, \(L_2\), 0)
\(A_3\) (p1a, \(L_2\), 0)
\(L_1\) (p1b, \(A_1\), 0, null)
\(L_2\) \(\emptyset\)

Configuration and Step

Configuration: the state of each process + the message buffer.

Step: one process \(p\) receives a message \(m\), makes a transition, and sends some messages.

Accessible configuration: a configuration is accessible if there is a run that arrives at it.

\(A_1\) (p2a, 0, \(L_1\), 0)
\(A_2\) (p1a, \(L_1\), 0) (p1a, \(L_2\), 0)
\(A_3\) (p1a, \(L_2\), 0)
\(L_1\) \(\emptyset\)
\(L_2\) \(\emptyset\)

Run

Admissible run

  • All messages send to nonfaulty processes are eventually received.
  • At most one process is faulty.
  • Nonfaulty means the process takes infinite number of steps.

Meaning let \(N\) or \(N-1\) processes run forever!

Deciding run

Some process eventually decide on an output value for \(y_p\).

Partially correct

  1. No accessible configuration has more than one decision value, \(y_p\). In Synod, this means that leaders decision register \(y_p\) never disagree.
  2. For each possible \(v \in \{0, 1\} \), some accessible configuration decides on \(v\). In Synod, this means either decisions are possible.

Totally correct despite one fault

A consensus protocol \(P\) is totally correct in spite of one fault if it is partially correct, and
every admissible run is a deciding run.

IMPOSSIBLE

Lemma 1

If run \(\sigma_1\) and run \(\sigma_2\) involve no common processes, then they commute.

Lemma 1 Eample: Synod

Valence

Lemma 2

If \(P\) is totally correct despite one fault, \(P\) has a bivalent initial configuration.

Lemma 2

Suppose that every initial configuration of \(P\) is univalent.

Observation: When the initial configurations are ordered by grey code, neighboring configurations share valent values.

\(x_1\) \(x_2\) \(x_3\) \(v\)
0 0 0 0
0 0 1 0
0 1 1 0
0 1 0 0
1 1 0 0
1 1 1 0
1 0 1 0
1 0 0 0

Lemma 2 Example: Synod

Synod have bivalent initial configurations, although it is not even close to "every admissible run is deciding".

\(x_1\) \(x_2\) \(v\)
0 0 0
0 1 0 & 1
1 1 1
1 0 0 & 1

Lemma 3

Then, \(\mathcal{D}\) contains a bivalent configuration.

\(\mathcal{D}\) contains both 1-valent and 0-valent configurations.

\(\mathcal{D}\) contains a bivalent configuration

Proof by contradiction: Suppose that \(\mathcal{D}\) contains only univalent configurations.

\(\mathcal{D}\) contains a bivalent configuration

Proof by contradiction: Suppose that \(\mathcal{D}\) contains only univalent configurations.

Bad News

To construct any admissible run, just let the processes take turns forever.

In \(P\), all admissible runs are deciding

\(\implies\)

\(P\) has a bivalent initial configuration

Given a bivalent configuration \(C\) and an event \(e\), \(P\) avoid \(e\) until applying \(e\) leads to a bivalent configuration.

Remarks

Remark 1: Synod is partially correct.

Suppose that two leaders disagree, then there must be an acceptor (say \(A_2\)) that accepted two values.

(p1a, \(L_1\), \(b_1\)) (p1b, \(A_2\), \(b_1\), null) (p2a, \(v_1\) \(L_1\), \(b_1\))

(p1a, \(L_2\), \(b_2\)) (p1b, \(A_2\), \(b_2\), null) (p2a, \(v_1\) \(L_2\), \(b_2\))

Remark 2: in Synod, nonfaulty run may not decide.

Remark 3: This model works for multiple bits of input and output.

More than \(1\) bit of input.

More than \(1\) bit of output.

Just find one bit for which both values can be reached (partial correctness).

Thanks

← →

/