There is a 1:1 correspondence between Interactive Consensus conditions and Error-Correcting Codes.


You have 27 coins, 1 of which is a different weight. Using a balance scale with 2 pans, how can you determine which coin is different in only 4 weighings?

Generalize this to N coins.


Asynchronous consensus is impossible (Fischer, Lynch, and Paterson 1983)

3 circumventions:

  1. weaken: approximate agreement, set agreement, randomized solutions
  2. strengthen synchrony: partially synchronous, failure detectors
  3. condition-based approach: place restrictions on the input to processes

Condition-based approach

Assume a likely case:

  • Fast termination in likely case
  • Still safe in unlikely case


Hamming distance

Number of symbols that differ:

\begin{align*} [\ {\color{red}{0\ 1\ 0}}\ 0\ 1\ ] \\ [\ {\color{red}{1\ 0\ 1}}\ 0\ 1\ ] \\ \end{align*}

The above two words have a Hamming distance of 3.

Hamming distance is a distance

Place every possible word in a binary hypercube: binary cube.svg

\(\ell_1\) distance is the Hamming distance


Naively send message 3×

or cleverly pick code words:

\begin{align*} 00000\quad 00111\quad 01110\quad 01001 \\ 11100\quad 11011\quad 10010\quad 10101 \end{align*}

Hamming distance \( \geq 2 \).

8 code words \( \implies \) 3 bits of information sent

Coding theory

A code \(C\) is \( (f_v, f_c) \)-error/erasure decoding iff its minimal hamming distance is \( > 2f_v + f_c \)

The original, Hamming(7,4), had a minimal hamming distance of 3:


Main Results

General Idea


1. ICCs ∼ ECCs

{conditions that allow IC to be solved despite \(f_c\) crashes and \(f_e\) value domain faults}


{ECCs capable of recovering from \(f_c\) erasures and \(f_e\) corruptions}


[ \( C \) \( \implies \) consensus despite \(f_c\) crashes ]

\( \Updownarrow \)

\(C\)’s Hamming distance is \(f_c+1\)

[ \( C \) \( \implies \) consensus despite \(f_b\) Byzantine faults ]

\( \Updownarrow \)

\(C\)’s Hamming distance is \(2f_b+1\)


Requirements that make an ECC valid ∼ conditions needed to solve IC

FLP \( \implies \) no perfect codes can tolerate erasure failures

Main Implication

agreement problem & conditions

\( \downarrow \)

algorithm to solve problem

Technical details

Form a graph of input vectors, \( G_{f_c,f_v}^C\):

  • Vertices are included iff they meet conditions
  • Vertices are neighbors iff their Hamming distance \(\leq 2f_v + f_c\)

Definition 3.1 & Theorem 3.4: An agreement problem \( (C, f_c,f_v)\) can be solved iff \( \exists h : \) h is constant on every connected component of \( G_{f_c,f_v}^C \)

See 2.1 and 3. \(d(a, b)\) is the Hamming distance between \( a \) and \( b \). \( C \) are the conditions: The set of assumed possible input vectors.




Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. 1983. “Impossibility of Distributed Consensus with One Faulty Process.” Proceedings of the 2nd Acm Sigact-Sigmod Symposium on Principles of Database Systems - Pods ’83. https://doi.org/10.1145/588058.588060.